修补操作比较麻烦，其他都是珂朵莉树的基本操作。
首先统计原材料区间有多少个 \(1\)，并把它们摊平成 \(0\)。
然后在待修补区间的迭代器上迭代，并让可使用的 \(1\) 的个数逐渐减少，直到无法填平整个结点的区间。
把它切开然后摊平。
具体细节见代码，参考了 yzhang 大佬的写法。
代码： 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
using namespace std;
const int N = 2e5;
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 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);
}
inline void cure(int tl,int tr,int l,int r)
{
IT itr = split(tr + 1),itl = split(tl);
int sum = 0;
for(;itl != itr;++itl)
sum += itl->val * (itl->r - itl->l + 1);
assign(tl,tr,0);
if(!sum)
return ;
itr = split(r + 1),itl = split(l);
if(sum >= r - l + 1)
{
tree.erase(itl,itr);
tree.insert((node){l,r,1});
return ;
}
for(;itl != itr;++itl)
if(!itl->val)
{
sum -= itl->r - itl->l + 1;
if(sum <= 0)
{
assign(itl->l,itl->r + sum,1);
break;
}
else
itl->val = 1;
}
}
int main()
{
scanf("%d%d",&n,&m);
tree.insert((node){1,n,1});
int op,a,b,c,d;
while(m--)
{
scanf("%d%d%d",&op,&a,&b);
if(op == 0)
assign(a,b,0);
else if(op == 1)
scanf("%d%d",&c,&d),cure(a,b,c,d);
else
printf("%d\n",continuity(a,b));
}
}