「洛谷P2617」Dynamic Rankings

发表于 | 分类于 | | 浏览量： 次

标算又是树套树？写不来QwQ…

传送门

BZOJ(是个权限题QwQ)

洛谷P2617

题解

据说这题可以用带修主席树、树套树、整体二分解。由于蒟蒻我实在太菜了QwQ，只好选择了整体二分。

把刚原始序列理解为n个添加操作，将修改操作理解为一个删除操作和一个添加操作。然后直接上整体二分，解法类似于「ZJOI2013」K大数查询。并且由于每次只需要修改一个位置的信息，所以用普通树状数组就行了呢poi，快得飞起（尽管我自带大常数QwQ）。

png1

代码

整体二分又好写又好理解呢poi

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
#include<cstdio>
using namespace std;
const int maxn=100005;
int n,m,tot,cnt,ans[maxn],A[maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
struct BIT                   //封装好的树状数组
{
	int Tree[maxn];
	void Update(int pos,int delta){while(pos<=n){Tree[pos]+=delta;pos+=pos&-pos;}}
	int Query(int pos){int ret=0;while(pos>0){ret+=Tree[pos];pos-=pos&-pos;}return ret;}
}Tr;
struct Command{int typ,idx,num,delta,L,R,k,id;}Q[maxn*4],Q1[maxn*4],Q2[maxn*4];
char GetChar()           //读取操作类型，排除无用字符
{
	char ch=getchar();
	while(ch!='C'&&ch!='Q') ch=getchar();
	return ch;
}
void BinarySearch(int L,int R,int S,int T)  //整体二分
{
	if(L>R||S>T) return;
	int mid=L+R>>1,til1=0,til2=0;
	if(L==R)
	{
		for(int i=S;i<=T;i++)
			if(Q[i].typ)
				ans[Q[i].id]=mid;
		return;
	}
	for(int i=S;i<=T;i++)
	{
		if(!Q[i].typ)
		{
			if(Q[i].num<=mid)
			{
				Tr.Update(Q[i].idx,Q[i].delta);
				Q1[++til1]=Q[i];
			}
			else Q2[++til2]=Q[i];
		}
		else
		{
			int cnt=Tr.Query(Q[i].R)-Tr.Query(Q[i].L-1);
			if(cnt<Q[i].k)
			{
				Q[i].k-=cnt;
				Q2[++til2]=Q[i];
			}
			else Q1[++til1]=Q[i];
		}
	}
	for(int i=S;i<=T;i++)              //别忘了还原树状数组哟poi
		if(!Q[i].typ)
			if(Q[i].num<=mid)
				Tr.Update(Q[i].idx,-Q[i].delta);
	for(int i=1;i<=til1;i++) Q[S+i-1]=Q1[i];
	for(int i=1;i<=til2;i++) Q[S+til1+i-1]=Q2[i];
	BinarySearch(L,mid,S,S+til1-1);
	BinarySearch(mid+1,R,S+til1,T);
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++){tot++;Q[tot].idx=i;Q[tot].num=A[i]=read();Q[tot].delta=1;}
	for(int i=1;i<=m;i++)
	{
		if(GetChar()=='Q'){tot++;cnt++;Q[tot].typ=1;Q[tot].L=read();Q[tot].R=read();Q[tot].k=read();Q[tot].id=cnt;}
		else
		{
			tot++;Q[tot].idx=read();Q[tot].num=read();Q[tot].delta=1;
			tot++;Q[tot].idx=Q[tot-1].idx;Q[tot].num=A[Q[tot-1].idx];A[Q[tot-1].idx]=Q[tot-1].num;Q[tot].delta=-1;
		}
	}
	BinarySearch(0,1000000000,1,tot);
	for(int i=1;i<=cnt;i++) printf("%d\n",ans[i]);
	return 0;
}