最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行），其优先级为Pi。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向查询系统询问，第Xi秒正在运行的任务中，优先级最小的Ki个任务（即将任务按照优先级从小到大排序后取前Ki个）的优先级之和是多少。特别的，如果Ki大于第Xi秒正在运行的任务总数，则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数，时间的范围在1到n之间（包含1和n）。
--by 洛谷；
https://daniu.luogu.org/problem/show?pid=3168
主席树（可持久化线段树）
考虑离散优先级（即权值）；
以时间为序列，维护主席树（主席树的详解见这个）
然后把询问处理为在S处加入，在E+1处删除之
跑就好了；
注意内存池开到4e6以上（我会说我因为这个卡了一个月？？）
代码如下：
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 struct ss{ 5 long long tim,val,p; 6 }x[200001]; 7 long long a[200001]; 8 struct pool{ 9 int l,r; 10 long long sum,size; 11 }data[4000050]; 12 int n,m,tot; 13 int fa[100001]; 14 long long A,B,C,pre; 15 16 bool cmpt(ss x,ss y){ 17 return x.tim<y.tim; 18 } 19 bool cmpv(ss x,ss y){ 20 return x.val<y.val; 21 } 22 23 void add(int ,int ,int ,int ); 24 long long find(int ,int ,int ,long long ); 25 26 int main() 27 { 28 int i,j,k,l,o; 29 scanf("%d%d",&m,&n); 30 for(i=1;i<=m;i++){ 31 scanf("%d%d%d",&j,&k,&l); 32 x[(i<<1)-1].tim=j;x[(i<<1)-1].val=l; 33 x[i<<1].tim=k+1;x[i<<1].val=l; 34 x[i<<1].p=-1;x[(i<<1)-1].p=1; 35 } 36 sort(x+1,x+2*m+1,cmpv); 37 j=0; 38 for(i=1;i<=2*m;i++){ 39 if(x[i].val!=a[j]){ 40 a[++j]=x[i].val; 41 x[i].val=j; 42 } 43 x[i].val=j; 44 } 45 k=j; 46 sort(x+1,x+2*m+1,cmpt); 47 j=1; 48 for(i=1;i<=n;i++){ 49 fa[i]=++tot; 50 data[fa[i]]=data[fa[i-1]]; 51 while(x[j].tim==i) 52 add(fa[i],j,1,k),j++; 53 } 54 pre=1; 55 for(i=1;i<=n;i++){ 56 scanf("%d%lld%lld%lld",&j,&A,&B,&C); 57 pre=find(fa[j],1,k,(A*pre+B)%C+1); 58 printf("%lld ",pre); 59 } 60 return 0; 61 } 62 63 void add(int now,int ma,int l,int r) 64 { 65 data[now].size+=x[ma].p; 66 data[now].sum+=a[x[ma].val]*x[ma].p; 67 if(l>=r) return; 68 int mid=(l+r)>>1; 69 if(x[ma].val<=mid){ 70 data[++tot]=data[data[now].l]; 71 data[now].l=tot; 72 add(data[now].l,ma,l,mid); 73 } 74 else{ 75 data[++tot]=data[data[now].r]; 76 data[now].r=tot; 77 add(data[now].r,ma,mid+1,r); 78 } 79 } 80 81 long long find(int now,int l,int r,long long ma) 82 { 83 long long sum; 84 if(ma==0)return 0; 85 if(ma>=data[now].size||l==r){ 86 sum=data[now].sum; 87 if(l==r&&data[now].size>ma)sum=(sum*ma)/data[now].size; 88 return sum; 89 } 90 int mid=(l+r)>>1; 91 if(ma<=data[data[now].l].size) 92 return find(data[now].l,l,mid,ma); 93 else 94 return data[data[now].l].sum+find(data[now].r,mid+1,r,ma-data[data[now].l].size); 95 }
祝AC哟！