正題

題目鏈接:https://www.luogu.com.cn/problem/P2617

---

題目大意

給出一個序列，要求支持

區間查詢第$k$大

單點修改

---

解題思路

區間查詢第$k$大需要使用主席樹，構建權值線段樹的前綴和。考慮如何進行單點修改，在前綴和上進行單點修改就是進行區間修改，區間修改主席樹顯然不可能，考慮樹套樹。

我們可以維護以權值線段樹為權值的樹狀數組，這樣可以單點修改并且維護動態前綴和。

時間復雜度:$O(n{\log }^{2}n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define lowbit(x) (x&-x) using namespace std; const int N=1e5+10,M=N*400; int n,m,a[N],b[N*2],root[N]; int q1[N],q2[N],q3[N],num; int w[M],ls[M],rs[M],tot; int cnt1,cnt2,tmp1[N],tmp2[N]; char op[N]; void Updata(int &x,int l,int r,int pos,int val){if(!x)x=++num;if(l==r){w[x]+=val;return;}int mid=(l+r)>>1;if(pos<=mid)Updata(ls[x],l,mid,pos,val);else Updata(rs[x],mid+1,r,pos,val);w[x]=w[ls[x]]+w[rs[x]]; } void Change(int x,int val){int k=lower_bound(b+1,b+1+tot,a[x])-b;while(x<=n){Updata(root[x],1,tot,k,val);x+=lowbit(x);}return; } int Ask(int l,int r,int k){if(l==r)return l;int mid=(l+r)>>1,sum=0;for(int i=1;i<=cnt1;i++)sum-=w[ls[tmp1[i]]];for(int i=1;i<=cnt2;i++)sum+=w[ls[tmp2[i]]];if(k<=sum){for(int i=1;i<=cnt1;i++)tmp1[i]=ls[tmp1[i]];for(int i=1;i<=cnt2;i++)tmp2[i]=ls[tmp2[i]];return Ask(l,mid,k);}else{for(int i=1;i<=cnt1;i++)tmp1[i]=rs[tmp1[i]];for(int i=1;i<=cnt2;i++)tmp2[i]=rs[tmp2[i]];return Ask(mid+1,r,k-sum);} } int Query(int x,int l,int r){l--;cnt1=cnt2=0;for(int i=l;i;i-=lowbit(i))tmp1[++cnt1]=root[i];for(int i=r;i;i-=lowbit(i))tmp2[++cnt2]=root[i];return Ask(1,tot,x); } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[++tot]=a[i];}for(int i=1;i<=m;i++){cin>>op[i];scanf("%d %d",&q1[i],&q2[i]);if(op[i]=='Q')scanf("%d",&q3[i]);else b[++tot]=q2[i];}sort(b+1,b+1+tot);tot=unique(b+1,b+1+tot)-b-1;for(int i=1;i<=n;i++)Change(i,1);for(int i=1;i<=m;i++){if(op[i]=='Q')printf("%d\n",b[Query(q3[i],q1[i],q2[i])]);else{Change(q1[i],-1);a[q1[i]]=q2[i];Change(q1[i],1);}}return 0; }

總結

以上是生活随笔為你收集整理的P2617-Dynamic Rankings【树套树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。