「ZJOI2013」K大数查询|整体二分

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

什么？树套树？不存在的。

传送门

洛谷传送门

BZOJ传送门

在您开始阅读本题解之前，蒟蒻我建议您先把题面多看几遍，并仔细阅读样例和样例说明。

我才不会告诉你蒟蒻我就是因为看错题面然后白忙活了一个小时。

题解

据说本题可以用树套树解，但是树套树这种东西常数稍微一大就TLE，这位dalao的树套树就咕掉了。而且树套树对于蒟蒻我来说太*难了，所以我们需要整体二分这种东西。

首先确保您已经掌握普通二分的写法，不会普通二分的请自行Ctrl+w。

整体二分的主要思想就是把这一大坨询问一起处理。

首先让我们来考虑只有一个询问操作的情况：

二分权值(即答案)，每次分到一个$mid$，我们就把这个询问之前所有的有贡献的添加操作(即$c$值大于$mid$的添加操作)用一个支持区间修改的树状数组或者线段树预处理，然后我们就可以很快地得到区间$[a,b]$中权值大于$mid$的数的个数$tot$。如果$tot$小于这个询问操作的$c$值，那么我们就把$c$值减去$tot$，然后把之前产生过贡献的添加操作扔掉删除，并修改二分的边界值继续二分；否则直接修改二分的边界值继续二分即可。

好了现在再来考虑有一坨询问的情况。

方便起见，我们把询问操作和添加操作一起处理。设当前二分的值是$mid$，二分的权值区间是$[L,R]$要处理的操作区间是$[s,t]$。那我们先遍历一遍操作区间，如果当前遍历到的是有贡献的添加操作，就更新一下线段树；若果是询问操作，就在线段树上查询一下该询问区间内权值大于$mid$的个数$tot$，根据$tot$是否大于$c$并把操作分成两堆，然后递归分别处理两堆，直到$L=R$时$mid$就是当前所有询问操作的答案。(添加操作也要根据$c$值是否大于$mid$也一起分成两堆)

注意将操作分堆时每一堆内不要打乱操作的顺序。

时间复杂度$\Theta(n\log^2{n})$，常数是真的小QwQ。

代码

貌似真的比树套树好懂

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
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=50005;
int n,m,cnt,ans[maxn];
inline LL read()
{
	LL 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 Command
{
	int typ,L,R,id;LL C;
}Q[maxn],Q1[maxn],Q2[maxn];
struct SegmentTree                            //一个普普通通的线段树
{
private:
	struct Node{LL Sum,Tag;}Tree[maxn*4];
	void PushUp(int rt){Tree[rt].Sum=Tree[rt*2].Sum+Tree[rt*2+1].Sum;}
	void PushDown(int rt,int LC,int RC)
	{
		Tree[rt*2].Tag+=Tree[rt].Tag;Tree[rt*2+1].Tag+=Tree[rt].Tag;
		Tree[rt*2].Sum+=LC*Tree[rt].Tag;Tree[rt*2+1].Sum+=RC*Tree[rt].Tag;
		Tree[rt].Tag=0;
	}
public:
	void RangeUpdate(int LL,int RR,int delta,int L=1,int R=n,int rt=1)
	{
		if(LL<=L&&R<=RR){Tree[rt].Sum+=(R-L+1)*delta;Tree[rt].Tag+=delta;return;}
		int M=L+R>>1;
		PushDown(rt,M-L+1,R-M);
		if(LL<=M) RangeUpdate(LL,RR,delta,L,M,rt*2);
		if(M<RR) RangeUpdate(LL,RR,delta,M+1,R,rt*2+1);
		PushUp(rt);
	}
	LL RangeQuery(int LL,int RR,int L=1,int R=n,int rt=1)
	{
		if(LL<=L&&R<=RR) return Tree[rt].Sum;
		int M=L+R>>1;::LL ret=0;
		PushDown(rt,M-L+1,R-M);
		if(LL<=M) ret+=RangeQuery(LL,RR,L,M,rt*2);
		if(M<RR) ret+=RangeQuery(LL,RR,M+1,R,rt*2+1);
		return ret;
	}
}S;
void BinarySearch(int L,int R,int s,int t)                 //整体二分
{
	if(L>R||s>t) return;
	int mid=L+R>>1,len1=0,len2=0;
	if(L==R)
	{
		for(int i=s;i<=t;i++)
			if(Q[i].typ==2)                              //只有询问操作才需要回答
				ans[Q[i].id]=mid;
		return;
	}
	for(int i=s;i<=t;i++)
	{
		if(Q[i].typ==1)
		{
			if(Q[i].C>mid)
			{
				S.RangeUpdate(Q[i].L,Q[i].R,1);
				Q1[++len1]=Q[i];                          //操作分堆
			}
			else Q2[++len2]=Q[i];
		}
		else
		{
			LL tot=S.RangeQuery(Q[i].L,Q[i].R);
			if(Q[i].C<=tot) Q1[++len1]=Q[i];             //操作分堆
			else{Q2[++len2]=Q[i];Q2[len2].C-=tot;}
		}
	}
	for(int i=s;i<=t;i++)                               //撤销操作，清空线段树
		if(Q[i].typ==1&&Q[i].C>mid)
			S.RangeUpdate(Q[i].L,Q[i].R,-1);
	int j=s;
	for(int i=1;i<=len1;i++,j++) Q[j]=Q1[i];
	for(int i=1;i<=len2;i++,j++) Q[j]=Q2[i];
	BinarySearch(L,mid,s+len1,t);BinarySearch(mid+1,R,s,s+len1-1);
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		Q[i].typ=read();
		if(Q[i].typ==2) Q[i].id=++cnt;
		Q[i].L=read();Q[i].R=read();Q[i].C=read();
	}
	BinarySearch(-n,n,1,m);
	for(int i=1;i<=cnt;i++) printf("%d\n",ans[i]);
	return 0;
}