P3168 [CQOI2015]任务查询系统 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

平常都是单点修改，区间修改就是差分呗，然后前缀和，我们要知道主席树本身就是有前缀和的性质。

//code by SPzos
/*
4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3
*/
#include<bits/stdc++.h>
#define ll long long
#define double
#define fo(i,j,k) for(register int i=j;i<=k;++i)
#define fd(i,j,k) for(register int i=j;i>=k;--i)
#define ff(i,x) for(register int i=head[x];i;i=e[i].nxt)
#define fv(i,x) for(register int i=0;i<v[x].size();++i)
using namespace std;
const int N=100010;
inline int read(){
    int ret=0,f=0;
    char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') f=1;ch=getchar();}
    while(ch>='0' && ch<='9') {ret=(ret<<1)+(ret<<3)+ch-(1<<4)-(1<<5);ch=getchar();} 
    return f?-ret:ret;
}
struct tree{
    int ls,rs;
    ll sum,cnt;
}t[N*105];
int n,m,cnt;
inline void build(int &x,int l,int r){
    x=++cnt;
    if(l==r) return ;
    int mid=l+r>>1;
    build(t[x].ls,l,mid); 
    build(t[x].rs,mid+1,r); 
}
int a[N],b[N],rt[N<<6];
inline void update(int &x,int pre,int l,int r,int pos,int v){
    x=++cnt;
    t[x]=t[pre];
    t[x].sum+=v*b[pos];
    t[x].cnt+=v;
    if(l==r) return ;
    int mid=l+r>>1;
    if(pos<=mid) update(t[x].ls,t[pre].ls,l,mid,pos,v);
    else update(t[x].rs,t[pre].rs,mid+1,r,pos,v);
}
vector<int> be[N],up[N];
inline ll query(int x,int l,int r,int k){
    if(l==r) return t[x].sum/(t[x].cnt)*k;
    int num=t[t[x].ls].cnt;
    int mid=l+r>>1;
    if(k<=num) return query(t[x].ls,l,mid,k);
    else return t[t[x].ls].sum+query(t[x].rs,mid+1,r,k-num);
}
int main(){
    n=read();m=read(); 
    fo(i,1,n){
        int x=read(),y=read();
        a[i]=b[i]=read();
        up[x].push_back(i);
        be[y+1].push_back(i);
    }
    sort(b+1,b+1+n);
    int tot=unique(b+1,b+1+n)-b-1;
    build(rt[0],1,tot);
    fo(i,1,m){
        rt[i]=rt[i-1];
        for(register int j=0;j<up[i].size();++j){
            int p=lower_bound(b+1,b+1+tot,a[up[i][j]])-b;
            update(rt[i],rt[i],1,tot,p,1);
        }
        for(register int j=0;j<be[i].size();++j){
            int p=lower_bound(b+1,b+1+tot,a[be[i][j]])-b;
            update(rt[i],rt[i],1,tot,p,-1);
        }
    }
    ll la=1;
    fo(i,1,m){
        int x=read(),a=read(),b=read(),c=read();
        int k=(a*la+b)%c+1;
        if(k>t[rt[x]].cnt) la=t[rt[x]].sum;
        else la=query(rt[x],1,tot,k);
        printf("%lld\n",la);
    }
    return 0;
}