Dynamic Rankings
动态区间第K大,方法有很多可以用或者是带修改主席树,这个题目相较于不带修改的区间第K大,整体二分的优势就体现出来了。又快又好打
#include <bits/stdc++.h>
const int MAXN = 500000;
using namespace std;
int n,m,top,cnt,cnt1;
int H[MAXN],last[MAXN],ans[MAXN],C[MAXN];
struct node{
int l,r,k,id;
}Q[MAXN],Tl[MAXN],Tr[MAXN];
inline void init()
{
int x;
for(int i = 1;i <= n;i++){
scanf("%d",&x);
last[i] = x;
Q[++cnt].l = i;
Q[cnt].r = x;
Q[cnt].id = 0;
H[++top] = x;
}
char s[10];
int l,r;
for(int i = 1;i <= m;i++){
scanf("%s",s);
if(s[0] == 'Q'){
cnt++;
scanf("%d %d %d",&Q[cnt].l,&Q[cnt].r,&Q[cnt].k);
Q[cnt].id = ++cnt1;
}
else {
cnt++;
scanf("%d %d",&l,&r);
Q[cnt].l = l;
Q[cnt].r = last[l];
last[l] = r;
Q[cnt].id = -1;
Q[++cnt].l = l;
Q[cnt].r = r;
Q[cnt].id = 0;
H[++top] = r;
}
}
sort(H+1,H+top+1);
top = unique(H+1,H+1+top) - H;
top--;
for(int i = 1;i <= cnt;i++){
if(Q[i].id <= 0){
Q[i].r = lower_bound(H+1,H+1+top,Q[i].r) - H;
}
}
}
inline int lowbit(int x){return x & -x;}
inline void add(int x,int d){
for(;x <= n;x += lowbit(x)) C[x] += d;
}
inline int sum(int x){
int ret = 0;
for(;x;x -= lowbit(x)) ret += C[x];
return ret;
}
void solve(int L,int R,int st,int ed){
if(st > ed) return;
if(L == R){
for(int i = st;i <= ed;i++)
if(Q[i].id > 0)
ans[Q[i].id] = H[L];
return;
}
int M = (L + R) >> 1;
int lc = 0,rc = 0;
for(int i = st;i <= ed;i++){
if(Q[i].id == -1){
if(Q[i].r <= M) add(Q[i].l,-1),Tl[++lc] = Q[i];
else Tr[++rc] = Q[i];
}
else if(Q[i].id == 0){
if(Q[i].r <= M) add(Q[i].l,1),Tl[++lc] = Q[i];
else Tr[++rc] = Q[i];
}
else {
int x = sum(Q[i].r) - sum(Q[i].l - 1);
if(Q[i].k <= x) Tl[++lc] = Q[i];
else Q[i].k -= x,Tr[++rc] = Q[i];
}
}
for(int i = ed;i >= st;i--) {
if(Q[i].id == -1 && Q[i].r <= M) add(Q[i].l,+1);
if(Q[i].id == 0 && Q[i].r <= M) add(Q[i].l,-1);
}
for(int i = 1;i <= lc;i++) Q[st+i-1] = Tl[i];
for(int i = 1;i <= rc;i++) Q[st+lc+i-1] = Tr[i];
solve(L,M,st,st+lc-1);solve(M+1,R,st+lc,ed);
}
int main()
{
scanf("%d %d",&n,&m);
init();
solve(1,top,1,cnt);
for(int i = 1;i <= cnt1;i++)
printf("%d\n",ans[i]);
return 0;
}