首页 > 代码库 > 【BZOJ1901】Dynamic Rankings [整体二分]
【BZOJ1901】Dynamic Rankings [整体二分]
Dynamic Rankings
Time Limit: 10 Sec Memory Limit: 128 MB[Submit][Status][Discuss]
Description
给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。
Input
第一行有两个正整数
分别表示序列的长度和指令的个数。第二行有n个数，表示a[1],a[2]……a[n]。
接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。
Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。
C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。
Output
Sample Input
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
6
HINT
m,n≤10000 , 0≤ai≤1e9。
Main idea
询问区间中第k小的数是多少，需要支持单点修改点的权值。
Source
我们看到这道题，发现对于一个询问应该是可以二分查找答案的，那么我们从整体二分的角度来思考。
我们发现，如果没有修改的话，显然很简单，直接整体二分将所有询问一起操作即可。
但是我们有操作，那应该怎么办呢？
我们对于每一次修改，记录一下原来的值，简单来说，就是对于每一次操作，记录一下若opt=1，则表示这个点在这个状态的值；若opt=3，则表示这是一个询问，
我们对于修改来说，新增一个opt=2，表示在修改之前的值。也就是说，我们在执行一个区间的操作时，如果发现一个opt=2，那么之前一定有一个一样的值的opt为1，并且其已经对答案造成影响，现在那个元素已经被修改了，就要相应地减去它之前对答案的影响，这样就完成了修改。
然后我们整体二分权值，像静态查询kth那样修改一下即可。思路一气呵成 \(≧▽≦)/
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 #include<map> 9 using namespace std; 10 11 const int ONE=30005; 12 const int INF=1e9+1; 13 14 int n,m; 15 int x,y,k; 16 char ch[3]; 17 int cnt,Num; 18 int a[ONE],record[ONE]; 19 int Ans[ONE]; 20 21 struct power 22 { 23 int opt,cnt; 24 int l,r,k; 25 int pos,value; 26 int cur; 27 }oper[ONE],qL[ONE],qR[ONE]; 28 29 int get() 30 { 31 int res=1,Q=1;char c; 32 while( (c=getchar())<48 || c>57 ) 33 if(c==‘-‘)Q=-1; 34 res=c-48; 35 while( (c=getchar())>=48 && c<=57 ) 36 res=res*10+c-48; 37 return res*Q; 38 } 39 40 namespace Bit 41 { 42 struct power 43 { 44 int value; 45 }Node[ONE]; 46 47 int lowbit(int i) 48 { 49 return i&-i; 50 } 51 52 void Update(int R,int x) 53 { 54 for(int i=R;i<=n;i+=lowbit(i)) 55 Node[i].value+=x; 56 } 57 58 int Query(int R) 59 { 60 int res=0; 61 for(int i=R;i>=1;i-=lowbit(i)) 62 res+=Node[i].value; 63 return res; 64 } 65 } 66 67 void Solve(int l,int r,int L,int R) 68 { 69 if(l>r) return; 70 if(L==R) 71 { 72 for(int i=l;i<=r;i++) 73 if(oper[i].opt==3) 74 Ans[oper[i].cnt] = L; 75 return; 76 } 77 78 int M=(L+R)>>1; 79 for(int i=l;i<=r;i++) 80 { 81 if(oper[i].opt==1 && oper[i].value<=M) 82 Bit::Update(oper[i].pos,1); 83 if(oper[i].opt==2 && oper[i].value<=M) 84 Bit::Update(oper[i].pos,-1); 85 if(oper[i].opt==3) 86 record[i]=Bit::Query(oper[i].r) - Bit::Query(oper[i].l-1); 87 } 88 89 for(int i=l;i<=r;i++) 90 { 91 if(oper[i].opt==1 && oper[i].value<=M) 92 Bit::Update(oper[i].pos,-1); 93 if(oper[i].opt==2 && oper[i].value<=M) 94 Bit::Update(oper[i].pos,1); 95 } 96 97 int l_num=0,r_num=0; 98 for(int i=l;i<=r;i++) 99 {100 if(oper[i].opt!=3)101 {102 if(oper[i].value <= M)103 qL[++l_num]=oper[i];104 else105 qR[++r_num]=oper[i];106 }107 else108 {109 if(oper[i].cur + record[i] >= oper[i].k)110 qL[++l_num]=oper[i];111 else112 {113 qR[++r_num]=oper[i];114 qR[r_num].cur+=record[i];115 }116 }117 }118 119 int t=l;120 for(int i=1;i<=l_num;i++) oper[t++]=qL[i];121 for(int i=1;i<=r_num;i++) oper[t++]=qR[i];122 123 124 Solve(l,l+l_num-1,L,M);125 Solve(l+l_num,r,M+1,R);126 } 127 128 int main()129 {130 n=get(); m=get();131 for(int i=1;i<=n;i++)132 {133 a[i]=get();134 oper[++cnt].opt=1; oper[cnt].pos=i; oper[cnt].value=http://www.mamicode.com/a[i];135 }136 137 for(int i=1;i<=m;i++)138 {139 scanf("%s",ch);140 if(ch[0]==‘Q‘)141 {142 x=get(); y=get(); k=get();143 oper[++cnt].opt=3; oper[cnt].l=x; oper[cnt].r=y; oper[cnt].k=k;144 oper[cnt].cnt=++Num;145 }146 else147 {148 x=get(); y=get();149 oper[++cnt].opt=2; oper[cnt].pos=x; oper[cnt].value=http://www.mamicode.com/a[x];150 oper[++cnt].opt=1; oper[cnt].pos=x; oper[cnt].value=http://www.mamicode.com/y;151 a[x]=y;152 }153 }154 155 Solve(1,cnt,0,INF);156 157 for(int i=1;i<=Num;i++)158 printf("%d\n",Ans[i]);159 }
【BZOJ1901】Dynamic Rankings [整体二分]