JZOJ 3191 「中山市选 2013」花瓶

为什么这么多人暴力过了啊!!!!!
比赛时写了正解的我非常不爽!!!
提供一组 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
#include <cstdio>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
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);
}
}