題目鏈接：點擊查看
題目大意：給出一個長度為 n 的數列 a，再給出 m 次操作：
Q l r k：返回區間 [ l , r ] 內第 k 大的數C x y：令?a[ x ] = y
題目分析：其實就是帶修主席樹。。考慮靜態主席樹，維護的是一個線段樹的前綴和，如果強行修改的話，修改一次的最壞時間復雜度將高達 nlogn，完成 m 次操作后的時間復雜度為 nmlogn，還不如直接暴力去區間里找呢。。直接暴力的話時間復雜度也才 n * m
所以為了盡可能去平衡查詢和修改的時間復雜度，考慮用樹狀數組維護前綴和，樹狀數組維護普通數組的前綴和，只需要維護 lowbit 位置的 logn 個點，將數組換成主席樹，也就只需要維護 logn 條鏈即可，這樣查詢和修改的時間復雜度都是 nlog^2n
注意，時空復雜度都是 nlog^2n，所以主席樹的空間應該開 1e5 * log( 1e5 ) * log( 1e5 ) ≈ 400N，本來是想直接開 1e5 * log( 1e5 ) * log( 1e9 ) 的，這樣就不用離散化了，可惜空間不太夠用，所以只能去離線然后乖乖離散化了
代碼：
?
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Qu
{char op[5];int a,b,c;
}q[N];int a[N],n,m,len;struct Node
{int l,r;int sum;
}tree[N*640];int cnt,root[N],num[2],temp[2][20];int lowbit(int x)
{return x&(-x);
}void update(int num,int &k,int l,int r,int val)
{tree[cnt++]=tree[k];k=cnt-1;tree[k].sum+=val;if(l==r)return;int mid=l+r>>1;if(num<=mid)update(num,tree[k].l,l,mid,val);elseupdate(num,tree[k].r,mid+1,r,val);
}void add(int pos,int val)
{for(int i=pos;i<=n;i+=lowbit(i))update(a[pos],root[i],1,len,val);
}int query(int l,int r,int k)
{if(l==r)return l;int sum=0;for(int i=1;i<=num[1];i++)sum+=tree[tree[temp[1][i]].l].sum;for(int i=1;i<=num[0];i++)sum-=tree[tree[temp[0][i]].l].sum;int mid=l+r>>1;if(k<=sum){for(int i=1;i<=num[1];i++)temp[1][i]=tree[temp[1][i]].l;for(int i=1;i<=num[0];i++)temp[0][i]=tree[temp[0][i]].l;return query(l,mid,k);}else{for(int i=1;i<=num[1];i++)temp[1][i]=tree[temp[1][i]].r;for(int i=1;i<=num[0];i++)temp[0][i]=tree[temp[0][i]].r;return query(mid+1,r,k-sum);}
}int ask(int l,int r,int k)
{num[0]=num[1]=0;for(int i=l-1;i>0;i-=lowbit(i))temp[0][++num[0]]=root[i];for(int i=r;i>0;i-=lowbit(i))temp[1][++num[1]]=root[i];return query(1,len,k);
}vector<int>node;int get_id(int x)
{return lower_bound(node.begin(),node.end(),x)-node.begin()+1;
}void discreate()
{sort(node.begin(),node.end());node.erase(unique(node.begin(),node.end()),node.end());len=node.size();for(int i=1;i<=n;i++)a[i]=get_id(a[i]);for(int i=1;i<=m;i++)if(q[i].op[0]=='C')q[i].b=get_id(q[i].b);
}void init()
{root[0]=0;tree[0].l=tree[0].r=tree[0].sum=0;cnt=1;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);init();scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",a+i);node.push_back(a[i]);}for(int i=1;i<=m;i++){scanf("%s",q[i].op);if(q[i].op[0]=='C'){scanf("%d%d",&q[i].a,&q[i].b);node.push_back(q[i].b);}elsescanf("%d%d%d",&q[i].a,&q[i].b,&q[i].c); }discreate();for(int i=1;i<=n;i++)add(i,1); for(int i=1;i<=m;i++){if(q[i].op[0]=='Q'){printf("%d\n",node[ask(q[i].a,q[i].b,q[i].c)-1]);}else{add(q[i].a,-1);a[q[i].a]=q[i].b;add(q[i].a,1);}}return 0;
}
?
超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生
總結
以上是生活随笔為你收集整理的洛谷 - P2617 Dynamic Rankings(树状数组套主席树)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
