Reincarnation

正因为梦易碎，才格外美好。

关联性容器 & 颜色段均摊

发表于 更新于 分类于 ，
本文字数： 18k 阅读时长 ≈ 16 分钟

“愿世间美好一如既往，不复存在。”

关联性容器

俗称为 std::set，是常用的 中的一种，其构成与 std::map 类似，内部使用红黑树实现，是一种关联容器。std::set 是一个已排序集。

需要注意的是，std::set 如同一个集合，不允许出现键值相同的元素，这是与 std::map 一个本质的区别，当然，如果既需要使用 std::set，又无法排除重复元素的影响，可以考虑使用 std::multiset，其用法与 std::set 类似。

std::set 支持很多操作，类比于平衡树，可以在 的时间内完成。

首先定义 std::set<int>St：

  • St.insert(x)：插入键值为 的元素，如果已经存在，则不执行。返回迭代器，以及插入是否成功的一个 std::pair<iterator,bool>。
  • St.erase(x)：删除所有键值为 的所有元素，并返回删除元素的个数。
  • St.erase(it)：此时的 it 是一个迭代器，并删除当前迭代器指向的元素，此时 it 必须合法。
  • St.erase(l,r)：此时的 l,r 为迭代器，并删除所有范围在 内的迭代器指向的元素。
  • St.clear()：清空。

std::set 提供了一些常用的迭代器：

  • St.begin() 指向当前 std::set 的第一个元素。
  • St.end() 指向尾端占位符的迭代器，此时迭代器为空。
  • St.rbegin() 指向当前 std::set 的最后一个合法元素。
  • St.rend() 指向第一个元素的前一个元素，迭代器为空。

std::set 提供了一些常用的操作：

  • St.count(x)：返回 std::set 内键值为 的元素数量。
  • St.find(x)：返回键值为 的迭代器，如果不存在返回 end()。
  • St.lower_bound(x) 返回指向首个不小于给定键的元素的迭代器。如果不存在这样的元素，返回 end()。
  • St.upper_bound(x) 返回指向首个大于给定键的元素的迭代器。如果不存在这样的元素，返回 end()。
  • St.empty() 返回 std::set 是否为空。
  • St.size() 返回元素个数。

颜色段均摊

起源于一道 的数据结构题，可以用于大多数可以使用线段树或者平衡树进行维护的随机数据的 题，一般可以骗很多的分数。

其核心思想在于，将权值相同的区间合并为一个结点，并保存在 std::set 里面，在随机数据的区间赋值下效率较高，但如果数据不随机，无法保证复杂度正确。

但如果复杂度正确，使用 std::set 维护可以做到 ，而使用链表则可以做到 。

存储

根据其核心思想，在区间赋值操作时，将连续相同权值的元素合并为一个结点，也就是将整个序列表示 的形式，表示序列中 区间内的权值都为 ，用结构体存储：

参考实现
 
1
2
3
4
5
6
7
8
struct Cho
{
    int l,r;
    mutable int v;
    Cho(int l=0,int r=0,int v=0):l(l),r(r),v(v){}
    bool operator<(const Cho &x) const { return l<x.l; }
};
std::set<Cho>Odt;

由于 std::set 强制内部有序，所以 operator 重载运算符是必要的。而至于 mutable，是指当整个结构体处于静态变量时，其权值依然为可变量，即不受 const 影响。

基础实现

很显然的，题目数据中所给到的操作区间与我们当前已经划分的区间可能并不大同，意味着我们可能会需要拆分区间，所以需要一个分裂区间的操作，也就是将 断为 。

参考实现
 
1
2
3
4
5
6
7
8
9
10
inline auto split(int x)
{
    auto it=Odt.lower_bound(Cho(x,0,0));
    if(it!=Odt.end()&&it->l==x) return it;
    it--;
    int l=it->l,r=it->r,v=it->v;
    Odt.erase(it);
    Odt.insert(Cho(l,x-1,v));
    return Odt.insert(Cho(x,r,v)).first;
}

至于区间赋值，赋值之后这一段区间一定会形如 ，而至于原来的，我们只需要全部将其覆盖即可。

参考实现
 
1
2
3
4
5
6
inline void assign(int l,int r,int v)
{
    auto ed=split(r+1),st=split(l);
    Odt.erase(st,ed);
    Odt.insert(Cho(l,r,v));
}

那么，做接下来的这道题就显得犹为简单了。

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/915/E

形式化题意：给定一个长度为 的序列，开始时所有 ，共 个操作，每一操作将 赋为 ，求全局和。

数据范围：

整个询问中只有一个修改，就是对区间进行赋值，那我们可以直接用珂朵莉树维护，而对于求和，我们选择在 assign 操作的时候进行在线维护，然后统计答案即可。

