3196: Tyvj 1730 二逼平衡樹 Description 您需要寫一種數據結構（可參考題目標題），來維護一個有序數列，其中需要提供以下操作：1.查詢k在區間內的排名2.查詢區間內排名為k的值3.修改某一位值上的數值4.查詢k在區間內的前驅(前驅定義為小於x，且最大的數)5.查詢k在區間內的 ...
3196: Tyvj 1730 二逼平衡樹
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 3357 Solved: 1326
[Submit][Status][Discuss]
Description
您需要寫一種數據結構（可參考題目標題），來維護一個有序數列，其中需要提供以下操作：
1.查詢k在區間內的排名
2.查詢區間內排名為k的值
3.修改某一位值上的數值
4.查詢k在區間內的前驅(前驅定義為小於x，且最大的數)
5.查詢k在區間內的後繼(後繼定義為大於x，且最小的數)
Input
第一行兩個數 n,m 表示長度為n的有序序列和m個操作
第二行有n個數，表示有序序列
下麵有m行，opt表示操作標號
若opt=1 則為操作1，之後有三個數l,r,k 表示查詢k在區間[l,r]的排名
若opt=2 則為操作2，之後有三個數l,r,k 表示查詢區間[l,r]內排名為k的數
若opt=3 則為操作3，之後有兩個數pos,k 表示將pos位置的數修改為k
若opt=4 則為操作4，之後有三個數l,r,k 表示查詢區間[l,r]內k的前驅
若opt=5 則為操作5，之後有三個數l,r,k 表示查詢區間[l,r]內k的後繼
Output
對於操作1,2,4,5各輸出一行，表示查詢結果
Sample Input
9 64 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5
Sample Output
24
3
4
9
HINT
1.n和m的數據範圍：n,m<=50000
2.序列中每個數的數據範圍：[0,1e8]
3.雖然原題沒有，但事實上5操作的k可能為負數 分析：樹狀數組套主席樹裸題
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 #define LL long long 8 #define Inf 2e9 9 #define Lowbit(x) (x&-x) 10 #define ls(x) (a[x].lc) 11 #define rs(x) (a[x].rc) 12 const int maxn=105000; 13 struct Node{ 14 int lc,rc,sum; 15 }a[maxn*50]; 16 struct Ques{ 17 int type,l,r,k; 18 }q[maxn]; 19 int n,m,cnt,root[maxn],s[maxn]; 20 int hash[maxn*2],num,b[maxn]; 21 int ra[maxn],rb[maxn],la[maxn],lb[maxn]; 22 void Insert(int x,int add,int & rt,int l,int r,int type){ 23 if(!rt || type){ 24 a[++cnt]=a[rt];rt=cnt; 25 } 26 a[rt].sum+=add; 27 if(l==r)return; 28 int mid=(l+r)>>1; 29 if(x<=mid)Insert(x,add,ls(rt),l,mid,type); 30 else Insert(x,add,rs(rt),mid+1,r,type); 31 } 32 void Bit_Update(int x,int p,int add){ 33 for(int i=x;i<=n;i+=Lowbit(i))Insert(p,add,s[i],1,num,0); 34 } 35 int Rank(int x,int pr,int rt,int l,int r){ 36 if(x>r){ 37 int temp=a[rt].sum-a[pr].sum; 38 for(int i=1;i<=ra[0];i++)temp-=a[ra[i]].sum; 39 for(int i=1;i<=rb[0];i++)temp+=a[rb[i]].sum; 40 return temp; 41 } 42 int mid=(l+r)>>1; 43 for(int i=1;i<=ra[0];i++)la[i]=ra[i],ra[i]=ls(ra[i]); 44 for(int i=1;i<=rb[0];i++)lb[i]=rb[i],rb[i]=ls(rb[i]); 45 int sum=Rank(x,ls(pr),ls(rt),l,mid); 46 if(x>mid+1){ 47 for(int i=1;i<=ra[0];i++)ra[i]=rs(la[i]); 48 for(int i=1;i<=rb[0];i++)rb[i]=rs(lb[i]); 49 sum+=Rank(x,rs(pr),rs(rt),mid+1,r); 50 } 51 return sum; 52 } 53 int kth(int k,int pr,int rt,int l,int r){ 54 if(l==r)return l; 55 int temp=a[ls(rt)].sum-a[ls(pr)].sum; 56 int mid=(l+r)>>1; 57 for(int i=1;i<=ra[0];i++)temp-=a[ls(ra[i])].sum; 58 for(int i=1;i<=rb[0];i++)temp+=a[ls(rb[i])].sum; 59 if(temp>=k){ 60 for(int i=1;i<=ra[0];i++)ra[i]=ls(ra[i]); 61 for(int i=1;i<=rb[0];i++)rb[i]=ls(rb[i]); 62 return kth(k,ls(pr),ls(rt),l,mid); 63 } 64 else{ 65 for(int i=1;i<=ra[0];i++)ra[i]=rs(ra[i]); 66 for(int i=1;i<=rb[0];i++)rb[i]=rs(rb[i]); 67 return kth(k-temp,rs(pr),rs(rt),mid+1,r); 68 } 69 } 70 void Copy(int l,int r){ 71 ra[0]=rb[0]=0; 72 for(int i=l-1;i;i-=Lowbit(i))ra[++ra[0]]=s[i]; 73 for(int i=r;i;i-=Lowbit(i))rb[++rb[0]]=s[i]; 74 } 75 void Init(); 76 int main(){ 77 freopen("psh.in","r",stdin);freopen("psh.out","w",stdout); 78 Init(); 79 getchar();getchar(); 80 return 0; 81 } 82 void Init(){ 83 scanf("%d%d",&n,&m); 84 for(int i=1;i<=n;i++){ 85 scanf("%d",&b[i]); 86 hash[++num]=b[i]; 87 } 88 for(int i=1;i<=m;i++){ 89 scanf("%d",&q[i].type); 90 if(q[i].type==3){ 91 scanf("%d%d",&q[i].l,&q[i].r); 92 hash[++num]=q[i].r; 93 } 94 else{ 95 scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k); 96 if(q[i].type!=2)hash[++num]=q[i].k; 97 } 98 } 99 sort(hash+1,hash+num+1); 100 num=unique(hash+1,hash+num+1)-hash-1; 101 for(int i=1;i<=n;i++){ 102 int x=lower_bound(hash+1,hash+num+1,b[i])-hash; 103 root[i]=root[i-1]; 104 Insert(x,1,root[i],1,num,1); 105 } 106 for(int i=1;i<=m;i++){ 107 int type=q[i].type; 108 if(type==1){ 109 int x=lower_bound(hash+1,hash+num+1,q[i].k)-hash; 110 Copy(q[i].l,q[i].r); 111 printf("%d\n",Rank(x,root[q[i].l-1],root[q[i].r],1,num)+1); 112 } 113 if(type==2){ 114 Copy(q[i].l,q[i].r); 115 printf("%d\n",hash[kth(q[i].k,root[q[i].l-1],root[q[i].r],1,num)]); 116 } 117 if(type==3){ 118 int x=lower_bound(hash+1,hash+num+1,b[q[i].l])-hash; 119 int y=lower_bound(hash+1,hash+num+1,q[i].r)-hash; 120 if(x==y)continue; 121 Bit_Update(q[i].l,x,-1); 122 Bit_Update(q[i].l,y,1); 123 b[q[i].l]=q[i].r; 124 } 125 if(type==4){ 126 int x=lower_bound(hash+1,hash+num+1,q[i].k)-hash; 127 Copy(q[i].l,q[i].r); 128 int pos=Rank(x,root[q[i].l-1],root[q[i].r],1,num); 129 Copy(q[i].l,q[i].r); 130 printf("%d\n",hash[kth(pos,root[q[i].l-1],root[q[i].r],1,num)]); 131 } 132 if(type==5){ 133 int x=lower_bound(hash+1,hash+num+1,q[i].k)-hash; 134 Copy(q[i].l,q[i].r); 135 int pos=Rank(x+1,root[q[i].l-1],root[q[i].r],1,num); 136 Copy(q[i].l,q[i].r); 137 printf("%d\n",hash[kth(pos+1,root[q[i].l-1],root[q[i].r],1,num)]); 138 } 139 } 140 }
