1901: Zju2112 Dynamic RankingsTime Limit:?10 Sec??Memory Limit:?128 MBSubmit:?9543??Solved:?4004 [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继续回答上面的问题。Input第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。 分别表示序列的长度和指令的个数。 第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。 接下来的m行描述每条指令 每行的格式是下面两种格式中的一种。? Q i j k 或者 C i t? 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 m,n≤10000Output?对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。 Sample Input5 33 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3 Sample Output36 ? 带元素修改的区间第k大问题。? ? 这题的方法也有很多。?? 1.分块 2.整体二分 3.线段树套线段树 4.区间线段树套平衡树 5.权值线段树套平衡树? 6.替罪羊树套线段树 ? 附整体二分代码：?? 整体二分就是把修改操作看成是一个删除操作和一个添加操作，把这些操作和询问放在一起进行二分。? 
1 #include<bits/stdc .h>
2 using namespace std;
3 int const N=300000 10;
4 int const inf=1e9;
5 struct node{
6 int x,num;
7 bool operator < (const node &rhs) const{
8 return x<rhs.x;
9 }
10 }a[N];
11 struct query{
12 int x,num,opt,k,cnt,y,v;
13 }q[N],ta[N],tb[N];
14 int n,m,ans[N],c[N],sum,xa[N];
15 void update(int x,int v){
16 for(int i=x;i<=n;i =(i&-i))
17 c[i] =v;
18 }
19 int inline getsum(int x){
20 int s=0;
21 for(int i=x;i;i-=(i&-i))
22 s =c[i];
23 return s;
24 }
25 void calc(int l,int r,int ll,int mid){
26 int left=1,right=n;
27 while (left<right){
28 int Mid=(left right)/2;
29 if(a[Mid].x>=ll) right=Mid;
30 else left=Mid 1;
31 }
32 for(int i=left;i<=n && a[i].x<=mid;i )
33 {
34 if(a[i].x>=ll) update(a[i].num,1);
35 }
36 for(int i=l;i<=r;i ){
37 if(q[i].opt==1 && q[i].v<=mid) update(q[i].num,1);
38 if(q[i].opt==2 && q[i].v<=mid) update(q[i].num,-1);
39 if(q[i].opt==3) q[i].cnt=getsum(q[i].y)-getsum(q[i].x-1);
40 }
41 for(int i=left;i<=n && a[i].x<=mid;i )
42 if(a[i].x>=ll) update(a[i].num,-1);
43 for(int i=l;i<=r;i ){
44 if(q[i].opt==1 && q[i].v<=mid) update(q[i].num,-1);
45 if(q[i].opt==2 && q[i].v<=mid) update(q[i].num,1);
46 }
47 }
48 void dfs(int l,int r,int ll,int rr){
49 if(l>r) return;
50 if(ll==rr){
51 for(int i=l;i<=r;i )
52 if(q[i].k) ans[q[i].num]=ll;
53 return;
54 }
55 int mid=(ll rr)/2;
56 calc(l,r,ll,mid);
57 int s1=0,s2=0;
58 for(int i=l;i<=r;i ){
59 if(q[i].k){
60 if(q[i].cnt>=q[i].k) ta[ s1]=q[i];
61 else q[i].k-=q[i].cnt,tb[ s2]=q[i];
62 }else {
63 if(q[i].v<=mid) ta[ s1]=q[i];
64 else tb[ s2]=q[i];
65 }
66 }
67 int p=l;
68 for(int i=1;i<=s1;i ) q[p ]=ta[i];
69 for(int i=1;i<=s2;i ) q[p ]=tb[i];
70 dfs(l,l s1-1,ll,mid);
71 dfs(l s1,r,mid 1,rr);
72 }
73 int main(){
74 while (scanf("%d",&n)!=EOF)
75 {
76 for(int i=1;i<=n;i ){
77 scanf("%d",&a[i].x);
78 a[i].num=i;
79 xa[i]=a[i].x;
80 }
81 sum=0;
82 scanf("%d",&m);
83 memset(q,0,sizeof(q));
84 memset(c,0,sizeof(c));
85 for(int i=1;i<=m;i ){
86 int t;
87 scanf("%d",&t);
88 if(t==1) {
89 sum;
90 q[sum].opt=1;
91 scanf("%d%d",&q[sum].num,&q[sum].v);
92 sum;
93 q[sum].opt=2;
94 q[sum].num=q[sum-1].num;
95 q[sum].v=xa[q[sum-1].num];
96 xa[q[sum].num]=q[sum-1].v;
97 }else {
98 sum;
99 q[sum].opt=3;
100 scanf("%d%d%d",&q[sum].x,&q[sum].y,&q[sum].k);
101 q[sum].num=i;
102 }
103 }
104 sort(a 1,a n 1);
105 memset(ans,0,sizeof(ans));
106 dfs(1,sum,1,inf);
107 for(int i=1;i<=m;i )
108 if(ans[i]) printf("%d\n",ans[i]);
109 }
110 return 0;
111 }
View Code
? 来源：https://www./content-4-396951.html |
|
|
