本文主要是介绍#主席树，二分，树状数组#洛谷 2617 Dynamic Ranking，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
TLE分块题解
题目
区间第 k k k大支持单点修改
分析
如果没有修改操作，就真的只是一道主席树裸题，但是加上修改操作，就不得不使用树状数组维护，其实思路比较简单，主要考验码题能力 (在这一点我是最菜的呀)
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=100011; struct rec{int l,r,w;}q[N];
int w[N*600],ls[N*600],rs[N*600],xa[N],xb[N],cnt,ta,tb,b[N<<1],a[N],n,m,rt[N],Q;
inline signed iut(){rr int ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
inline void print(int ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
inline void update(int &rt,int l,int r,int x,int y){if (!rt) rt=++cnt; w[rt]+=y;if (l==r) return; rr int mid=(l+r)>>1;if (x<=mid) update(ls[rt],l,mid,x,y);else update(rs[rt],mid+1,r,x,y);
}
inline signed query(int l,int r,int x){if (l==r) return l;rr int sum=0,mid=(l+r)>>1;for (rr int i=1;i<=ta;++i) sum-=w[ls[xa[i]]];for (rr int i=1;i<=tb;++i) sum+=w[ls[xb[i]]];if (x<=sum){for (rr int i=1;i<=ta;++i) xa[i]=ls[xa[i]];for (rr int i=1;i<=tb;++i) xb[i]=ls[xb[i]];return query(l,mid,x);}else{for (rr int i=1;i<=ta;++i) xa[i]=rs[xa[i]];for (rr int i=1;i<=tb;++i) xb[i]=rs[xb[i]];return query(mid+1,r,x-sum); }
}
inline void add(int x,int y){rr int t=lower_bound(b+1,b+1+m,a[x])-b;for (rr int i=x;i<=n;i+=-i&i) update(rt[i],1,m,t,y);
}
signed main(){m=n=iut(); Q=iut();for (rr int i=1;i<=n;++i) b[i]=a[i]=iut();for (rr int i=1;i<=Q;++i){rr char c=getchar();while (!isalpha(c)) c=getchar();q[i]=(rec){iut(),iut(),c=='Q'?iut():0};if (c=='C') b[++m]=q[i].r;}sort(b+1,b+1+m); m=unique(b+1,b+1+m)-b-1;for (rr int i=1;i<=n;++i) add(i,1);for (rr int i=1;i<=Q;++i)if (q[i].w){ta=tb=0;for (rr int j=q[i].l-1;j;j-=-j&j) xa[++ta]=rt[j];for (rr int j=q[i].r;j;j-=-j&j) xb[++tb]=rt[j];print(b[query(1,m,q[i].w)]),putchar(10);}else add(q[i].l,-1),a[q[i].l]=q[i].r,add(q[i].l,1);return 0;
}
这篇关于#主席树，二分，树状数组#洛谷 2617 Dynamic Ranking的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
