[bzoj3932]任务查询系统

概述每一个区间相当于对[x,n]新增一个p，对[y+1,n]减少一个p，那么建立一棵可持久化线段树，然后对于修改第p个位置，同时统计出子树的点数和所有的和，类似于二分确定即可。 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 #define ll long long 5 #define mid

每一个区间相当于对[x,n]新增一个p，对[y+1,n]减少一个p，那么建立一棵可持久化线段树，然后对于修改第p个位置，同时统计出子树的点数和所有的和，类似于二分确定即可。

 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 #define ll long long 5 #define mID (l+r>>1) 6 int V,n,m,x,y,z,p1,p2,p3,ID[N],r[N],a[N],b[N],ls[N*30],rs[N*30],sz[N*30]; 7 ll ans,f[N*30]; 8 bool cmp(int x,int y){ 9     return a[x]<a[y];10 }11 voID up(int k){12     f[k]=f[ls[k]]+f[rs[k]];13     sz[k]=sz[ls[k]]+sz[rs[k]];14 }15 voID update(int k1,int &k2,int l,int r,int x,int y,int z){16     k2=++V;17     if (l==r){18         sz[k2]=sz[k1]+z;19         f[k2]=f[k1]+y*z;20         return;21     }22     ls[k2]=ls[k1];23     rs[k2]=rs[k1];24     if (y<=mID)update(ls[k1],ls[k2],l,mID,z);25     else update(rs[k1],rs[k2],mID+1,r,z);26     up(k2);27 }28 ll query(int k,int x){29     if (l==r)return 1LL*l*x;30     if (x<=sz[ls[k]])return query(ls[k],x);31     return query(rs[k],mID+1,x-sz[ls[k]])+f[ls[k]];32 }33 int main(){34     scanf("%d%d",&n,&m);35     for(int i=1;i<=n;i++){36         scanf("%d%d%d",&x,&y,&z);37         a[2*i-1]=x;38         b[2*i-1]=z;39         a[2*i]=y+1;40         b[2*i]=-z;41     }42     n*=2;43     for(int i=1;i<=n;i++)ID[i]=i;44     sort(ID+1,ID+n+1,cmp);45     for(int i=1;i<=n;i++)r[i]=a[ID[i]];46     memcpy(a,sizeof(a));47     for(int i=1;i<=n;i++)r[i]=b[ID[i]];48     memcpy(b,sizeof(b));49     for(int i=1;i<=n;i++)update(r[i-1],r[i],1,10000000,a[i],abs(b[i]),abs(b[i])/b[i]);50     ans=1;51     for(int i=1;i<=m;i++){52         scanf("%d%d%d%d",&p1,&p2,&p3);53         x=upper_bound(a+1,a+n+1,x)-a-1;54         y=1+(p1*ans+p2)%p3;55         if (sz[r[x]]<=y)printf("%lld\n",ans=f[r[x]]);56         else printf("%lld\n",ans=query(r[x],10000000,y));57     }58 }

VIEw Code 总结

以上是内存溢出为你收集整理的[bzoj3932]任务查询系统全部内容，希望文章能够帮你解决[bzoj3932]任务查询系统所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。