题目大意
有$n$个位置和$m$个操作。操作有两种，每次操作如果是$1\, a\,b \,c$的形式，表示往第$a$个位置到第$b$个位置每个位置加入一个数$c$。如果操作形如$2\,a\,b\,c$的形式，表示询问从第$a$个位置到第$b$个位置，第$c$大的数是多少。
整体二分
这道题可以使用树套树解决，但在这里我们提出一种更加神奇的做法，它的名字是：整体二分。
整体二分是什么？其实这不是什么新东西，就是CDQ分治的变种。
整体二分的特殊在于它是对答案进行二分，而CDQ分治是对操作（时间轴）等进行二分。
为什么这种方法被称为整体二分？普通的二分是对某个单个元素进行的二分，而整体二分是对一个区间整体进行的二分，因此被称为整体二分。
整体二分的原理是二分答案，将操作对答案的影响根据二分的值划归在两个区间中依次继续二分。若每一层消耗的时间是$O(R-L)$，那么整体二分的复杂度则为$O(n\log n)$
题目分析
本题是一道整体二分的题，步骤如下：
我们用CDQBinary(s,t,L,R)表示处理$s\rightarrow t$的操作，答案在$L\rightarrow R$间。我们对$L$、$R$进行分治，而$s$、$t$是附属属性，如果是普通二分，$s==t$。
注意询问的是$k$大，需要转化为$k$小进行操作。
如果$L==R$，达到区间$[s,t]$答案。
处理区间$[s,t]$操作，如果是修改操作，插入的值$\le$二分出的$mid$，则在树状数组中更新区间个数，放入左区间，否则放入右区间。
如果是询问操作，使用树状数组得到区间的元素个数，若元素个数$\ge k$，将询问放入左区间，否则将$k$减去元素个数，放入右区间。
如果不会树状数组区间修改查询可以参考这里，讲的非常好。
清空树状数组，并递归左右区间。（若左右区间不存在不需要递归）
代码
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
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=50005;
struct Point {
int opt,id,l,r;
LL k;
} p[maxn];
int n;
LL ans[maxn];
struct BIT {
LL c1[maxn],c2[maxn];
#define lowbit(x) x&(-x)
void add(int x,LL v) {
for(int i=x; i<=n; i+=lowbit(i)) {
c1[i]+=v;
c2[i]+=x*v;
}
}
LL ask(int x) {
LL ans=0;
for(int i=x; i>0; i-=lowbit(i))ans+=(x+1)*c1[i]-c2[i];
return ans;
}
} bit;
void CDQBinary(int s,int t,LL Left,LL Right) {
if(s>t)return;
if(Left==Right) {
for(int i=s; i<=t; i++)
if(p[i].opt==2)ans[p[i].id]=Left;
return;
}
LL mid=(Left+Right)>>1;
vector<Point>q1,q2;
for(int i=s; i<=t; i++)
if(p[i].opt==1) {
if(p[i].k<=mid) {
bit.add(p[i].l,1);
bit.add(p[i].r+1,-1);
q1.push_back(p[i]);
} else q2.push_back(p[i]);
} else {
LL tmp=bit.ask(p[i].r)-bit.ask(p[i].l-1);
if(tmp>=p[i].k)q1.push_back(p[i]);
else p[i].k-=tmp,q2.push_back(p[i]);
}
for(int i=s; i<=t; i++)
if(p[i].opt==1&&p[i].k<=mid) {
bit.add(p[i].l,-1);
bit.add(p[i].r+1,1);
}
bool bj1=0,bj2=0;
for(int i=0; i<q1.size(); i++)p[i+s]=q1[i],bj1=1;
for(int i=0; i<q2.size(); i++)p[i+s+q1.size()]=q2[i],bj2=1;
if(bj1)CDQBinary(s,s+q1.size()-1,Left,mid);
if(bj2)CDQBinary(s+q1.size(),t,mid+1,Right);
}
int m,cnt=0;
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=m; i++) {
p[i].opt=Get_Int();
p[i].l=Get_Int();
p[i].r=Get_Int();
p[i].k=Get_Int();
if(p[i].opt==1)p[i].k=n+1-p[i].k;
else p[i].id=++cnt;
}
CDQBinary(1,m,0,n<<1+2);
for(int i=1; i<=cnt; i++)printf("%d\n",n+1-ans[i]);
return 0;
}
|
