为什么这么多人暴力过了啊！！！！！
比赛时写了正解的我非常不爽！！！
提供一组 Hack 数据。
第一个其实操作就是找到 \(A\) 之后的第一个空花瓶和第 \(F\) 个空花瓶，并且把他们修改为非空。
第二个就是修改一段花瓶为空。
我们可以把空花瓶视作 \(1\)，非空视作 \(0\)。
那么我们需要的操作相当于找某个数之后的第 \(k\) 个 \(1\)，或者是修改一段数。
如果用线段树来维护，修改其实就是区间赋值的操作，第 \(k\) 个 \(1\) 也可以类比权值线段树上找第 \(k\) 小的方式。
所以我们已经得到了一个 \(O(n \log n)\) 的算法。
代码： 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
using namespace std;
const int N = 5e4;
int n,m;
struct node
{
int sum,tag;
} seg[(N << 2) + 10];
inline void push(int p,int tl,int tr)
{
if(~seg[p].tag)
{
int mid = tl + tr >> 1;
seg[ls].sum = seg[p].tag * (mid - tl + 1),seg[ls].tag = seg[p].tag;
seg[rs].sum = seg[p].tag * (tr - mid),seg[rs].tag = seg[p].tag;
seg[p].tag = -1;
}
}
void update(int l,int r,int k,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
{
seg[p].sum = k * (tr - tl + 1),seg[p].tag = k;
return ;
}
push(p,tl,tr);
int mid = tl + tr >> 1;
if(l <= mid)
update(l,r,k,ls,tl,mid);
if(r > mid)
update(l,r,k,rs,mid + 1,tr);
seg[p].sum = seg[ls].sum + seg[rs].sum;
}
int query(int l,int r,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
return seg[p].sum;
push(p,tl,tr);
int mid = tl + tr >> 1;
int ret = 0;
if(l <= mid)
ret += query(l,r,ls,tl,mid);
if(r > mid)
ret += query(l,r,rs,mid + 1,tr);
return ret;
}
int query(int k,int p,int tl,int tr)
{
if(tl == tr)
return tl;
push(p,tl,tr);
int mid = tl + tr >> 1;
if(k <= seg[ls].sum)
return query(k,ls,tl,mid);
else
return query(k - seg[ls].sum,rs,mid + 1,tr);
}
int main()
{
scanf("%d%d",&n,&m),update(1,n,1,1,1,n);
int op,x,y;
while(m--)
{
scanf("%d%d%d",&op,&x,&y);
if(op == 1)
{
++x;
if(!query(x,n,1,1,n))
puts("Can not put any one.");
else
{
int k = x > 1 ? query(1,x - 1,1,1,n) : 0;
int l = query(min(k + 1,seg[1].sum),1,1,n);
int r = query(min(k + y,seg[1].sum),1,1,n);
update(l,r,0,1,1,n);
printf("%d %d\n",l - 1,r - 1);
}
}
else
++x,++y,printf("%d\n",y - x + 1 - query(x,y,1,1,n)),update(x,y,1,1,1,n);
}
}