Dynamic Rankings

题意：

一个序列，N个数，M次操作，操作分为两种：
1、 将一个数修改为另外一个数。
2、 询问区间第K小。
\(1<=n,m<=10^5\) , \(0<=a_i<=10^9\)

思路：

裸的整体二分。
对于修改操作，只需把原来的数减去再把新的加上来就好了。
时间复杂度\((nlog^2n)\)

注意事项：

树状数组中存的到底是什么？

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=1e9;
int n,m,cnt,tot;
int a[N],ans[N];
struct node{int l,r,k,id,tp;}q[N<<2],q1[N<<2],q2[N<<2];
inline int read()
{
	int s=0,w=1; char ch=getchar();
	for(;'0'>ch||ch>'9';ch=getchar())if(ch=='-')w=-1;
	for(;'0'<=ch&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
	return s*w;
}
struct tree{
	int c[N];
	inline int lowbit(int x){return x&(-x);}
	inline void add(int x,int v)
	{
		for(;x<=n;x+=lowbit(x))c[x]+=v;
	}
	inline int query(int x)
	{
		int anss=0;
		for(;x;x-=lowbit(x))anss+=c[x];
		return anss;
	}
}T;
void solve(int L,int R,int l,int r)
{
	if(l>r) return;
	if(L==R)
	{
		for(int i=l;i<=r;++i)
			if(q[i].tp==1) ans[q[i].id]=L;
		return;
	}
	int mid=L+R>>1,cnt1=0,cnt2=0;
	for(int i=l;i<=r;++i)
	{
		if(q[i].tp==2) 
		{
			if(q[i].l<=mid) T.add(q[i].id,q[i].r),q1[++cnt1]=q[i];
			else q2[++cnt2]=q[i];
		}
		else
		{
			int tmp=T.query(q[i].r)-T.query(q[i].l-1);
			if(q[i].k<=tmp) q1[++cnt1]=q[i];
			else q2[++cnt2]=q[i],q2[cnt2].k-=tmp;
		}
	}
	for(int i=l;i<=r;++i)
		if(q[i].l<=mid&&q[i].tp==2) T.add(q[i].id,-q[i].r);
	for(int i=l;i<=l+cnt1-1;++i)q[i]=q1[i-l+1];
	for(int i=l+cnt1;i<=r;++i)q[i]=q2[i-l-cnt1+1];
	solve(L,mid,l,l+cnt1-1);
	solve(mid+1,R,l+cnt1,r);
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		q[i]=node{a[i],1,0,i,2};
	}
	char opt[5];cnt=n;
	for(int i=n+1;i<=n+m;++i)
	{
		scanf("%s",opt);
		if(opt[0]=='Q')
		{
			int l=read(),r=read(),k=read();
			q[++cnt]=node{l,r,k,++tot,1};
		}
		else
		{
			int x=read(),y=read();
			q[++cnt]=node{a[x],-1,0,x,2};
			q[++cnt]=node{a[x]=y,1,0,x,2};
		}
	}
	solve(0,inf,1,cnt);
	for(int i=1;i<=tot;++i)
		printf("%d\n",ans[i]);
	return 0;
}