lg3168[求区间前k小的和] 发表于 2018-04-22 | 分类于 算法 , 树 , 主席树 | 阅读数 次 链接:lg3168[求区间前k小的和] 题解 显然对于区间优先级加k操作进行差分,对时间建主席树,维护优先级前缀和以及在这个优先级区间里的任务个数,更新就很简单了 ,查询类似查区间第k小. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=2e5+7;struct node{ int l,val,p; node(int l,int val,int p):l(l),val(val),p(p){} node(){}}e[N<<2];ll tr[N<<5],size[N<<5];int lson[N<<5],rson[N<<5],root[N],a[N],len,n,m,cnt;inline int cmpv(node x,node y){return x.val<y.val;}inline int cmpt(node x,node y){return x.l<y.l;}inline void update(int &o,int l,int r,int k,int p){ lson[++cnt]=lson[o];rson[cnt]=rson[o];tr[cnt]=tr[o];size[cnt]=size[o]; o=cnt;tr[o]+=a[k]*p;size[o]+=p; if(l==r)return; int mid=l+r>>1; if(k<=mid)update(lson[o],l,mid,k,p); else update(rson[o],mid+1,r,k,p);}inline ll query(int o,int l,int r,int k){ if(size[o]<=k)return tr[o]; if(l==r)return tr[o]/size[o]*k; int mid=l+r>>1; if(k<=size[lson[o]])return query(lson[o],l,mid,k); return tr[lson[o]]+query(rson[o],mid+1,r,k-size[lson[o]]);}inline void solve(){ scanf("%d%d",&n,&m); rep(i,1,n){ int a,b,c; scanf("%d%d%d",&a,&b,&c); e[(i<<1)-1]=node(a,c,1);e[i<<1]=node(b+1,c,-1); } sort(e+1,e+n*2+1,cmpv); rep(i,1,n*2){if(e[i].val!=a[len])a[++len]=e[i].val;e[i].val=len;} sort(e+1,e+n*2+1,cmpt); ll pre=1;int k=1; rep(i,1,m){ root[i]=root[i-1]; while(e[k].l==i)update(root[i],1,len,e[k].val,e[k].p),k++; } rep(i,1,m){ int x,A,B,c; scanf("%d%d%d%d",&x,&A,&B,&c); pre=(pre*A+B)%c+1; printf("%lld\n",pre=query(root[x],1,len,pre)); }}int main(){ solve(); return 0;}