AC Code
 
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
// ----- Eternally question-----
// Problem: E. Physical Education Lessons
// Contest: Codeforces - Educational Codeforces Round 36 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/915/E
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-06-27 08:28:14
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=3e5+10;
int N,Q;
ll ans;
struct Cho
{
	int l,r;
	mutable ll v;
	Cho(int l=0,int r=0,ll v=0):l(l),r(r),v(v){}
	bool operator<(const Cho &x) const { return l<x.l; }
};
std::set<Cho>Odt;
inline auto split(int x)
{
	auto it=Odt.lower_bound(Cho(x,0,0));
	if(it!=Odt.end()&&it->l==x) return it;
	it--;
	int  l=it->l,r=it->r;ll v=it->v;
	Odt.erase(it),Odt.insert(Cho(l,x-1,v));
	return Odt.insert(Cho(x,r,v)).first;
}
inline void assign(int l,int r,ll v)
{
	auto ed=split(r+1),st=split(l);
	int cnt=0,len=0;
	for(auto it=st;it!=ed;it++)
	{
		len+=(it->r-it->l+1);
		cnt+=it->v*(it->r-it->l+1);
	}
	Odt.erase(st,ed),Odt.insert(Cho(l,r,v));
	if(v==1) ans+=(len-cnt);
	else ans-=cnt;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	Odt.insert(Cho(1,N,1)),ans=N;
	for(int ql,qr,qk;Q--;)
	{
		read(ql,qr,qk);
		assign(ql,qr,qk-1);
		write(ans,'\n');
	}
	return 0;
}
/*

*/

例题

珂朵莉树的实现主要突出一个暴力，不管怎么样，都直接往最暴力的思想去凑，只要数据足够随机，其复杂度就是正确的，甚至如果将珂朵莉树与朴素暴力进行平衡规划的话，甚至可以通过很多线段树与平衡树的没有经过精心构造的数据。

纵使日薄西山

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/896/C

形式化题意：给定一个长度为 的序列 ，共 次操作：

  • 区间加 ；
  • 区间覆盖 ；
  • 求区间第 小值；
  • 求区间 次方和对 取模。

数据强随机，随机种子为 ，值域不超过 。

数据范围：

这道题就是 的起源了，出题人为了介绍自己研究的数据结构专门出了这么一道题。

对于区间覆盖，就是提到的 assign 操作，而对于区间加，我们想办法把区间内所有结点提出并直接维护，也就是朴素暴力，但是枚举的是 std::set 的结点。

对于区间 小值，居然是我没法想到的极其朴素的暴力，那就是将区间内的所有结点全部扔进一个 std::vector 或者数组然后直接 std::sort，最后枚举 std::vector，有一说一，确实太离谱了。

对于区间 次方和，我们也同样枚举结点，直接统计答案为 。

AC Code
 
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// ----- Eternally question-----
// Problem: C. Willem, Chtholly and Seniorious
// Contest: Codeforces - Codeforces Round 449 (Div. 1)
// URL: https://codeforces.com/problemset/problem/896/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-06-27 14:14:30
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const ll Mod=1e9+7;
ll N,Q,Seed,Vmax;
inline ll rnd()
{
	auto ret=Seed;
	Seed=(Seed*7+13)%Mod;
	return ret;
}
struct Cho
{
	ll l,r;
	mutable ll v;
	Cho(ll l=0,ll r=0,ll v=0):l(l),r(r),v(v){}
	bool operator<(const Cho &x) const { return l<x.l; }
};
std::set<Cho>Odt;
inline auto split(ll x)
{
	auto it=Odt.lower_bound(Cho(x,0,0));
	if(it!=Odt.end()&&it->l==x) return it;
	it--;
	ll l=it->l,r=it->r,v=it->v;
	Odt.erase(it),Odt.insert(Cho(l,x-1,v));
	return Odt.insert(Cho(x,r,v)).first;
}
inline void assign(ll l,ll r,ll v)
{
	auto ed=split(r+1),st=split(l);
	Odt.erase(st,ed);
	Odt.insert(Cho(l,r,v));
}
inline void add(ll l,ll r,ll v)
{
	auto ed=split(r+1),st=split(l);
	for(auto it=st;it!=ed;it++) it->v+=v;
}
inline ll kth(ll l,ll r,ll k)
{
	auto ed=split(r+1),st=split(l);
	std::vector<std::pair<ll,ll>>vec;
	for(auto it=st;it!=ed;it++) vec.push_back(std::make_pair(it->v,it->r-it->l+1));
	std::sort(vec.begin(),vec.end());
	for(auto x:vec)
	{
		k-=x.second;
		if(k<=0) return x.first;
	}
	return vec[vec.size()-1].first;
}
inline ll qPow(ll a,ll b,ll p)
{
	ll res=1;a%=p;
	for(;b;b>>=1,a=a*a%p) (b&1)&&(res=res*a%p);
	return res;
}
inline ll query(ll l,ll r,ll k,ll p)
{
	ll res=0;
	auto ed=split(r+1),st=split(l);
	for(auto it=st;it!=ed;it++) res=(res+qPow(it->v,k,p)*(it->r-it->l+1)%p)%p;
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q,Seed,Vmax);
	for(int i=1;i<=N;++i)
	{
		auto a=rnd()%Vmax+1;
		Odt.insert(Cho(i,i,a));
	}
	for(ll opt,ql,qr,qx,qy;Q--;)
	{
		opt=rnd()%4+1,ql=rnd()%N+1,qr=rnd()%N+1;
		if(ql>qr) std::swap(ql,qr);
		if(opt==1) qx=rnd()%Vmax+1,add(ql,qr,qx);
		else if(opt==2) qx=rnd()%Vmax+1,assign(ql,qr,qx);
		else if(opt==3) qx=rnd()%(qr-ql+1)+1,write(kth(ql,qr,qx),'\n');
		else
		{
			qx=rnd()%Vmax+1,qy=rnd()%Vmax+1;
			write(query(ql,qr,qx,qy),'\n');
		}
	}
	return 0;
}
/*

*/

