主席树学习

很好的博客：https://blog.csdn.net/qq_39809664/article/details/79934516

#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn=1000000+10101;
inline int read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
int n,m,a[maxn],tree[maxn*20],rt[maxn*20],cnt,lc[maxn*20],rc[maxn*20];
//rt[i]为插入i个点后的树的根节点编号
void build(int &k,int l,int r){
k=++cnt;
if(l==r){tree[k]=a[l];return ;}
int mid=l+r>>1;
build(lc[k],l,mid);build(rc[k],mid+1,r);
return ;
}
void change(int &k,int pre,int l,int r,int q,int v){
k=++cnt;lc[k]=lc[pre];rc[k]=rc[pre];tree[k]=tree[pre];
if(l==r){tree[k]=v;return ;}
int mid=l+r>>1;
if(mid else change(lc[k],lc[pre],l,mid,q,v);
}
int query(int k,int l,int r,int pos){
if(l==r)return tree[k];
int mid=l+r>>1;
if(pos<=mid)return query(lc[k],l,mid,pos);
else return query(rc[k],mid+1,r,pos);
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
build(rt[0],1,n);
for(int i=1;i<=m;i++){
int vi=read(),opt=read(),x=read();
if(opt==1)change(rt[i],rt[vi],1,n,x,read());
else printf("%d\n",query(rt[vi],1,n,x)),rt[i]=rt[vi];
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn=1000000+10101;
inline int read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
int len,n,m,a[maxn],b[maxn],cnt,rt[maxn*20];
struct wzq{
int sum,lr,rc;
}tre[maxn*20];
void build(int &k,int l,int r){
k=++cnt;
if(l==r)return ;
int mid=l+r>>1;
build(tre[k].lr,l,mid);build(tre[k].rc,mid+1,r);
return ;
}
void update(int l,int r,int &now,int pre,int pos){
tre[++cnt]=tre[pre];
now=cnt;
tre[cnt].sum++;
if(l==r)return ;
int mid=l+r>>1;
if(pos<=mid)update(l,mid,tre[now].lr,tre[pre].lr,pos);
else update(mid+1,r,tre[now].rc,tre[pre].rc,pos);
return ;
}
int query(int l,int r,int x,int y,int pos){
if(l==r)return l;
int xx=tre[tre[y].lr].sum-tre[tre[x].lr].sum;
int mid=l+r>>1;
if(xx>=pos)return query(l,mid,tre[x].lr,tre[y].lr,pos);
return query(mid+1,r,tre[x].rc,tre[y].rc,pos-xx);
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i];
sort(a+1,a+n+1);
len=unique(a+1,a+1+n)-a-1;
build(rt[0],1,m);
for(int i=1;i<=n;i++){
int t=lower_bound(a+1,a+1+m,b[i])-a;
update(1,m,rt[i],rt[i-1],t);
}
for(int i=1;i<=m;i++){
int l=read(),r=read(),k=read();
printf("%d\n",a[query(1,m,rt[l-1],rt[r],k)]);
}
return 0;
}

这道题可以对每秒建棵权值线段树，并以1～lim（优先级的最大值）为区间大小记录个数，这样就可以处理在x秒的第k小前缀和了，

但是lim因为很大，可能会导致MLE，所以要离散化一下

// luogu-judger-enable-o2
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn=201010;
inline int read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
int n,m,cnt,tot,rt[maxn],to[maxn],h[maxn];
ll ans=1;
struct wzq{ll sum;int sz,lr,rc;}tre[maxn*128];
struct hhh{int pos,v;}b[maxn];
bool cmp(hhh i,hhh j){return i.posvoid build(int &k,int l,int r){
k=++cnt;
if(l==r)return ;
int mid=l+r>>1;
build(tre[k].lr,l,mid);build(tre[k].rc,mid+1,r);
return ;
}
void change(int &k,int pre,int l,int r,int tag){
k=++cnt;
tre[k]=tre[pre];tre[k].sum+=tag;
if(tag<0)tre[k].sz--;
else tre[k].sz++;
if(l==r)return ;
int mid=l+r>>1;
if(abs(tag)<=h[mid])change(tre[k].lr,tre[pre].lr,l,mid,tag);
else change(tre[k].rc,tre[pre].rc,mid+1,r,tag);
return ;
}
ll query(int k,int l,int r,int pos){
if(l==r)return 1ll*tre[k].sum/tre[k].sz*min(pos,tre[k].sz);
int mid=l+r>>1;
if(tre[tre[k].lr].sz>=pos)return 1ll*query(tre[k].lr,l,mid,pos);
return 1ll*tre[tre[k].lr].sum+query(tre[k].rc,mid+1,r,pos-tre[tre[k].lr].sz);
}
int main(){
m=read();n=read();
for(int i=1;i<=m;i++){
int x=read(),y=read(),z=read();
b[++tot].pos=x;b[tot].v=z;
b[++tot].pos=y+1;b[tot].v=-z;
h[i]=z;
}
sort(h+1,h+m+1);
int tot1=unique(h+1,h+m+1)-h-1;
sort(b+1,b+tot+1,cmp);build(rt[0],1,tot1);
for(int i=1;i<=tot;i++)change(rt[i],rt[i-1],1,tot1,b[i].v);
for(int i=tot;i>=1;i--)if(b[i].pos!=b[i+1].pos)to[b[i].pos]=i;
for(int i=1;i<=m;i++)if(!to[i])to[i]=to[i-1];
for(int i=1;i<=n;i++){
ll x=read(),a=read(),b=read(),c=read();
ll k=(1ll*a*ans+b)%c+1;
x=rt[to[x]];
if(tre[x].sz<=k)ans=1ll*tre[x].sum;
else ans=query(x,1,tot1,k);
printf("%lld\n",ans);
}
return 0;
}