区间覆盖，区间求和，区间连续值个数……
珂朵莉树！
骗分神器珂朵莉树，懒得写线段树就用她！
出题人很良心地没有卡珂朵莉树，估计只有发明人才会卡吧……
代码： 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
using namespace std;
const int N = 1e5;
int n,m;
struct node
{
int l,r;
mutable int val;
inline bool operator<(const node &a) const
{
return l < a.l;
}
};
set<node> tree;
typedef set<node>::iterator IT;
IT split(int x)
{
IT it = tree.lower_bound((node){x,0,0});
if(it != tree.end() && it->l == x)
return it;
--it;
int l = it->l,r = it->r;
int v = it->val;
tree.erase(it);
tree.insert((node){l,x - 1,v});
return tree.insert((node){x,r,v}).first;
}
inline void assign(int l,int r,int val)
{
IT itr = split(r + 1),itl = split(l);
tree.erase(itl,itr);
tree.insert((node){l,r,val});
}
inline void flip(int l,int r)
{
IT itr = split(r + 1),itl = split(l);
for(;itl != itr;++itl)
itl->val ^= 1;
}
inline int query(int l,int r)
{
IT itr = split(r + 1),itl = split(l);
int ret = 0;
for(;itl != itr;++itl)
ret += itl->val * (itl->r - itl->l + 1);
return ret;
}
inline int continuity(int l,int r)
{
IT itr = split(r + 1),itl = split(l);
int ret = 0,cur = 0;
for(;itl != itr;++itl)
if(itl->val)
cur += itl->r - itl->l + 1;
else
{
ret = max(ret,cur);
cur = 0;
}
return max(ret,cur);
}
int main()
{
scanf("%d%d",&n,&m);
int x,last,cnt = 1;
scanf("%d",&last);
for(register int i = 2;i <= n;++i)
{
scanf("%d",&x);
if(x == last)
++cnt;
else
{
tree.insert((node){i - cnt,i - 1,last});
last = x;
cnt = 1;
}
}
tree.insert((node){n - cnt + 1,n,last});
int op,a,b;
while(m--)
{
scanf("%d%d%d",&op,&a,&b);
++a,++b;
if(op == 0 || op == 1)
assign(a,b,op);
else if(op == 2)
flip(a,b);
else if(op == 3)
printf("%d\n",query(a,b));
else
printf("%d\n",continuity(a,b));
}
}