http://www.lydsy.com/JudgeOnline/problem.php?id=3932

主席树棵题

按时间每次建一棵线段树

然后合并成主席树

考虑差分的性质

对于三元组(S,E,P)

每次修改变为

在S时间时，P处+1

在T+1时间时，P处-1

然后对应的区间也做相同的操作

根据修改操作建树

#include
     
      #include
      
       #define FOR(i,s,t) for(register int i=s;i<=t;++i)using namespace std;typedef long long ll;const int NlogN=8000011;const int N=400011;struct node{    int ls,rs;    int sum;    ll res;}tr[NlogN];int n,m;int a[N>>1];int root[N>>1];struct cg{    int t,p,v;    inline bool operator<(cg A)const{        if(t!=A.t)return t
       
        A.v;    }}c[N];int s,t,p,tot,cnt,cpy;inline void disc_init(){    sort(a+1,a+a[0]+1);    a[0]=unique(a+1,a+a[0]+1)-a-1;    FOR(i,1,(n<<1))c[i].p=lower_bound(a+1,a+a[0]+1,c[i].p)-a;}inline void change(int p,int &now,int l,int r,int pos,int v){    tr[now=++cnt]=tr[p];    tr[now].sum+=v;tr[now].res+=1ll*v*a[pos];    if(l==r)return;    int mid=(l+r)>>1;    pos<=mid?change(tr[p].ls,tr[now].ls,l,mid,pos,v):change(tr[p].rs,tr[now].rs,mid+1,r,pos,v);}inline ll query(int now,int l,int r,int k){    if(!now)return 0;    if(l==r)return !tr[now].sum?0:1ll*tr[now].res/tr[now].sum*k;    int mid=(l+r)>>1;    int data=tr[tr[now].ls].sum;    if(k<=data)return query(tr[now].ls,l,mid,k);    return tr[tr[now].ls].res+query(tr[now].rs,mid+1,r,k-data);}ll pre=1;int A,B,C,x,k;int main(){    scanf("%d%d",&n,&m);    FOR(i,1,n){        scanf("%d%d%d",&s,&t,&p);        c[++tot]=(cg){s,p,1};c[++tot]=(cg){t+1,p,-1};        a[++a[0]]=p;    }    disc_init();    sort(c+1,c+(n<<1|1));    tot=1;    FOR(i,1,100000){        root[i]=root[i-1];        while(c[tot].t==i&&tot<=(n<<1)){            cpy=root[i];            change(cpy,root[i],1,a[0],c[tot].p,c[tot].v);            ++tot;        }    }    while(m--){        scanf("%d%d%d%d",&x,&A,&B,&C);        A%=C;B%=C;        k=(A*pre%C+B)%C+1;        k=min(k,tr[root[x]].sum);        pre=query(root[x],1,a[0],k);        printf("%lld\n",pre);    }    return 0;}