树状数组套主席树裸题
等下上课就要讲了啊。。。赶快传上来先
好了可以开写了虽然还没讲
其实这个东西很简单的。。
因为操作要求单点修改单点查询
主席树原本用的是前缀和,查询O(1)修改O(n)
啥都不用是查询O(n)修改O(1)
【很自然的】就想到折中的树状数组了
于是就完了
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 |
// <1901.cpp> - 01/26/16 20:51:46 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=10001; int lowbit(int x){return x&-x;} int val[40*MAXN],l[40*MAXN],r[40*MAXN]; int a[MAXN],u[MAXN*2],root[MAXN]; int A[MAXN],B[MAXN],C[MAXN]; int ls,rs,LS[30],RS[30]; int tot; int ref(int root,int L,int R,int rank,int x){ int now=++tot; val[now]=val[root]+x;l[now]=l[root];r[now]=r[root]; if(L!=R){ int M=(L+R)>>1; if(rank<=M)l[now]=ref(l[root],L,M,rank,x); else r[now]=ref(r[root],M+1,R,rank,x); } return now; } int src(int L,int R,int k){ if(L==R)return L; int suml=0,sumr=0; for(int i=1;i<=ls;i++)suml+=val[l[LS[i]]]; for(int i=1;i<=rs;i++)sumr+=val[l[RS[i]]]; int M=(L+R)>>1; if(k<=sumr-suml){ for(int i=1;i<=ls;i++)LS[i]=l[LS[i]]; for(int i=1;i<=rs;i++)RS[i]=l[RS[i]]; return src(L,M,k); }else{ for(int i=1;i<=ls;i++)LS[i]=r[LS[i]]; for(int i=1;i<=rs;i++)RS[i]=r[RS[i]]; return src(M+1,R,k-(sumr-suml)); } } int main(){ int n=getint(),m=getint(),L=n; char s; for(int i=1;i<=n;i++)u[i]=a[i]=getint(); for(int i=1;i<=m;i++){ cin>>s; A[i]=getint();B[i]=getint(); if(s=='Q')C[i]=getint(); else u[++L]=B[i]; } sort(u+1,u+1+L); L=unique(u+1,u+1+L)-u-1; for(int i=1;i<=n;i++){ int rank=lower_bound(u+1,u+1+L,a[i])-u; for(int o=i;o<=n;o+=lowbit(o))root[o]=ref(root[o],1,L,rank,1); } for(int i=1;i<=m;i++){ if(C[i]){ ls=0;rs=0;A[i]--; for(int o=A[i];o;o-=lowbit(o))LS[++ls]=root[o]; for(int o=B[i];o;o-=lowbit(o))RS[++rs]=root[o]; printf("%d\n",u[src(1,L,C[i])]); }else{ int rank=lower_bound(u+1,u+1+L,a[A[i]])-u; a[A[i]]=B[i]; for(int o=A[i];o<=n;o+=lowbit(o))root[o]=ref(root[o],1,L,rank,-1); rank=lower_bound(u+1,u+1+L,B[i])-u; for(int o=A[i];o<=n;o+=lowbit(o))root[o]=ref(root[o],1,L,rank,1); } } return 0; } |