现在有一群任务,每个任务都有开始和结束的时间和一个优先级,给你所有任务的开始结束时间和优先级,问你在某个时间点优先级最小的k个的优先级的和是多少.
普通的主席树是单点修改 区间查询 这题正好相反
可以用差分数组来做 区间查询改为1-i的前缀和
注意copy结点的方式 不能简单的复制T 还有son t num
重复累加的操作 要写成T[i] T[i] 而不是 T[i-1] T[i]
主席树的范围只和放入的数据的离散化下标有关 和历史版本号没有任何关系
这题的时间为历史版本号 和主席树的范围没有关系
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) typedef pair<int,int>pii; ////////////////////////////////// const int N=2e6+10; int son[N<<5][2]; ll t[N<<5],num[N<<5]; int T[N<<5],ncnt; struct node {int x,v;ll flag; } a[N]; int n,m; ll b[N]; void build(int l,int r,int &pos) { pos=++ncnt; if(l==r)return ; int m=l+r>>1; build(l,m,son[pos][0]); build(m+1,r,son[pos][1]); } void up(int x,int flag,int l,int r,int pre,int &pos) { pos=++ncnt; son[pos][0]=son[pre][0]; son[pos][1]=son[pre][1]; t[pos]=t[pre]+flag*b[x]; num[pos]=num[pre]+flag; if(l==r){return ;} int m=l+r>>1; if(x<=m)up(x,flag,l,m,son[pos][0],son[pos][0]); else up(x,flag,m+1,r,son[pos][1],son[pos][1]); } int qsum(int k,int l,int r,int pos) { if(l==r)return min(k*t[pos]/num[pos],t[pos]); if(num[pos]<=k)return t[pos]; int m=l+r>>1; if(num[son[pos][0]]>=k)return qsum(k,l,m,son[pos][0]); else return t[son[pos][0]]+qsum(k-num[son[pos][0]],m+1,r,son[pos][1]); } void cpy(int &pos,int pre) { pos=++ncnt; son[pos][0]=son[pre][0]; son[pos][1]=son[pre][1]; t[pos]=t[pre]; num[pos]=num[pre]; } int main() { scanf("%d%d",&n,&m); rep(i,1,n) { int x,y;ll z;scanf("%d%d%lld",&x,&y,&z); a[2*i-1]=(node){x,z,1}; a[2*i ]=(node){y+1,z,-1}; b[i]=z; } sort(b+1,b+1+n); int nn=unique(b+1,b+1+n)-b-1; sort(a+1,a+1+2*n,[](node a,node b){return a.x<b.x;} ); build(1,nn,T[0]); int pos=1; rep(i,1,m) { cpy(T[i],T[i-1]); while(pos<=2*n&&a[pos].x==i) { up(lower_bound(b+1,b+1+nn,a[pos].v)-b,a[pos].flag,1,nn,T[i],T[i]); pos++;//注意这里如果写成T[i-1],T[i] 就不能满足重复更新 } } ll ans=1,A,B,C,x,k; rep(j,1,m) { scanf("%lld%lld%lld%lld",&x,&A,&B,&C); k=1+(A*ans+B)%C; if(k>=num[T[x]]) ans=t[T[x]]; else ans=qsum((int)k,1,nn,T[x]); printf("%lld ",ans); } return 0; }