简述难点
这种题极其友（(mathrm{e})）好（(mathrm{xin})），基本上就是 (mathrm{pushup})，(mathrm{build})，(mathrm{pushdown})，(mathrm{update})，(mathrm{query})，传统线段树五套餐伺候，但是要维护的信息极多，关键还不太能想到要怎么样维护信息，而且维护代码极长。
题目一 子区间最大公约数
NC15557 连续区间的最大公约数
这道题没有修改，只有查询。查询最大公约数还是比较简单的，但是查询子区间的最大公约数也等于整个区间的最大公约数的数量，这就不这么快乐了。假设我们两个孩子区间的 (gcd) 和 他们子区间满足条件的数目 (cnt_l,cnt_r)，要合并成父亲区间，父亲区间的 (gcd) 就是对两孩子的 (gcd) 再取一个 (gcd) ，但是满足这个新的 (gcd) 的子区间数目没有办法仅从孩子的 (cnt_l,cnt_r) 解析出，因为子区间可能是两个孩子区间的一部分,这里我就记这种情况为“中间情况”。所以我们需要在节点中保存更多的信息来维护出“中间情况”。
有一个重要结论，也是做这道题最最关键的一个结论，就是随着区间变长， (gcd) 一定是不上升的 。也就是说，一个从端点扩展区间的 (gcd) 不可能是中间高两边低的，也不可能是两边高中间低的。那么，我们维护两个向量 (l、r) ，分别表示从区间左端点和右端点向另一端扩展的 (gcd) 变化情况。先给出定义代码：
struct myPair{
ll gcd, len; //扩展长度
};
struct node{
vector<myPair>l,r;
ll noGcdCnt = 0, gcd = 0,len = 0; //不是区间gcd的区间数目，区间gcd，区间长度
}t[maxn<<2];
先解释 (vector) 的含义，它的元素类型是我自定义的一个类型。下面的表格可以直观解释它的用法：
可以看出 (l) 是区间 ([1,i],iin[1,7]) 的 (gcd) 和能维持的长度 (len) ，在这个例子中 (l) 向量有 (5) 个元素; (r) 意义类似,是从右往左进行扩展。得到了从端点向中间扩展的 (gcd) 变化情况，加上一个 (mathrm{noGcdCnt}) 变量表示不是这个区间 (gcd) 的区间数目,即区间内部的情况，这三者就可以求出合并后新区间的 (mathrm{noGcdCnt}) 。也就是说，我们通过两孩子向量的扩展求出“中间情况”，通过两孩子的 (mathrm{noGcdCnt}) 求出在孩子区间内部的其他情况。来分析一下这个合并代码求 (mathrm{noGcdCnt}) 的那部分（还有一部分要求合并的向量，先不写），需要用到结构体运算符重载的知识，不会的可以查一下这方面的知识。
node operator+(const node & rr)const{
node fa; //用于返回的合并节点
fa.gcd = Gcd(gcd, rr.gcd); //新区间gcd是两节点的gcd再取gcd
fa.len = len + rr.len; //长度直接加
/*计算noGcdCnt部分：
* ①判断孩子的gcd是否等于父亲的gcd，等于就直接加上原来的noGcdCnt，
* ②否则孩子任何一个子区间的gcd都不可能等于父亲的gcd，因为父亲的gcd一定是最小的，
* 孩子区间的gcd一定大于等于父亲区间的gcd，
* 假如孩子的一个子区间gcd等于父亲的gcd，但是整体的gcd却大于这个子区间，这是不可能的
* 所以直接加上孩子所有子区间的数目，即(len + 1) * len / 2
* */
fa.noGcdCnt += (fa.gcd == gcd) ? noGcdCnt : (len + 1) * len / 2;
fa.noGcdCnt += (fa.gcd == rr.gcd) ? rr.noGcdCnt : (rr.len + 1) * rr.len / 2;
/*计算“中间情况”
* ① tot记录右区间rr从左端点扩展的子区间 和 左区间从右端点扩展的子区间
* 构成的中间区间的gcd不等于父亲gcd的情况下，右区间rr从左端点扩展的子区间长度(耐心理解一下)。
* ②last记录右区间rr的向量l 最后一个满足上述情况的向量下标。
*/
ll tot = rr.len,last = rr.l.size()-1;
//左区间从它的右端点向左扩展
For(i,0,r.size()-1) {
//子区间构成的区间的gcd如果等于父亲的gcd，减去
while(last >= 0 && Gcd(rr.l[last].gcd,r[i].gcd) == fa.gcd ) tot -= rr.l[last--].len;
//否则加上子区间的子区间所有不等于父亲gcd的数目
fa.noGcdCnt += r[i].len * tot;
}
return fa;
}
可能你会不太理解后面怎么计算“中间情况”，为什么不是两个向量同时从中间开始扩展，而是右区间向量一开始就在另一端？原因就是这样可以保证不漏区间的情况下时间复杂度最短。还记得上面那个结论吗？随着区间变长， (gcd) 一定是不上升的。所以如果下面这个条件成立：
Gcd(rr.l[last].gcd,r[i].gcd) == fa.gcd
那么对于所有大于等于 (i) 的左区间向量与右区间构成的中间区间 (gcd) 一定等于父亲的 (gcd) ，因为如果不等于的话只有可能是比父亲的 (gcd) 要小，这是不可能的，因为父亲的 (gcd) 已经是最小的了（区间长度最长），而这部分区间我们是要减掉的。所以减掉是正确的，因为后面用不到了。这样时间复杂度就是两个向量的长度和了。
来看一下这个帮了我们大忙的向量是怎么维护出来的,会比刚才维护 (mathrm{noGcdCnt}) 好理解。
//父亲先继承左区间的左向量，右区间的右向量
fa.l = l, fa.r = rr.r;
//维护父亲左向量
For(i,0,rr.l.size()-1)
//如果右区间的左向量的一个区间是父亲左向量的倍数（注意谁是谁的倍数），长度延长
if(rr.l[i].gcd % fa.l.back().gcd == 0) fa.l.back().len += rr.l[i].len;
//否则，加入新向量
else fa.l.push_back({Gcd(rr.l[i].gcd, fa.l.back().gcd), rr.l[i].len} );
//维护父亲右向量，类似
For(i,0,r.size()-1)
if(r[i].gcd % fa.r.back().gcd == 0) fa.r.back().len += r[i].len;
else fa.r.push_back({Gcd(r[i].gcd, fa.r.back().gcd), r[i].len} );
这里就是模拟一下扩展过程就行了，注意延长的条件。
剩下的和普通线段树差不多，没了修改就不需要 (mathrm{pushdown}) 和懒标记了。注意我是在建树的时候读入的，查询的时候返回的是一个节点。
(Code):
#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define ls now<<1
#define rs now<<1|1
#define mid (l+r)/2
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef long long ll;
typedef __int128 lll;
const int maxn = 1e5+9;
int n,m,num[maxn];
ll Gcd(ll a,ll b){
if(a == 0) return b;
if(b == 0) return a;
while(b^=a^=b^=a%=b);
return a;
}
struct myPair{
ll gcd, len;
};
struct node{
vector<myPair>l,r;
ll noGcdCnt = 0, gcd = 0,len = 0;//不是区间gcd的区间数目，区间gcd，区间长度
//重载 + 运算符，用于合并本节点（左孩子）和另一个结点rr（右孩子），注意本节点在左边，rr在右边，返回新节点
node operator+(const node & rr)const{
node fa; //用于返回的合并节点
fa.gcd = Gcd(gcd, rr.gcd); //新区间gcd是两节点的gcd再取gcd
fa.len = len + rr.len; //长度直接加
/*计算noGcdCnt部分：
* ①判断孩子的gcd是否等于父亲的gcd，等于就直接加上原来的noGcdCnt，
* ②否则孩子任何一个子区间的gcd都不可能等于父亲的gcd，因为父亲的gcd一定是最小的，
* 孩子区间的gcd一定大于等于父亲区间的gcd，
* 假如孩子的一个子区间gcd等于父亲的gcd，但是整体的gcd却大于这个子区间，这是不可能的
* 所以直接加上孩子所有子区间的数目，即(len + 1) * len / 2
* */
fa.noGcdCnt += (fa.gcd == gcd) ? noGcdCnt : (len + 1) * len / 2;
fa.noGcdCnt += (fa.gcd == rr.gcd) ? rr.noGcdCnt : (rr.len + 1) * rr.len / 2;
/*计算“中间情况”
* ① tot记录右区间rr从左端点扩展的子区间 和 左区间从右端点扩展的子区间
* 构成的中间区间的gcd不等于父亲gcd的情况下，右区间rr从左端点扩展的子区间长度(耐心理解一下)。
* ②last记录右区间rr的向量l 最后一个满足上述情况的向量下标。
*/
ll tot = rr.len,last = rr.l.size()-1;
//左区间从它的右端点向左扩展
For(i,0,r.size()-1) {
//子区间构成的区间的gcd如果等于父亲的gcd，减去
while(last >= 0 && Gcd(rr.l[last].gcd,r[i].gcd) == fa.gcd ) tot -= rr.l[last--].len;
//否则加上子区间的子区间所有不等于父亲gcd的数目
fa.noGcdCnt += r[i].len * tot;
}
//父亲先继承左区间的左向量，右区间的右向量
fa.l = l, fa.r = rr.r;
//维护父亲左向量
For(i,0,rr.l.size()-1)
//如果右区间的左向量的一个区间是父亲左向量的倍数（注意谁是谁的倍数），长度延长
if(rr.l[i].gcd % fa.l.back().gcd == 0) fa.l.back().len += rr.l[i].len;
//否则，加入新向量
else fa.l.push_back({Gcd(rr.l[i].gcd, fa.l.back().gcd), rr.l[i].len} );
//维护父亲右向量，类似
For(i,0,r.size()-1)
if(r[i].gcd % fa.r.back().gcd == 0) fa.r.back().len += r[i].len;
else fa.r.push_back({Gcd(r[i].gcd, fa.r.back().gcd), r[i].len} );
return fa;
}
}t[maxn<<2];
void build(int now,int l,int r){
if(l == r){
t[now].len = 1;
t[now].noGcdCnt = 0;
cin>>t[now].gcd; //从这里读入数据，一个数gcd就是它本身
t[now].l.clear();
t[now].r.clear();
t[now].l.push_back({t[now].gcd,1});t[now].r.push_back({t[now].gcd,1});
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
t[now] = t[ls] + t[rs]; //合并，相当于pushup
}
//注意返回的是一个节点
node query(int now,int l,int r,int x,int y){
if(x <= l&& r <= y ) return t[now];
node lef,rig;
rig.len = lef.len = -1;
if(x <= mid) lef = query(ls,l,mid,x,y);
if(y > mid) rig = query(rs,mid+1,r,x,y);
if(lef.len == -1) return rig; //无左区间
else if(rig.len == -1) return lef; //无右区间
return lef + rig; //左右区间都有，合并
}
int main(){
speedUp_cin_cout
int T,cas=0;int l,r;
cin>>T;
while( T-- ){
cout<<"Case #"<<(++cas)<<":"<<endl;
cin>>n;
build(1,1,n);
cin>>m;
while( m-- ){
cin>>l>>r;
node ans=query(1,1,n,l,r);
//区间左右可能的子区间数 - 不等于gcd的子区间数 = 等于gcd的子区间数
cout<<ans.gcd<<" "<<(1ll * (ans.len + 1) * ans.len / 2 - ans.noGcdCnt)<<endl;
}
}
return 0;
}
题目二 覆盖反转操作
牛客做的人比较少，建议在洛谷上做。
3个操作，2个查询，线段树模拟大题。来想一想要维护什么信息。首先，(0) 和 (1)在这道题中反复转换，所以每种信息肯定给 (0) 和 (1) 分别维护一份，这样在反转时直接 (mathrm{swap}) 交换即可，用一个只有两个元素的数组搞定。
然后考虑查询 (3) 要维护的信息。 可以知道我们要维护每一个区间 (0) 和 (1) 的数目 (cnt) ，这还是比较好操作的，合并的时候直接加起来就好了，如果全部要变成 (0) 或 (1) ，就把这个数目改为区间长度。区间长度就等于 (0) 和 (1) 的数目之和 。
接着思考查询 (4) 要维护的信息，我们要维护最大连续的 (0) 和 (1) 的长度 (len) ，并且要让合并的时候也可以维护这个长度。根据上一道题的经验，我们可以维护两个从端点向中间扩展的最大长度，这样合并的时候最大连续长度就可以取以下三者的最大值：
①左区间 (len_l)。
②右区间 (len_r)。
③“中间情况”：从左区间的右端点向左扩展的最大连续长度 (+) 从右区间的左端点向右扩展最大连续长度。
最后涉及到区间修改，我们还要有一个状态懒标记 (state) ，我这里定义了它的四种情况：
① (-1) 表示没有发生过修改的状态。
② (0) 表示全部覆盖为0的状态。
③ (1) 表示全部覆盖为1的状态。
④ (2) 表示0和1反转状态。
好了，剩下就是漫长的模拟了，需要细心地打下每一个函数，为 (mathrm{debug}) 减轻负担 []~(￣▽￣)~*。看到这里可以自己尝试了，如果有不清楚的可以看我的分部分（介绍顺序不一定是在主函数中定义的顺序）讲解。
首先是节点结构体定义和建树部分：
struct node{
//状态，0或1连续的长度，0或1的数量，从两边扩展0或1的最大长度
int state,len[2],cnt[2],l[2],r[2];
}t[maxn<<2];
void build(int now,int l,int r){
if(l == r){
bool b; cin >> b;
//读入原序列0或1，!b表示取相反，0->1,1->0，也可以用异或
t[now].len[b] = t[now].cnt[b] = t[now].l[b] = t[now].r[b] = 1;
t[now].len[!b] = t[now].cnt[!b] = t[now].l[!b] = t[now].r[!b] =0;
t[now].state = -1;
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(now);
}
然后是有点烦人的 (mathrm{pushup}) ，注意我推荐是用一个 (for) 循环来节省代码量 ，因为 (0) 和 (1) 是处理是完全一样的，并且检查方便。我之前是复制后把0改成1，(mathrm{WA}) 了好多次才发现是哪里忘记改了。
void pushup(int now){
t[now].state = -1;
int lenL,lenR; //左区间的长度，右区间的长度
lenL = t[ls].cnt[0] + t[ls].cnt[1];
lenR = t[rs].cnt[0] + t[rs].cnt[1];
for(int i = 0;i <= 1;i++){
//0或1的数量
t[now].cnt[i] = t[ls].cnt[i] + t[rs].cnt[i];
//连续的长度在三者取最大
t[now].len[i] = max(t[ls].len[i] ,max(t[rs].len[i],t[ls].r[i]+t[rs].l[i]));
//0或1的延展长度
t[now].l[i] = t[ls].l[i];
t[now].r[i] = t[rs].r[i];
//判断是否左或右区间全是0或1
if(t[ls].l[i] == lenL) t[now].l[i] += t[rs].l[i];
if(t[rs].r[i] == lenR) t[now].r[i] += t[ls].r[i];
}
}
然后是修改和 (mathrm{pushdown}) 操作，更长，需要考虑到懒标记的变换了。
void update(int now,int l,int r,int x,int y,int op){
if(x <= l && r <= y){
//如果命令是全部变成0，或者命令是反转并且原来全是1，执行的结果是一样的
if(op == 0 || (t[now].state == 1 && op == 2)){
t[now].state = 0;
t[now].cnt[0] = t[now].l[0] = t[now].r[0] = t[now].len[0] = r-l+1;
t[now].cnt[1] =t[now].l[1] = t[now].r[1] = t[now].len[1] = 0;
}else if(op == 1|| (t[now].state == 0 && op == 2)){
t[now].state = 1;
t[now].cnt[1] = t[now].l[1] = t[now].r[1] = t[now].len[1] = r-l+1;
t[now].cnt[0] =t[now].l[0] = t[now].r[0] = t[now].len[0] = 0;
}else{
if(t[now].state == 2) t[now].state = -1;
else t[now].state = 2;
swap(t[now].l[0],t[now].l[1]);swap(t[now].r[0],t[now].r[1]);
swap(t[now].cnt[0],t[now].cnt[1]);swap(t[now].len[0],t[now].len[1]);
}
return;
}
if(t[now].state != -1) pushdown(now, r - l + 1);
if(x <= mid) update(ls,l,mid,x,y,op);
if(y > mid) update(rs,mid+1,r,x,y,op);
pushup(now);
}
void pushdown(int now,int len){
//全是0或者1状态
if(t[now].state == 0 || t[now].state == 1)
for(int i = 0;i <= 1;i++){
if(t[now].state == i){
t[ls].state = t[rs].state = i;
t[ls].len[i] = t[ls].r[i] = t[ls].l[i] = t[ls].cnt[i] = len-len/2;
t[rs].len[i] = t[rs].r[i] = t[rs].l[i] = t[rs].cnt[i] = len/2;
t[ls].len[i^1] = t[ls].r[i^1] = t[ls].l[i^1] = t[ls].cnt[i^1] = 0;
t[rs].len[i^1] = t[rs].r[i^1] = t[rs].l[i^1] = t[rs].cnt[i^1] = 0;
}
}
//全部反转状态
else{
//如果原来就处于反转状态了，就变成正常状态的-1
if(t[ls].state == 2) t[ls].state = -1;
//如果原来是0或者1，就变成相反的状态，0变成1,1,变成0
else if(t[ls].state != -1)t[ls].state ^= 1;
//否则，就是从正常状态变成反转状态2
else t[ls].state = 2;
//右孩子同理处理
if(t[rs].state == 2) t[rs].state = -1;
else if(t[rs].state != -1)t[rs].state ^= 1;
else t[rs].state = 2;
//全部交换，8个swap，左孩子4个，右孩子4个
swap(t[ls].l[0],t[ls].l[1]);swap(t[ls].r[0],t[ls].r[1]);
swap(t[ls].cnt[0],t[ls].cnt[1]);swap(t[ls].len[0],t[ls].len[1]);
swap(t[rs].l[0],t[rs].l[1]);swap(t[rs].r[0],t[rs].r[1]);
swap(t[rs].cnt[0],t[rs].cnt[1]);swap(t[rs].len[0],t[rs].len[1]);
}
t[now].state = -1;
}
然后是两个查询操作：
//查询区间[x,y]中1的数目
int query_tot(int now,int l,int r,int x,int y){
if(x <= l && r <= y) return t[now].cnt[1];
if(t[now].state != -1) pushdown(now, r - l + 1);
int ans = 0;
if(x <= mid) ans += query_tot(ls,l,mid,x,y);
if(y > mid) ans+= query_tot(rs,mid+1,r,x,y);
return ans;
}
//查询区间[x,y]中连续的1最长长度，返回节点
node query_len(int now, int l, int r, int x, int y){
if(x <= l && r <= y) return t[now];
if(t[now].state != -1) pushdown(now, r - l + 1);
int lenL,lenR;
node fa,lef,rig;
if(x <= mid) lef = query_len(ls,l,mid,x,y);
if(y > mid) rig = query_len(rs,mid+1,r,x,y);
//和pushup合并类似
if( x <= mid && y > mid){
lenL = lef.cnt[0] + lef.cnt[1];
lenR = rig.cnt[0] + rig.cnt[1];
for(int i = 0;i <= 1;i++){
//0或1的数量
fa.cnt[i] = lef.cnt[i] + rig.cnt[i];
//连续的长度在三者取最大
fa.len[i] = max(lef.len[i] , max(rig.len[i], lef.r[i] + rig.l[i]));
//0或1的延展长度
fa.l[i] = lef.l[i], fa.r[i] = rig.r[i];
//判断是否左或右区间全是0或1
if(lef.l[i] == lenL) fa.l[i] += rig.l[i];
if(rig.r[i] == lenR) fa.r[i] += lef.r[i];
}
return fa;
}else if(x <= mid) return lef;
else if(y > mid) return rig;
}
主函数比较简单，我直接给出完整代码了。
(Code):
#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define ls now<<1
#define rs now<<1|1
#define mid (l+r)/2
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
const int maxn = 1e5+9;
struct node{
//状态，0或1连续的长度，0或1的数量，从两边扩展0或1的最大长度
int state,len[2],cnt[2],l[2],r[2];
}t[maxn<<2];
int n,m;
void pushup(int now){
t[now].state = -1;
int lenL,lenR; //左区间的长度，右区间的长度
lenL = t[ls].cnt[0] + t[ls].cnt[1];
lenR = t[rs].cnt[0] + t[rs].cnt[1];
for(int i = 0;i <= 1;i++){
//0或1的数量
t[now].cnt[i] = t[ls].cnt[i] + t[rs].cnt[i];
//连续的长度在三者取最大
t[now].len[i] = max(t[ls].len[i] ,max(t[rs].len[i],t[ls].r[i]+t[rs].l[i]));
//0或1的延展长度
t[now].l[i] = t[ls].l[i];
t[now].r[i] = t[rs].r[i];
//判断是否左或右区间全是0或1
if(t[ls].l[i] == lenL) t[now].l[i] += t[rs].l[i];
if(t[rs].r[i] == lenR) t[now].r[i] += t[ls].r[i];
}
}
void pushdown(int now,int len){
//全是0或者1状态
if(t[now].state == 0 || t[now].state == 1)
for(int i = 0;i <= 1;i++){
//全为0或者1
if(t[now].state == i){
t[ls].state = t[rs].state = i;
t[ls].len[i] = t[ls].r[i] = t[ls].l[i] = t[ls].cnt[i] = len-len/2;
t[rs].len[i] =t[rs].r[i] = t[rs].l[i] = t[rs].cnt[i] = len/2;
t[ls].len[i^1] =t[ls].r[i^1] = t[ls].l[i^1] = t[ls].cnt[i^1] = 0;
t[rs].len[i^1] =t[rs].r[i^1] = t[rs].l[i^1] = t[rs].cnt[i^1] = 0;
}
}
//全部反转状态
else{
//如果原来就处于反转状态了，就变成正常状态的-1
if(t[ls].state == 2) t[ls].state = -1;
//如果原来是0或者1，就变成相反的状态，0变成1,1,变成0
else if(t[ls].state != -1)t[ls].state ^= 1;
//否则，就是从正常状态变成反转状态2
else t[ls].state = 2;
//右孩子同理处理
if(t[rs].state == 2) t[rs].state = -1;
else if(t[rs].state != -1)t[rs].state ^= 1;
else t[rs].state = 2;
//全部交换，8个swap，左孩子4个，右孩子4个
swap(t[ls].l[0],t[ls].l[1]);swap(t[ls].r[0],t[ls].r[1]);
swap(t[ls].cnt[0],t[ls].cnt[1]);swap(t[ls].len[0],t[ls].len[1]);
swap(t[rs].l[0],t[rs].l[1]);swap(t[rs].r[0],t[rs].r[1]);
swap(t[rs].cnt[0],t[rs].cnt[1]);swap(t[rs].len[0],t[rs].len[1]);
}
t[now].state = -1;
}
void build(int now,int l,int r){
if(l == r){
bool b; cin >> b; //读入原序列0或1，!b表示取相反，0->1,1->0，也可以用异或
t[now].len[b] = t[now].cnt[b] = t[now].l[b] = t[now].r[b] = 1;
t[now].len[!b] = t[now].cnt[!b] = t[now].l[!b] = t[now].r[!b] =0;
t[now].state = -1;
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(now);
}
void update(int now,int l,int r,int x,int y,int op){
if(x <= l && r <= y){
//如果命令是全部变成0，或者命令是反转并且原来全是1，执行的结果是一样的
if(op == 0 || (t[now].state == 1 && op == 2)){
t[now].state = 0;
t[now].cnt[0] = t[now].l[0] = t[now].r[0] = t[now].len[0] = r-l+1;
t[now].cnt[1] =t[now].l[1] = t[now].r[1] = t[now].len[1] = 0;
}else if(op == 1|| (t[now].state == 0 && op == 2)){
t[now].state = 1;
t[now].cnt[1] = t[now].l[1] = t[now].r[1] = t[now].len[1] = r-l+1;
t[now].cnt[0] =t[now].l[0] = t[now].r[0] = t[now].len[0] = 0;
}else{
if(t[now].state == 2) t[now].state = -1;
else t[now].state = 2;
swap(t[now].l[0],t[now].l[1]);swap(t[now].r[0],t[now].r[1]);
swap(t[now].cnt[0],t[now].cnt[1]);swap(t[now].len[0],t[now].len[1]);
}
return;
}
if(t[now].state != -1) pushdown(now, r - l + 1);
if(x <= mid) update(ls,l,mid,x,y,op);
if(y > mid) update(rs,mid+1,r,x,y,op);
pushup(now);
}
//查询区间[x,y]中1的数目
int query_tot(int now,int l,int r,int x,int y){
if(x <= l && r <= y) return t[now].cnt[1];
if(t[now].state != -1) pushdown(now, r - l + 1);
int ans = 0;
if(x <= mid) ans += query_tot(ls,l,mid,x,y);
if(y > mid) ans+= query_tot(rs,mid+1,r,x,y);
return ans;
}
//查询区间[x,y]中连续的1最长长度
node query_len(int now, int l, int r, int x, int y){
if(x <= l && r <= y) return t[now];
if(t[now].state != -1) pushdown(now, r - l + 1);
int lenL,lenR;
node fa,lef,rig;
if(x <= mid) lef = query_len(ls,l,mid,x,y);
if(y > mid) rig = query_len(rs,mid+1,r,x,y);
//和pushup合并类似
if( x <= mid && y > mid){
lenL = lef.cnt[0] + lef.cnt[1];
lenR = rig.cnt[0] + rig.cnt[1];
for(int i = 0;i <= 1;i++){
//0或1的数量
fa.cnt[i] = lef.cnt[i] + rig.cnt[i];
//连续的长度在三者取最大
fa.len[i] = max(lef.len[i] , max(rig.len[i], lef.r[i] + rig.l[i]));
//0或1的延展长度
fa.l[i] = lef.l[i], fa.r[i] = rig.r[i];
//判断是否左或右区间全是0或1
if(lef.l[i] == lenL) fa.l[i] += rig.l[i];
if(rig.r[i] == lenR) fa.r[i] += lef.r[i];
}
return fa;
}else if(x <= mid) return lef;
else if(y > mid) return rig;
}
int main(){
speedUp_cin_cout
cin>>n>>m;int op,l,r;
build(1,1,n);
For(i,1,m){
cin>>op>>l>>r;
if(op <= 2) update(1,1,n,l+1,r+1,op);
else if(op == 3) cout<<query_tot(1,1,n,l+1,r+1)<<endl;
else cout<<query_len(1,1,n,l+1,r+1).len[1]<<endl;
}
return 0;
}
这道题最好还是自己打过一遍，可以大大提高自己对线段树的理解。如果有发现哪里有笔误或者代码问题都可以找我，我也只是一个刚刚学线段树不够两周的小蒟蒻，希望得到各位的指点。