bzoj 1901 Dynamic Rankings

Posted on | Views:

整体二分.

  • $solve(l,r,L,R)$ 表示当前处理编号在 $L\sim R$ 内的询问与修改操作,询问的答案在 $l\sim r$ 内.
  • 每次处理时,若当前 $l=r$ ,就回答 $L\sim R$ 内的询问.
  • 否则,二分答案 $mid$ ,对于编号在 $L\sim R$ 内的修改操作,按照修改的权值分成 $\le mid,>mid$ 两边,若 $\le mid$ ,就在树状数组里将它对应的位置 $+1$ .
  • 对于编号在 $L\sim R$ 内的询问操作,按照在树状数组中询问区间的权值和 $sum\le k,>k$ 分成两边,若 $<k$ ,就将 $k$ 减去这个 $sum$ .
  • 然后将分出的修改与询问操作分到左右两边,递归解决即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int inf=1e9;
const int MAXN=1e5+10;
int n,m,a[MAXN];
int ans[MAXN];
struct node
{
	int x,y,k,id,type;
	node(){x=y=k=id=type=0;}
	node(int x,int y,int k,int id,int type):x(x),y(y),k(k),id(id),type(type) {}
}q[MAXN*3],ql[MAXN*3],qr[MAXN*3];
struct FenwickTree
{
	int bit[MAXN];
	FenwickTree(){memset(bit,0,sizeof bit);}
#define lowbit(x) x&(-x)
	void add(int x,int c)
	{
		for(;x<=n;x+=lowbit(x))
			bit[x]+=c;
	}
	int sum(int x)
	{
		int s=0;
		for(;x;x-=lowbit(x))
			s+=bit[x];
		return s;
	}
	int query(int l,int r)
	{
		return sum(r)-sum(l-1);
	}
}T;
int cnt=0,qcnt=0;
void solve(int l,int r,int L,int R)
{
	if(l>r || L>R)
		return;
	if(l==r)
	{
		for(int i=L;i<=R;++i)
			if(q[i].type)
				ans[q[i].id]=l;
		return;
	}
	int mid=(l+r)>>1,cntl=0,cntr=0;
	for(int i=L;i<=R;++i)
	{
		if(q[i].type)
		{
			int sum=T.query(q[i].x,q[i].y);
			if(sum>=q[i].k)
				ql[++cntl]=q[i];
			else
			{
				q[i].k-=sum;
				qr[++cntr]=q[i];
			}
		}
		else
		{
			if(q[i].x<=mid)
			{
				T.add(q[i].id,q[i].y);
				ql[++cntl]=q[i];
			}
			else
				qr[++cntr]=q[i];
		}
	}
	for(int i=1;i<=cntl;++i)
		if(!ql[i].type)
			T.add(ql[i].id,-ql[i].y);
	for(int i=1;i<=cntl;++i)
		q[L+i-1]=ql[i];
	for(int i=1;i<=cntr;++i)
		q[L+cntl+i-1]=qr[i];
	solve(l,mid,L,L+cntl-1);
	solve(mid+1,r,L+cntl,R);
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		q[++cnt]=node(a[i],1,0,i,0);
	}	
	for(int i=1;i<=m;++i)
	{
		char buf[2];
		scanf("%s",buf);
		if(buf[0]=='Q')
		{
			int x=read(),y=read(),k=read();
			q[++cnt]=node(x,y,k,++qcnt,1);
		}
		else
		{
			int x=read(),y=read();
			q[++cnt]=node(a[x],-1,0,x,0);
			a[x]=y;
			q[++cnt]=node(a[x],1,0,x,0);
		}
	}
	solve(-inf,inf,1,cnt);
	for(int i=1;i<=qcnt;++i)
		printf("%d\n",ans[i]);
	return 0;
}