记录下自己写错的地方吧
1. 区间可能有重复
2. 没有出现的坐标也要计入version （因为询问里可能会有）
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int n,m,t1,t2,t3,t4,_s[500005],_e[500005],_p[500005],ind,ch[5000005][2]; 5 int a[5000005],root[5000005],rcnt,ver[500005],maxn,_list[5000005],flag; 6 long long s[5000005]; 7 8 struct Item { 9 int pos,typ,key; 10 void init(int a,int b,int c) { 11 pos=a; typ=b; key=c; 12 } 13 } item[5000005]; 14 15 int cmp(const Item &a, const Item &b) { 16 return a.pos<b.pos; 17 } 18 19 void modify(int sp,int &p,int l,int r,int pos,int val,int k) { 20 if(p==0||p==sp) p=++ind, ch[p][0]=ch[sp][0], ch[p][1]=ch[sp][1], a[p]=a[sp], s[p]=s[sp]; 21 if(l==r) { 22 if(k==1) a[p]+=1, s[p]+=(long long)_list[val]; 23 else a[p]-=1, s[p]-=(long long)_list[val]; 24 } 25 else{ 26 if(val<=(l+r)/2) modify(ch[sp][0],ch[p][0],l,(l+r)/2,pos,val,k); 27 else modify(ch[sp][1],ch[p][1],(l+r)/2+1,r,pos,val,k); 28 a[p]=a[ch[p][0]]+a[ch[p][1]]; 29 s[p]=s[ch[p][0]]+s[ch[p][1]]; 30 } 31 } 32 33 int queryA(int p,int l,int r,int ql,int qr) { 34 if(l>qr||r<ql) return 0; 35 if(l>=ql && r<=qr) return a[p]; 36 return queryA(ch[p][0],l,(l+r)/2,ql,qr)+queryA(ch[p][1],(l+r)/2+1,r,ql,qr); 37 } 38 39 long long queryS(int p,int l,int r,int ql,int qr) { 40 if(l>qr||r<ql) return 0; 41 if(l>=ql && r<=qr) return s[p]; 42 return queryS(ch[p][0],l,(l+r)/2,ql,qr)+queryS(ch[p][1],(l+r)/2+1,r,ql,qr); 43 } 44 45 int kth(int p,int l,int r,int k) { 46 if(l==r) { 47 if(a[p]) flag=(k-a[p])*(s[p]/a[p]); 48 else flag=0; 49 return l; 50 } 51 if(k<=a[ch[p][0]]) return kth(ch[p][0],l,(l+r)/2,k); 52 else return kth(ch[p][1],(l+r)/2+1,r,k-a[ch[p][0]]); 53 } 54 55 int main(){ 56 long long pre=1; 57 ios::sync_with_stdio(false); 58 cin>>n>>m; maxn=n; 59 for(int i=1;i<=n;i++) cin>>_s[i]>>_e[i]>>_p[i], 60 item[i*2-1].init(_s[i],1,_p[i]), 61 item[i*2].init(_e[i]+1,0,_p[i]), 62 _list[i]=_p[i]; 63 sort(item+1,item+2*n+1,cmp); 64 sort(_list+1,_list+n+1); 65 unique(_list+1,_list+n+1); 66 for(int i=1;i<=2*n;i++) { 67 if(item[i].pos-item[i-1].pos) for(int j=item[i-1].pos;j<item[i].pos;j++) ver[j]=i-1; 68 modify(root[i-1],root[i],1,maxn,item[i].pos,lower_bound(_list+1,_list+n+1,item[i].key)-_list,item[i].typ?1:-1); 69 } 70 ver[item[2*n].pos]=2*n; 71 for(int i=1;i<=m;i++) { 72 cin>>t1>>t2>>t3>>t4; 73 t2=1+((long long)t2*(long long)pre+(long long)t3)%(long long)t4; 74 t3=kth(root[ver[t1]],1,maxn,t2), 75 cout<<(pre=(queryS(root[ver[t1]],1,maxn,1,t3)+flag))<<endl; 76 } 77 }