「zoj2112」Dynamic Rankings
The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], …, a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], …, a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.
Your task is to write a program for this computer, which
– Reads N numbers from the input (1 <= N <= 50,000)
– Processes M instructions of the input (1 <= M <= 10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], …, a[j] and change some a[i] to t.
Input
The first line of the input is a single number X (0 < X <= 4), the number of the test cases of the input. Then X blocks each represent a single test case.
The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format
Q i j k or
C i t
It represents to query the k-th number of a[i], a[i+1], …, a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000.
There’re NO breakline between two continuous test cases.
Output
For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],…, a[j])
There’re NO breakline between two continuous test cases.
Sample Input
2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
3
6
题解
线段树套平衡树，在线段树的每一个区间内套一棵平衡树
然后二分值判断区间内比它小的数的个数
似乎比可持久更好理解
主要是代码量比较大
treap写的不够顺手
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #define N 200001 #define M 1300001 using namespace std; int T,n,m,tmp; int a[50001],root[N]; int sz,s[M],ls[M],rs[M],v[M],w[M],rnd[M]; void update(int k) {s[k]=s[ls[k]]+s[rs[k]]+w[k];} void rturn(int &k) {int t=ls[k];ls[k]=rs[t];rs[t]=k;s[t]=s[k];update(k);k=t;} void lturn(int &k) {int t=rs[k];rs[k]=ls[t];ls[t]=k;s[t]=s[k];update(k);k=t;} void insert(int &k,int num) { if(!k) {k=++sz;s[k]=w[k]=1;ls[k]=rs[k]=0;rnd[k]=rand();v[k]=num;return;} s[k]++; if(v[k]==num)w[k]++; else if(num<v[k]) {insert(ls[k],num);if(rnd[ls[k]]<rnd[k])rturn(k);} else {insert(rs[k],num);if(rnd[rs[k]]<rnd[k])lturn(k);} } void del(int &k,int num) { if(v[k]==num) { if(w[k]>1){w[k]--;s[k]--;return;} if(ls[k]*rs[k]==0)k=ls[k]+rs[k]; else if(rnd[ls[k]]<rnd[rs[k]]) {rturn(k);del(k,num);} else {lturn(k);del(k,num);} } else if(num<v[k]){del(ls[k],num);s[k]--;} else {del(rs[k],num);s[k]--;} } void change(int k,int l,int r,int x,int num,int y) { del(root[k],y); insert(root[k],num); if(l==r)return; int mid=(l+r)>>1; if(x<=mid)change(k<<1,l,mid,x,num,y); else change(k<<1|1,mid+1,r,x,num,y); } void build(int k,int l,int r,int x,int num) { insert(root[k],num); if(l==r)return; int mid=(l+r)>>1; if(x<=mid)build(k<<1,l,mid,x,num); else build(k<<1|1,mid+1,r,x,num); } void find(int k,int num) { if(!k)return; if(v[k]<=num){tmp+=s[ls[k]]+w[k];find(rs[k],num);} else find(ls[k],num); } void que(int k,int l,int r,int x,int y,int num) { if(l==x&&r==y){find(root[k],num);return;} int mid=(l+r)>>1; if(mid>=y)que(k<<1,l,mid,x,y,num); else if(mid<x)que(k<<1|1,mid+1,r,x,y,num); else { que(k<<1,l,mid,x,mid,num); que(k<<1|1,mid+1,r,mid+1,y,num); } } int main() { scanf("%d",&T); while(T--) { memset(root,0,sizeof(root)); sz=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){scanf("%d",&a[i]);} for(int i=1;i<=n;i++)build(1,1,n,i,a[i]); for(int i=1;i<=m;i++) { char s[3];int x,y,z; scanf("%s",s); if(s[0]=='C') { scanf("%d%d",&x,&y); change(1,1,n,x,y,a[x]); a[x]=y; } else { scanf("%d%d%d",&x,&y,&z); int l=0,r=1000000000; while(l<=r) { int mid=(l+r)>>1; tmp=0;que(1,1,n,x,y,mid); if(tmp>=z)r=mid-1; else l=mid+1; } printf("%d\n",l); } } } return 0; } |
求问root数组在哪里修改过吗？我没看出来。如果没修改，那作用是什么？
insert和del的k是&k
系统:正在调用fc函数
系统:正在对比文件zoj2112from lwher && zoj2112from hzwer
系统:找不到相异处……
23333
大神。群里好多人拜摸你！求加群 : 318135341