首页 > 代码库 > [bzoj3932][CQOI2015]任务查询系统-题解[主席树][权值线段树]
[bzoj3932][CQOI2015]任务查询系统-题解[主席树][权值线段树]
Description
最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的
任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行
），其优先级为Pi。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向
查询系统询问，第Xi秒正在运行的任务中，优先级最小的Ki个任务（即将任务按照优先级从小到大排序后取前Ki个
）的优先级之和是多少。特别的，如果Ki大于第Xi秒正在运行的任务总数，则直接回答第Xi秒正在运行的任务优先
级之和。上述所有参数均为整数，时间的范围在1到n之间（包含1和n）。
Input
输入文件第一行包含两个空格分开的正整数m和n，分别表示任务总数和时间范围。接下来m行，每行包含三个空格
分开的正整数Si、Ei和Pi(Si≤Ei)，描述一个任务。接下来n行，每行包含四个空格分开的整数Xi、Ai、Bi和Ci，
描述一次查询。查询的参数Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci计算得到。其中Pre表示上一次查询的结果，
对于第一次查询，Pre=1。
Output
输出共n行，每行一个整数，表示查询结果。
Sample Input
4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3
Sample Output
2
8
11
8
11
HINT
样例解释
K1 = (1*1+3)%2+1 = 1
K2 = (1*2+3)%4+1 = 2
K3 = (2*8+4)%3+1 = 3
对于100%的数据，1≤m,n,Si,Ei,Ci≤100000，0≤Ai,Bi≤100000，1≤Pi≤10000000，Xi为1到n的一个排列
正在学主席树。。听说这个题是个模板题就跑去做了。。
如果你不知道什么是主席树的话建议出门左转去学。。
对于每一个时间点我们建一个版本的权值线段树，每个线段树记录当前结点的任务数与这个结点的任务优先级之和。
一个任务从i到j的话就给第i个版本++，第j+1个版本--；
但是我们需要考虑几个事情
1.pi太大，需要离散化，这是很显然的。
2.修改了第x个版本的话后面所有版本都需要更改。
对于1我的方法是把所有优先级先序排序去重然后依次放到数组里，因为排了序了所以它们的大小关系不会改变，然后通过二分找到离散化以后的值（但是被dalao嘲讽了）
对于2我的方法是把所有操作按时间点大小先序排序，然后依次进行操作，如果当前的操作点比目前建的树要大那就开到那个时间点
这个意思
1 for(int i=1;i<=操作数;++i)2 {3 while(已经建了p个<a[i].time){建树(++p);}4 操作：加或减5 }
因为我之后建的树会复制前面的树的值，而前面的树的操作都是已经做完了的，然后这个操作是2*m+n。
当然这个也被dalao嘲讽了。。
然后有一个东西要考虑（我就是错了这个）
就是你查询到叶子结点的时候，它的任务数可能会比你剩下要查的个数要大，这样你就不需要取走全部了。。似乎是一个很显然的事情但我当时做却没想到。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #define N (100000+5) 7 #define ll long long 8 using namespace std; 9 inline ll read() 10 { 11 char ch=getchar();ll kin=1,gi=0; 12 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)kin=-1;ch=getchar();} 13 while(ch>=‘0‘&&ch<=‘9‘){gi=gi*10+ch-48;ch=getchar();} 14 return kin*gi; 15 } 16 struct tree 17 { 18 ll num; 19 ll simple; 20 ll son[2]; 21 ll l,r,fl; 22 }d[5000005]; 23 struct naive 24 { 25 ll nic; 26 ll st; 27 bool fl; 28 }ni[N*2]; 29 bool cmp(naive x,naive y) 30 { 31 return x.st<y.st; 32 } 33 ll n,m,siz,rt[N]; 34 ll sot[N],trl[N],kiz,fis,trik; 35 ll pre=1,lis[N],ra,rig; 36 void make(ll,ll,bool); 37 ll query(ll,ll); 38 void build(ll,ll,ll); 39 void rut(ll); 40 ll mmid(ll x) 41 { 42 ll l=1,r=kiz,res=0; 43 while(l<=r) 44 { 45 ll mid=(l+r)>>1; 46 if(trl[mid]<=x){l=mid+1;res=mid;} 47 else r=mid-1; 48 } 49 return res; 50 } 51 int main() 52 { 53 m=read();n=read(); 54 for(ll i=1;i<=m;++i) 55 { 56 57 ni[++trik].st=read();ni[trik].fl=1; 58 ni[++trik].st=read()+1;ni[trik].fl=0; 59 ni[trik-1].nic=ni[trik].nic=read(); 60 sot[i]=ni[trik].nic; 61 } 62 sort(sot+1,sot+m+1); 63 sort(ni+1,ni+trik+1,cmp); 64 for(ll i=1;i<=m;++i)if(sot[i]!=sot[i-1])trl[++kiz]=sot[i]; 65 for(ll i=1;i<=trik;++i) 66 { 67 if(ni[i].st>n)break; 68 while(fis<ni[i].st){rut(++fis);} 69 ll rik=mmid(ni[i].nic); 70 make(ni[i].st,rik,ni[i].fl); 71 } 72 while(fis<n){rut(++fis);} 73 for(ll i=1;i<=n;++i) 74 { 75 ll sec=read(); 76 ll a,b,c,k; 77 a=read();b=read();c=read(); 78 k=(a*pre+b)%c+1; 79 printf("%lld\n",pre=query(sec,k)); 80 } 81 return 0; 82 } 83 ll query(ll x,ll y) 84 { 85 ll nw=rt[x],res=0; 86 y=min(y,d[nw].simple); 87 while(1) 88 { 89 if(y==0)break; 90 if(d[nw].l==d[nw].r&&d[nw].simple>y){res+=trl[d[nw].l]*y;break;} 91 if(d[nw].simple<=y){res+=d[nw].num;break;} 92 if(d[d[nw].son[0]].simple<=y) y-=d[d[nw].son[0]].simple,res+=d[d[nw].son[0]].num,nw=d[nw].son[1]; 93 else nw=d[nw].son[0]; 94 } 95 return res; 96 } 97 void make(ll x,ll num,bool p) 98 { 99 ll nw=rt[x];bool f;100 while(d[nw].l!=d[nw].r)101 {102 if(p)103 {d[nw].num+=trl[num];d[nw].simple++;}104 else105 {d[nw].num-=trl[num];d[nw].simple--;}106 f=(num>(d[nw].l+d[nw].r)>>1);107 if(d[d[nw].son[f]].fl!=x)108 {109 d[++siz]=d[d[nw].son[f]];110 d[nw].son[f]=siz;111 d[siz].fl=x;112 }113 nw=d[nw].son[f];114 }115 if(p)116 {d[nw].num+=trl[num];d[nw].simple++;}117 else118 {d[nw].num-=trl[num];d[nw].simple--;}119 }120 void rut(ll p)121 {122 ll x;123 x=rt[p]=++siz;124 d[x].l=1;d[x].r=kiz;d[x].fl=1;125 if(x>1)126 {127 d[rt[p]]=d[rt[p-1]];128 d[rt[p]].son[0]=d[rt[p-1]].son[0];129 d[rt[p]].son[1]=d[rt[p-1]].son[1];130 }131 else132 {133 d[x].son[0]=++siz;134 build(d[x].son[0],1,(kiz+1)>>1);135 d[x].son[1]=++siz;136 build(d[x].son[1],((kiz+1)>>1)+1,kiz);137 }138 }139 void build(ll x,ll l,ll r)140 {141 d[x].l=l;d[x].r=r;d[x].fl=1;142 if(l!=r)143 {144 d[x].son[0]=++siz;145 build(siz,l,(l+r)>>1);146 d[x].son[1]=++siz;147 build(siz,((l+r)>>1)+1,r);148 }149 }
[bzoj3932][CQOI2015]任务查询系统-题解[主席树][权值线段树]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。