LonginusMonkey @ 2023-08-14 22:55:43
我的做法是线段树，pre1记录前导1，pre0记录前导0，ls0记录后导0，ls1记录后导1，然后这个flag是翻转操作，flag2是一个变为0操作，flag3是一个变为1操作，sum2是这个中间连续的1，sum3是中间连续的0，sum是1的个数
下面打开调试之后，为什么最后的一个4操作，中间过程前导1会比总共答案大，奇怪，求调
#include<bits/stdc++.h>
#define int long long
using namespace std;
int arr[100010];
struct node2{
int suml, sumr, sum;
}temp;
struct node{
int sum, pre0, pre1, ls0, ls1, flag, flag2, flag3, sum2, sum3;
}tree[100010<<3];
void push_up(int l, int r, int index) {
int mid = l + r >> 1;
tree[index].sum = tree[index*2].sum + tree[index*2+1].sum;
if(tree[index*2].sum == mid-l+1) {
tree[index].pre1 = mid-l+1 + tree[index*2+1].pre1;
} else {
tree[index].pre1 = tree[index*2].pre1;
}
if(tree[index*2+1].sum == 0) {
tree[index].pre0 = mid-l+1 + tree[index*2].pre0;
} else {
tree[index].pre0 = tree[index*2+1].pre0;
}
if(tree[index*2+1].sum == r-(mid+1)+1) {
tree[index].ls1 = r-(mid+1)+1 + tree[index*2].ls1;
} else {
tree[index].ls1 = tree[index*2+1].ls1;
}
if(tree[index*2+1].sum == 0) {
tree[index].ls0 = r-(mid+1)+1 + tree[index*2].ls0;
} else {
tree[index].ls0 = tree[index*2+1].ls0;
}
tree[index].sum2 = max(tree[index*2].sum2, max(tree[index*2+1].sum2, tree[index*2].ls1 + tree[index*2+1].pre1));
tree[index].sum3 = max(tree[index*2].sum3, max(tree[index*2+1].sum3, tree[index*2].ls0 + tree[index*2+1].pre0));
}
void push_down(int l, int r, int index) {
if(tree[index].flag2) {
tree[index].flag3 = 0;
tree[index*2].flag3 = 0;
tree[index*2+1].flag3 = 0;
tree[index].flag = 0;
tree[index*2].flag = 0;
tree[index*2+1].flag= 0;
tree[index].sum = 0;
tree[index].pre0 = r-l+1;
tree[index].pre1 = 0;
tree[index*2].flag2 = 1;
tree[index*2+1].flag2 = 1;
tree[index].flag2 = 0;
tree[index].sum2 = 0;
tree[index].ls0 = r-l+1;
tree[index].ls1 = 0;
tree[index].sum3 = r-l+1;
}
if(tree[index].flag3) {
tree[index].flag2 = 0;
tree[index*2].flag2 = 0;
tree[index*2+1].flag2 = 0;
tree[index].flag = 0;
tree[index*2].flag = 0;
tree[index*2+1].flag= 0;
tree[index].sum = r-l+1;
tree[index].pre0 = 0;
tree[index].pre1 = r-l+1;
tree[index*2].flag3 = 1;
tree[index*2+1].flag3 = 1;
tree[index].ls0 = 0;
tree[index].ls1 = r-l+1;
tree[index].flag3 = 0;
tree[index].sum2 = r-l+1;
tree[index].sum3 = 0;
}
if(tree[index].flag) {
tree[index].sum = r-l+1-tree[index].sum;
tree[index*2].flag = !tree[index*2].flag;
tree[index*2+1].flag = !tree[index*2+1].flag;
tree[index].flag = 0;
swap(tree[index].ls0, tree[index].ls1);
swap(tree[index].pre0, tree[index].pre1);
swap(tree[index].sum2, tree[index].sum3);
}
}
void build(int l, int r, int index) {
if(l == r) {
if(arr[l] == 1) {
tree[index].sum3 = 0;
tree[index].sum2 = 1;
tree[index].sum = 1; tree[index].pre0 = 0; tree[index].pre1 = 1; tree[index].ls0 = 0; tree[index].ls1 = 1; tree[index].flag = 0;
} else {
tree[index].sum3 = 1;
tree[index].sum2 = 0;
tree[index].sum = 0; tree[index].pre0 = 1; tree[index].pre1 = 0; tree[index].ls0 = 1; tree[index].ls1 = 0;
}
return;
}
int mid = l + r >> 1;
tree[index].flag = 0; tree[index].flag2 = 0; tree[index].flag3 = 0;
build(l, mid, index*2); build(mid+1, r, index*2+1);
push_up(l, r, index);
}
void modify1(int l, int r, int index, int left, int right) {
push_down(l, r, index);
if(left > r || right < l) {return;}
if(l>=left && right >= r) {tree[index].flag2=1; return;}
int mid = l + r >> 1;
modify1(l, mid, index*2, left, right); modify1(mid+1, r, index*2+1, left, right);
push_down(l, mid, index*2); push_down(mid+1, r, index*2+1);
push_up(l, r, index);
}
void modify2(int l, int r, int index, int left, int right) {
push_down(l, r, index);
if(left > r || right < l) {return;}
if(l>=left && r <= right) {tree[index].flag3=1; return;}
int mid = l + r >> 1;
modify2(l, mid, index*2, left, right); modify2(mid+1, r, index*2+1, left, right);
push_down(l, mid, index*2); push_down(mid+1, r, index*2+1);
push_up(l, r, index);
}
void modify3(int l, int r, int index, int left, int right) {
push_down(l, r, index);
if(left > r || right < l) {return;}
if(l>=left && r <= right) {tree[index].flag=1; return;}
int mid = l + r >> 1;
modify3(l, mid, index*2, left, right); modify3(mid+1, r, index*2+1, left, right);
push_down(l, mid, index*2); push_down(mid+1, r, index*2+1);
push_up(l, r, index);
}
int sum(int l, int r, int index, int left, int right) {
push_down(l, r, index);
if(l > right || r < left) return 0;
if(l >= left && r <= right) return tree[index].sum;
int mid = l + r >> 1;
int ans = sum(l, mid, index*2, left, right) + sum(mid+1, r, index*2+1, left, right);
return ans;
}
node2 sum2(int l, int r, int index, int left, int right) {
push_down(l, r, index);
temp.sum = 0; temp.suml = 0; temp.sumr = 0;
if(l > right || r < left) return temp;
if(l >= left && r <= right) {
temp.sum = tree[index].sum2;
temp.suml = tree[index].pre1;
temp.sumr = tree[index].ls1;
return temp;
}
int mid = l + r >> 1;
node2 temp1 = sum2(l, mid, index*2, left, right), temp2 = sum2(mid+1, r, index*2+1, left, right);
node2 tempans;
// cout << temp1.sum << "pp" << temp2.sum << "pp" << temp1.sumr + temp2.suml << endl;
tempans.sum = max(temp1.sum, max(temp2.sum, temp1.sumr + temp2.suml));
if(temp1.sum == mid-l+1) {
tempans.suml = temp1.sum + temp2.suml;
} else {
tempans.suml = temp1.suml;
}
if(temp2.sum == r-(mid+1)+1) {
tempans.sumr = temp2.sum + temp1.sumr;
} else {
tempans.sumr = temp2.sumr;
}
// cout << tempans.sum << "d" << tempans.suml << "d" << tempans.sumr << "d" << l << "d" << r << endl;
return tempans;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
for(int i=1; i<=n; ++i) {
cin >> arr[i];
}
build(1, n, 1);
while(m--) {
int opt; cin >> opt;
if(opt == 0) {
int left, right; cin >> left >> right;
left++; right++;
modify1(1,n,1,left,right);
} else if(opt == 1) {
int left, right; cin >> left >> right;
left++; right++;
modify2(1,n,1,left,right);
} else if(opt == 2) {
int left, right; cin >> left >> right;
left++; right++;
modify3(1,n,1,left,right);
} else if(opt == 3) {
int left, right; cin >> left >> right;
left++; right++;
cout << sum(1, n, 1, left, right) << endl;
} else if(opt == 4) {
int left, right; cin >> left >> right;
left++; right++;
cout << sum2(1, n, 1, left, right).sum << endl;
}
// for(int i=1; i<=n; ++i) {
// cout << sum(1, n, 1, i, i) << "f";
// }
// cout << endl;
}
return 0;
}
/*
input:
10 6
0 0 0 1 1 0 1 0 1 1
1 3 8
0 6 7
2 1 9
3 1 8
3 1 8
4 1 7
ans:
4
4
2
*/