1_1_1_1_1_1_ @ 2024-07-30 17:52:21
除了#2和hack外全WA
#include<bits/stdc++.h>
using namespace std;
struct node
{
int sum0, sum1;//共有多少个0,1
int m0, m1;//连续0,1的最长长度
int l0, r0, l1, r1;//l0表示从左起连续0的长度
node(int asum0, int am0, int al0, int ar0 , int asum1 , int am1 , int al1 , int ar1 )
{
sum0 = asum0;
m0 = am0;
l0 = al0;
r0 = ar0;
sum1 = asum1;
m1 = am1;
l1 = al1;
r1 = ar1;
}
node(){
}
}tr[400010];
int n, m;
int a[400010];
int tag[400010];//更改的懒标记,-1表示不需要更改,0表示改为0,1表示改为1
bool tag2[400010];//取反的懒标记
node qufan(node x)//取反一个节点
{
swap(x.sum0, x.sum1);
swap(x.m0, x.m1);
swap(x.l0, x.l1);
swap(x.r0, x.r1);
return x;
}
void push_down(int id, int l, int r)//下放懒标记
{
int mid = (l + r) / 2;
if(tag[id] != -1)//需要更改为0或1
{
int x = tag[id];
tag[id * 2] = x;
tag[id * 2 + 1] = x;
tag[id] = -1;
node g;
int k;
if(x == 0)
{
k = mid - l + 1;
g = node(k, k, k, k, 0, 0, 0, 0);
tr[id * 2] = g;
k = r - mid;
g = node(k, k, k, k, 0, 0, 0, 0);
tr[id * 2 + 1] = g;
}
else
{
k = mid - l + 1;
g = node(0, 0, 0, 0, k, k, k, k);
tr[id * 2] = g;
k = r - mid;
g = node(0, 0, 0, 0, k, k, k, k);
tr[id * 2 + 1] = g;
}
}
if(tag2[id] == 1)//需要取反
{
tr[id * 2] = qufan(tr[id * 2]);
tr[id * 2 + 1] = qufan(tr[id * 2 + 1]);
tag2[id * 2] = 1 - tag2[id * 2];//1变为0,0变为1
tag2[id * 2 + 1] = 1 - tag2[id * 2 + 1];//1变为0,0变为1
tag2[id] = 0;
}
}
node push_up(node x, node y)//合并区间
{
node ans;
ans.sum0 = x.sum0 + y.sum0;
ans.sum1 = x.sum1 + y.sum1;
ans.m0 = max(x.r0 + y.l0, max(x.m0, y.m0));
if(x.sum1 == 0)//左子树全是0
{
ans.l0 = x.sum0 + y.l0;
}
else
{
ans.l0 = x.l0;
}
if(y.sum1 == 0)//右子树全是0
{
ans.r0 = x.r0 + y.sum0;
}
else
{
ans.r0 = y.r0;
}
ans.m1 = max(x.r1 + y.l1, max(x.m1, y.m1));
if(x.sum0 == 0)//左子树全是1
{
ans.l1 = x.sum1 + y.l1;
}
else
{
ans.l1 = x.l1;
}
if(y.sum0 == 0)//右子树全是1
{
ans.r1 = x.r1 + y.sum1;
}
else
{
ans.r1 = y.r1;
}
return ans;
}
void build(int id, int l, int r)//建树
{
if(l == r)
{
if(a[l] == 1)
{
tr[id].sum1 = 1;
tr[id].m1 = 1;
tr[id].l1 = 1;
tr[id].r1 = 1;
}
else
{
tr[id].sum0 = 1;
tr[id].m0 = 1;
tr[id].l0 = 1;
tr[id].r0 = 1;
}
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
tr[id] = push_up(tr[id * 2], tr[id * 2 + 1]);
}
void gengxin_0(int id, int l, int r, int left, int right)//全部改为0
{
if(left <= l && r <= right)
{
if(tag2[id] == 1)
{
tag2[id] = 0;
}
int k = r - l + 1;
tr[id] = node(k, k, k, k, 0, 0, 0, 0);
tag[id] = 0;
return;
}
push_down(id, l, r);
int mid = (l + r) / 2;
if(left <= mid)
{
gengxin_0(id * 2, l, mid, left, right);
}
if(mid < right)
{
gengxin_0(id * 2 + 1, mid + 1, r, left, right);
}
tr[id] = push_up(tr[id * 2], tr[id * 2 + 1]);
}
void gengxin_1(int id, int l, int r, int left, int right)//全部改为1
{
if(left <= l && r <= right)
{
if(tag2[id] == 1)
{
tag2[id] = 0;
}
int k = r - l + 1;
tr[id] = node(0, 0, 0, 0, k, k, k, k);
tag[id] = 1;
return;
}
push_down(id, l, r);
int mid = (l + r) / 2;
if(left <= mid)
{
gengxin_1(id * 2, l, mid, left, right);
}
if(mid < right)
{
gengxin_1(id * 2 + 1, mid + 1, r, left, right);
}
tr[id] = push_up(tr[id * 2], tr[id * 2 + 1]);
}
void gengxin_qufan(int id, int l, int r, int left, int right)//取反
{
if(left <= l && r <= right)
{
tr[id] = qufan(tr[id]);
tag2[id] = 1 - tag2[id];
return;
}
push_down(id, l, r);
int mid = (l + r) / 2;
if(left <= mid)
{
gengxin_qufan(id * 2, l, mid, left, right);
}
if(mid < right)
{
gengxin_qufan(id * 2 + 1, mid + 1, r, left, right);
}
tr[id] = push_up(tr[id * 2], tr[id * 2 + 1]);
}
int ask_sum(int id, int l, int r, int left, int right)//询问1的个数
{
if(left <= l && r <= right)
{
return tr[id].sum1;
}
push_down(id, l, r);
int mid = (l + r) / 2;
int ans = 0;
if(left <= mid)
{
ans = ask_sum(id * 2, l, mid, left, right);
}
if(mid < right)
{
ans += ask_sum(id * 2 + 1, mid + 1, r, left, right);
}
return ans;
}
node ask_d(int id, int l, int r, int left, int right)//询问最长连续1的长度
{
if(left <= l && r <= right)
{
return tr[id];
}
push_down(id, l, r);
int mid = (l + r) / 2;
node x, y;
bool flagx = 0;
bool flagy = 0;
if(left <= mid)
{
flagx = 1;
x = ask_d(id * 2, l, mid, left, right);
}
if(mid < right)
{
flagy = 1;
y = ask_d(id * 2 + 1, mid + 1, r, left, right);
}
if(flagx == 0)
{
return y;
}
if(flagy == 0)
{
return x;
}
return push_up(x, y);
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
memset(tag, -1, sizeof(tag));
build(1, 1, n);
for(int i = 1; i <= m; i++)
{
int op, l, r;
cin >> op >> l >> r;
l++;
r++;
if(op == 0)
{
gengxin_0(1, 1, n, l, r);
}
else if(op == 1)
{
gengxin_1(1, 1, n, l, r);
}
else if(op == 2)
{
gengxin_qufan(1, 1, n, l, r);
}
else if(op == 3)
{
cout << ask_sum(1, 1, n, l, r) << endl;
}
else if(op == 4)
{
node g = ask_d(1, 1, n, l, r);
cout << g.m1 << endl;
}
}
return 0;
}
by wrh316 @ 2024-07-31 09:17:09
代码风格确实良好
by fzy_qwq @ 2024-07-31 10:03:19
@1_1_1_1_11 不如暴力拿30分
by pugong @ 2024-08-09 21:29:20
@1_1_1_1_11 给你组数据
输入:
7 5
0 0 1 1 1 1 0
3 5 6
2 1 5
0 2 6
3 1 4
2 5 6
输出:
1
1