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

蔚落 2023-06-01 06:08 9阅读 0赞

模板题...

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

就是细节烦...

1 #include<bits/stdc++.h>
     2 #define int long long
     3 #define mid (l+r>>1)
     4 #define writeln(x)  write(x),puts("")
     5 #define writep(x)   write(x),putchar(' ')
     6 using namespace std;
     7 inline int read(){
     8     int ans=0,f=1;char chr=getchar();
     9     while(!isdigit(chr)){
        if(chr=='-') f=-1;chr=getchar();}
    10     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    11     return ans*f;
    12 }void write(int x){
    13     if(x<0) putchar('-'),x=-x;
    14     if(x>9) write(x/10);
    15     putchar(x%10+'0');
    16 }const int M = 2e5+5; 
    17 int rt[M*20],s[M*20],ls[M*20],rs[M*20],cnt[M*20],n,m,lst,x,y,k,a[M],b[M],T;
    18 vector<int> aa[M],bb[M];
    19 void Update(int &x,int y,int l,int r,int p,int opt){
    20     x=++T;ls[x]=ls[y],rs[x]=rs[y],s[x]=s[y]+opt*b[p],cnt[x]=cnt[y]+opt;
    21     if(l==r) return;
    22     if(p<=mid)    Update(ls[x],ls[x],l,mid,p,opt);
    23     else         Update(rs[x],rs[x],mid+1,r,p,opt);
    24 }
    25 int Query(int x,int l,int r,int k){
    26     if(l==r) return s[x]/cnt[x]*k;
    27     int t=cnt[ls[x]];
    28     if(k<=t) return Query(ls[x],l,mid,k);
    29     return Query(rs[x],mid+1,r,k-t)+s[ls[x]];
    30 }
    31 signed main(){
    32     n=read(),m=read();
    33     for(int i=1,x,y,z;i<=n;i++){
    34         x=read(),y=read();a[i]=b[i]=read();
    35         aa[x].push_back(i),bb[y+1].push_back(i);
    36     }sort(b+1,b+n+1);int len=unique(b+1,b+n+1)-b-1;
    37     for(int i=1,pos;i<=m;i++){
    38         rt[i]=rt[i-1];
    39         for(int j=0;j<aa[i].size();j++){
    40             pos=lower_bound(b+1,b+len+1,a[aa[i][j]])-b;
    41             Update(rt[i],rt[i],1,len,pos,1);
    42         }
    43         for(int j=0;j<bb[i].size();j++){
    44             pos=lower_bound(b+1,b+len+1,a[bb[i][j]])-b;
    45             Update(rt[i],rt[i],1,len,pos,-1);
    46         }
    47     }lst=1;
    48     while(m--){
    49         int x=read(),y=read(),z=read(),w=read();
    50         k=(lst*y+z)%w+1;
    51         if(k>cnt[rt[x]]) writeln(lst=s[rt[x]]);
    52         else writeln(lst=Query(rt[x],1,len,k));
    53     }return 0;
    54 }

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

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

贴一下暴力代码：

#include<bits/stdc++.h>
    #define re register int
    using namespace std;
    inline int read(){
        int ans=0,f=1;char chr=getchar();
        while(!isdigit(chr)){
        if(chr=='-') f=-1;chr=getchar();}
        while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
        return ans*f;
    }const int N=1e5+10;
    struct P{
        int s,e,p;}a[N];
    int n,m,sum;long long ans=1;
    inline bool cmp(const P&a,const P&b){
        return a.p<b.p;}
    int main(){
        n=read(),m=read();
        for(int i=1;i<=n;i++) a[i].s=read(),a[i].e=read(),a[i].p=read();
        sort(a+1,a+n+1,cmp);re x,q,w,e,k;
        while(m--){
            x=read(),q=read(),w=read(),e=read();
            k=(1ll*q*ans%e+w)%e+1;ans=sum=0;
            for(re i=1;i<=n&&sum<k;++i)
                if(a[i].s<=x&&x<=a[i].e)ans+=a[i].p,++sum;
            printf("%lld\n",ans);
        }return 0;
    }

转载于:https://www.cnblogs.com/zhenglw/p/11259460.html