纵使繁花落尽

题目简介

题目名称：脑洞治疗仪
题目来源：上海省选

评测链接 ：https://loj.ac/p/2037
评测链接 ：https://www.luogu.com.cn/problem/P4344

形式化题意：给定一个长度为 的 序列，初始全为 ，共 次操作：

  • 将区间 赋为 ；
  • 用区间 的 去填补 的 ，多余舍去，不足则从左往右填完为止。
  • 查询区间 内最大的连续 段长度。

数据范围：

超这道题洛谷上 被 掉了，搞得我还得重写一遍线段树。

用 写，第二个修改直接从左往右扫直到没得填，询问也扫一遍直接 checkMax 即可。

用线段树写，可以考虑类似于 「序列操作」 的维护方法，但第二个操作需要用到线段树二分，时间复杂度 ，好像有一支 的做法，但我不会。

AC Code（珂朵莉树）
 
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// ----- Eternally question-----
// Problem: #2037. 「SHOI2015」脑洞治疗仪
// Contest: LibreOJ
// URL: https://loj.ac/p/2037
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-06-27 15:57:26
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
int N,Q;
struct Cho
{
	int l,r;
	mutable int v;
	Cho(int l=0,int r=0,int v=0):l(l),r(r),v(v){}
	bool operator<(const Cho &x) const { return l<x.l; }
};
std::set<Cho>Odt;
inline auto split(int x)
{
	auto it=Odt.lower_bound(Cho(x,0,0));
	if(it!=Odt.end()&&it->l==x) return it;
	it--;
	int l=it->l,r=it->r,v=it->v;
	Odt.erase(it),Odt.insert(Cho(l,x-1,v));
	return Odt.insert(Cho(x,r,v)).first;
}
inline void assign(int l,int r,int v)
{
	auto ed=split(r+1),st=split(l);
	Odt.erase(st,ed);
	Odt.insert(Cho(l,r,v));
}
inline int get(int l,int r)
{
	auto ed=split(r+1),st=split(l);
	int ret=0;
	for(auto it=st;it!=ed;it++) ret+=(it->r-it->l+1)*it->v;
	return ret;
}
inline void cover(int l,int r,int ql,int qr)
{
	int cnt=get(l,r);
	assign(l,r,0);
	auto ed=split(qr+1),st=split(ql);
	for(auto it=st;it!=ed;it++)
	{
		if(it->v==1) continue;
		if(cnt>=it->r-it->l+1) it->v=1,cnt-=it->r-it->l+1;
		else
		{
			if(!cnt) return ;
			assign(it->l,it->l+cnt-1,1);
			return ;
		}
	}
}
inline int query(int l,int r)
{
	int res=0,pos=0;
	auto ed=split(r+1),st=split(l);
	for(auto it=st;it!=ed;it++)	
	{
		if(it->v==0) pos+=it->r-it->l+1;
		else pos=0;
		checkMax(res,pos);
	}
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	Odt.insert(Cho(1,N,1));
	for(int opt,ql,qr;Q--;)
	{
		read(opt,ql,qr);
		if(opt==0) assign(ql,qr,0);
		else if(opt==1)
		{
			int l,r;read(l,r);
			cover(ql,qr,l,r);
		}
		else write(query(ql,qr),'\n');
	}
	return 0;
}
/*

*/
AC Code（线段树）
 
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
// ----- Eternally question-----
// Problem: P4344 [SHOI2015] 脑洞治疗仪
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4344
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-06-27 19:31:05
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
int N,Q;
#define ls (p<<1)
#define rs (p<<1|1)
struct St
{
	int l,r,len,cnt;
	int lx,rx,val,tag;
}Tr[MAXN<<2];
inline void pushUp(int p)
{
	Tr[p].lx=Tr[ls].lx,Tr[p].rx=Tr[rs].rx;
	if(Tr[ls].lx==Tr[ls].len) Tr[p].lx+=Tr[rs].lx;
	if(Tr[rs].rx==Tr[rs].len) Tr[p].rx+=Tr[ls].rx;
	Tr[p].val=std::max(std::max(Tr[ls].val,Tr[rs].val),Tr[ls].rx+Tr[rs].lx);
	Tr[p].cnt=Tr[ls].cnt+Tr[rs].cnt;
}
inline void pushDown(int p)
{
	if(~Tr[p].tag)
	{
		Tr[ls].lx=Tr[ls].rx=Tr[ls].val=(Tr[p].tag^1)*Tr[ls].len;
		Tr[rs].lx=Tr[rs].rx=Tr[rs].val=(Tr[p].tag^1)*Tr[rs].len;
		Tr[ls].cnt=Tr[ls].len*(Tr[p].tag^1),Tr[rs].cnt=Tr[rs].len*(Tr[p].tag^1);
		Tr[ls].tag=Tr[rs].tag=Tr[p].tag;
		Tr[p].tag=-1;
	}
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r,Tr[p].tag=-1,Tr[p].len=r-l+1;
	if(l==r) return Tr[p].lx=Tr[p].rx=Tr[p].val=Tr[p].cnt=0,void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void modifyCover(int p,int l,int r,int c)
{
	if(l<=Tr[p].l&&Tr[p].r<=r)
	{
		Tr[p].lx=Tr[p].rx=Tr[p].val=Tr[p].len*(c^1);
		Tr[p].tag=c,Tr[p].cnt=Tr[p].len*(c^1);
		return ;
	}
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyCover(ls,l,r,c);
	if(mid<r) modifyCover(rs,l,r,c);
	pushUp(p);
}
int queryCnt(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].cnt;
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1,res=0;
	if(l<=mid) res+=queryCnt(ls,l,r);
	if(mid<r) res+=queryCnt(rs,l,r);
	return res;
}
void modifyFix(int l,int r,int k)
{
	if(!k) return ;
	int res=l,_l=l;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(queryCnt(1,_l,mid)<=k) res=mid,l=mid+1;
		else r=mid-1;
	}
	modifyCover(1,_l,res,1);
}
St queryVal(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p];
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(mid<l) return queryVal(rs,l,r);
	if(r<=mid) return queryVal(ls,l,r);
	St L=queryVal(ls,l,r),R=queryVal(rs,l,r),res;
	res.cnt=L.cnt+R.cnt;
	res.lx=L.lx,res.rx=R.rx;
	if(L.len==L.lx) res.lx+=R.lx;
	if(R.len==R.rx) res.rx+=L.rx;
	res.val=std::max(std::max(L.val,R.val),L.rx+R.lx);
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	build(1,1,N);
	for(int opt,ql,qr;Q--;)
	{
		read(opt,ql,qr);
		if(opt==0) modifyCover(1,ql,qr,0);
		else if(opt==1)
		{
			int l,r;read(l,r);int res=qr-ql+1-queryCnt(1,ql,qr);
			modifyCover(1,ql,qr,0),modifyFix(l,r,res);
		}
		else write(queryVal(1,ql,qr).val,'\n');
	}
	return 0;
}
/*

*/

山无遮，海无拦

很久没有唠嗑了呢，其实珂朵莉树能做的题说少，那是少之又少，说多，却又无穷无尽，在大多数有区间重构的题中，珂朵莉树都能拿到很多分数，但一般而言都拿不满，所以，珂朵莉树的实际运用也就只有骗分这一环了，顺便也把 std::set 学了一下。

开始停课了，我也有在准备之后的课程了，之所以还在继续断断续续整 其实还是因为没有办法在不受监视的前提下做自己的事情，我真的有在努力啊，只不过不够。就像前阵子我对自己的评价，从不缺直言不讳的批判，却从未一往无前的行动。如果真这样我还真出生啊。

所以，即使繁花落尽，我们永不放弃。

相关文章