BZOJ3110

发表于 | 分类于 |

题目传送门

Description

有N个位置，M个操作。

操作有两种：

1：在位置a到位置b加入一个数c。

2：询问位置a到位置b，第c大的数是什么。

Input

第一行，两个整数$N$，$M$，意义如上。

接下来$M$行，每行形如：1 a b c或2 a b c。第一个数为1时执行第一个操作，为2时执行第2个操作。

Output

输出每个询问的结果

Solution

嵌套数据结构经典题目。

一开始想的是用区间线段树套权值线段树，发觉搞不了。

后来听大佬说后发现可以用权值树套区间数。然后用二分查找找到第c大数。

因为如果节点直接全开会爆空间而且有很多浪费，所以需要动态开空间。

Code

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=40*50000+10;
long long int n,m;
struct TREE2
{
	long long int sum,lazy;
	TREE2 *lsun,*rsun;
};
struct TREE1
{
	TREE2 *ROOT;
}tree[maxn];
struct IntervalTree2D
{
	long long int x,y,x1,ans,sum;
	
	long long query2(TREE2 *v,long long int l,long long int r)
	{
		if(v==NULL) return 0;
		if(l>=x&&r<=y) return v->sum;
		long long int k=0,mid=(l+r)/2;
		
		if(v->lazy)
		{
			if(v->lsun==NULL) v->lsun=new TREE2();
			if(v->rsun==NULL) v->rsun=new TREE2();
			v->lsun->sum+=v->lazy*(mid-l+1);
			v->rsun->sum+=v->lazy*(r-mid);
			v->lsun->lazy+=v->lazy;
			v->rsun->lazy+=v->lazy;
			v->lazy=0;
		}
		if(x<=mid) k+=query2(v->lsun,l,mid);
		if(y>mid) k+=query2(v->rsun,mid+1,r);
		return k;
	}
	
	void query1(long long int num,long long int l,long long int r)
	{
		if(l==r) {ans=l;return;}
		long long sum1=query2(tree[num*2+1].ROOT,1,n);
		long long int mid=(r+l)/2;
		if(sum+sum1>=x1) query1(num*2+1,mid+1,r);
		else
		{
			sum+=sum1;
			query1(num*2,l,mid);
		}
	}
	
	void modify2(TREE2 *v,long long int l,long long int r)
	{
		if(l>=x&&r<=y)
		{
			v->lazy++;
			v->sum+=(r-l+1);
			return;
		}
		
		long long int mid=(l+r)/2;
		if(v->lsun==NULL) v->lsun=new TREE2();
		if(v->rsun==NULL) v->rsun=new TREE2();
		
		if(v->lazy)
		{
			v->lsun->sum+=v->lazy*(mid-l+1);
			v->rsun->sum+=v->lazy*(r-mid);
			v->lsun->lazy+=v->lazy;
			v->rsun->lazy+=v->lazy;
			v->lazy=0;
		}
		
		if(mid>=x) modify2(v->lsun,l,mid);
		if(mid<y) modify2(v->rsun,mid+1,r);
		v->sum=v->lsun->sum+v->rsun->sum;
	}
	
	void modify1(long long int num,long long int l,long long int r)
	{
		if(tree[num].ROOT==NULL) tree[num].ROOT=new TREE2();
		if(l==r){ modify2(tree[num].ROOT,1,n);return;}
		long long int mid=(l+r)/2;
		
		if(x1<=mid) modify1(num*2,l,mid);
		else modify1(num*2+1,mid+1,r);
		
		modify2(tree[num].ROOT,1,n);
	}
}t;
struct FFF
{
	long long int q,x,y,z;
}que[maxn];
struct FFFF
{
	long long int v,num;
}list[maxn];
int lnum;
bool cmp(FFFF a,FFFF b)
{
	return a.v<b.v;
}
long long int turn[maxn];
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld%lld",&que[i].q,&que[i].x,&que[i].y,&que[i].z);
		if(que[i].q==1)
		{
			list[++lnum].v=que[i].z;
			list[lnum].num=i;
		}
	}
	
	sort(list+1,list+1+lnum,cmp);
	long long int c=1;
	turn[1]=list[1].v;
	que[list[1].num].z=1;
	for(int i=2;i<=lnum;i++)
	{
		if(list[i].v!=list[i-1].v)
		{
			c++;
			turn[c]=list[i].v;
		}
		que[list[i].num].z=c;
	}
	
	for(int i=1;i<=m;i++)
	{
		long long int k=que[i].q;
		t.x=que[i].x;
		t.y=que[i].y;
		t.x1=que[i].z;
		if(k==1)
			t.modify1(1,1,n);
		else
		{
			t.sum=0;
			t.query1(1,1,n);
			printf("%lld\n",turn[t.ans]);
		}
	}
	return 0;
}