bzoj3932[CQOI2015]任务查询系统

时间:2021-03-31 18:51:34

bzoj3932[CQOI2015]任务查询系统

题意:

m个任务,任务(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei秒后结束,优先级为Pi。n个询问,每次询问第Xi秒正在运行的任务中,优先级最小的Ki个任务的优先级之和是多少。若Ki大于第Xi秒正在运行的任务总数,输出第Xi秒任务优先级之和。m,n≤100000,强制在线。

题解:

第一次写主席树……(因为没彻底理解被yyl大爷d:你根本不理解主席树)主席树本质上就是权值线段树+重用节点。

反映在本题中,就是给每个时间点建一棵权值线段树,但这样会MLE,所以我们先将所有任务拆成“Si到n时间点的权值+Pi”和“Ei+1到n时间点的权值+(-Pi),然后按插入的时间点排序,在每个插入操作前,将之前上一次操作得到的权值线段树的根节点指针复制过来,然后插入时只新开节点记录被修改后的节点,因为一次插入只会影响log2n个节点,所以总空间复杂度为O(nlog2n),同时因为相隔两个插入时间点之间的时间点只要复制一个指针就行,每次插入时间复杂度为log2n,故时间复杂度为O(nlog2n)。本题可以不离散化,但我比较怂所以还是离散了一下省空间。

代码:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 400000
 7 #define ll long long
 8 using namespace std;
 9 
10 struct opt{int a,b,c,id;}; opt opts[maxn*2];
11 bool cmp1(opt a,opt b){return a.b<b.b;}
12 bool cmp2(opt a,opt b){return a.a<b.a;}
13 int lc[20*maxn],rc[20*maxn],rt[maxn],sz[20*maxn],n,m,valn,tot,optn;
14 ll sm[20*maxn];
15 void build(int &x,int l,int r){
16     x=++tot; lc[x]=rc[x]=sz[x]=sm[x]=0; if(l==r)return;
17     int mid=(l+r)>>1; build(lc[x],l,mid); build(rc[x],mid+1,r);
18 }
19 void ins(int &x,int l,int r,int y,int z1,int z2){
20     tot++; sm[tot]=sm[x]+(ll)(z1*z2); sz[tot]=sz[x]+z2;
21     lc[tot]=lc[x]; rc[tot]=rc[x]; x=tot; if(l==r)return; int mid=(l+r)>>1;
22     if(y<=mid)ins(lc[x],l,mid,y,z1,z2);else ins(rc[x],mid+1,r,y,z1,z2);
23 }
24 ll query(int x,ll k){
25     ll q=0; int y=x;
26     while(1){
27         if(k>=sz[y]){q+=sm[y]; return q;} if(!lc[y]&&!rc[y]){q+=sm[y]/sz[y]*k; return q;}
28         if(k==sz[lc[y]]){q+=sm[lc[y]]; return q;}
29         if(k<sz[lc[y]])y=lc[y];else k-=sz[lc[y]],q+=sm[lc[y]],y=rc[y];
30     }
31 }
32 int main(){
33     scanf("%d%d",&m,&n); optn=0;
34     inc(i,1,m){
35         int a,b,c; scanf("%d%d%d",&a,&b,&c);
36         opts[++optn]=(opt){a,c,1,0}; if(b!=n)opts[++optn]=(opt){b+1,c,-1,0};
37     }
38     sort(opts+1,opts+1+optn,cmp1); valn=1; opts[1].id=1;
39     inc(i,2,optn){if(opts[i].b!=opts[i-1].b)opts[i].id=++valn;else opts[i].id=valn;}
40     tot=0; build(rt[0],1,valn); sort(opts+1,opts+1+optn,cmp2); opts[optn+1].a=n;
41     for(int i=1;i<=opts[1].a&&i<=n;i++)rt[i]=rt[i-1];
42     inc(i,1,optn){
43         ins(rt[opts[i].a],1,valn,opts[i].id,opts[i].b,opts[i].c);
44         for(int j=opts[i].a+1;j<=opts[i+1].a&&j<=n;j++)rt[j]=rt[j-1];
45     }
46     ll last=1;
47     inc(i,1,n){
48         int a;ll b,c,d; scanf("%d%lld%lld%lld",&a,&b,&c,&d);
49         last=query(rt[a],1+(b*last+c)%d);
50         printf("%lld\n",last);
51     }
52     return 0;
53 }

 

20160516