【主席树】 [CQOI2015]任务查询系统

模板题...

差分，然后用主席树维护时间点上的优先值和就好了

就是细节烦...

 #include<bits/stdc++.h>

 #define int long long

 #define mid (l+r>>1)

 #define writeln(x)  write(x),puts("")

 #define writep(x)   write(x),putchar(' ')

 using namespace std;

 inline int read(){

     int ans=,f=;char chr=getchar();

     while(!isdigit(chr)){if(chr=='-') f=-;chr=getchar();}

     while(isdigit(chr)){ans=(ans<<)+(ans<<)+chr-;chr=getchar();}

     return ans*f;

 }void write(int x){

     if(x<) putchar('-'),x=-x;

     if(x>) write(x/);

     putchar(x%+'');

 }const int M = 2e5+;

 int rt[M*],s[M*],ls[M*],rs[M*],cnt[M*],n,m,lst,x,y,k,a[M],b[M],T;

 vector<int> aa[M],bb[M];

 void Update(int &x,int y,int l,int r,int p,int opt){

     x=++T;ls[x]=ls[y],rs[x]=rs[y],s[x]=s[y]+opt*b[p],cnt[x]=cnt[y]+opt;

     if(l==r) return;

     if(p<=mid)    Update(ls[x],ls[x],l,mid,p,opt);

     else         Update(rs[x],rs[x],mid+,r,p,opt);

 }

 int Query(int x,int l,int r,int k){

     if(l==r) return s[x]/cnt[x]*k;

     int t=cnt[ls[x]];

     if(k<=t) return Query(ls[x],l,mid,k);

     return Query(rs[x],mid+,r,k-t)+s[ls[x]];

 }

 signed main(){

     n=read(),m=read();

     for(int i=,x,y,z;i<=n;i++){

         x=read(),y=read();a[i]=b[i]=read();

         aa[x].push_back(i),bb[y+].push_back(i);

     }sort(b+,b+n+);int len=unique(b+,b+n+)-b-;

     for(int i=,pos;i<=m;i++){

         rt[i]=rt[i-];

         for(int j=;j<aa[i].size();j++){

             pos=lower_bound(b+,b+len+,a[aa[i][j]])-b;

             Update(rt[i],rt[i],,len,pos,);

         }

         for(int j=;j<bb[i].size();j++){

             pos=lower_bound(b+,b+len+,a[bb[i][j]])-b;

             Update(rt[i],rt[i],,len,pos,-);

         }

     }lst=;

     while(m--){

         int x=read(),y=read(),z=read(),w=read();

         k=(lst*y+z)%w+;

         if(k>cnt[rt[x]]) writeln(lst=s[rt[x]]);

         else writeln(lst=Query(rt[x],,len,k));

     }return ;

 }

然而悲伤的是：洛谷上暴力跑的最快惹qaq，排行榜第一页全是暴力,转行打暴力吧

upd:经测试bzoj上暴力跑得也贼快，上了第一页

贴一下暴力代码：

#include<bits/stdc++.h>

#define re register int

using namespace std;

inline int read(){

    int ans=,f=;char chr=getchar();

    while(!isdigit(chr)){if(chr=='-') f=-;chr=getchar();}

    while(isdigit(chr)){ans=(ans<<)+(ans<<)+chr-;chr=getchar();}

    return ans*f;

}const int N=1e5+;

struct P{int s,e,p;}a[N];

int n,m,sum;long long ans=;

inline bool cmp(const P&a,const P&b){return a.p<b.p;}

int main(){

    n=read(),m=read();

    for(int i=;i<=n;i++) a[i].s=read(),a[i].e=read(),a[i].p=read();

    sort(a+,a+n+,cmp);re x,q,w,e,k;

    while(m--){

        x=read(),q=read(),w=read(),e=read();

        k=(1ll*q*ans%e+w)%e+;ans=sum=;

        for(re i=;i<=n&&sum<k;++i)

            if(a[i].s<=x&&x<=a[i].e)ans+=a[i].p,++sum;

        printf("%lld\n",ans);

    }return ;

}