[bzoj3932]任务查询系统

 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<=@H_241_47@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,&@H_241_47@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 }