题目：下列操作
Change operations:
0 a b change all characters into '0's in [a , b]
1 a b change all characters into '1's in [a , b]
2 a b change all '0's into '1's and change all '1's into '0's in [a, b]
Output operations:
3 a b output the number of '1's in [a, b]
4 a b output the length of the longest continuous '1' string in [a , b]
思路： 基础 区间 合并 不过操作比较多， 题目要求查询最长的 1 因为有异或 也要记下最长的 0
#include <iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#define N 100050
using namespace std;
int flag[N * ], Xor[N * ], sum[N * ];
int a[N];
int lsum[][N * ], rsum[][N * ], msum[][N * ];
int max(int x, int y) {
return x > y ? x : y;
}
void pushup(int i, int l, int r) {
int mid = (l + r) >> ;
sum[i] = sum[i << ] + sum[i << | ];
for (int j = ; j < ; ++j) {
lsum[j][i] = lsum[j][i << ];
rsum[j][i] = rsum[j][i << | ];
if (lsum[j][i] == mid - l + )
lsum[j][i] += lsum[j][i << | ];
if (rsum[j][i] == r - mid)
rsum[j][i] += rsum[j][i << ];
msum[j][i] = max(msum[j][i << ], msum[j][i << | ]);
msum[j][i] = max(msum[j][i], rsum[j][i << ] + lsum[j][i << | ]);
}
}
void pushdown(int i, int l, int r) {
if (flag[i] != -) {
int mid = (l + r) >> ;
flag[i << ] = flag[i << | ] = flag[i];
Xor[i << ] = Xor[i << | ] = ;
sum[i << ] = (mid - l + ) * flag[i];
sum[i << | ] = (r - mid) * flag[i];
lsum[flag[i]][i << ] = rsum[flag[i]][i << ] = msum[flag[i]][i << ]
= mid - l + ;
lsum[flag[i]][i << | ] = rsum[flag[i]][i << | ] = msum[flag[i]][i
<< | ] = r - mid;
lsum[ - flag[i]][i << ] = rsum[ - flag[i]][i << ] = msum[
- flag[i]][i << ] = ;
lsum[ - flag[i]][i << | ] = rsum[ - flag[i]][i << | ] = msum[
- flag[i]][i << | ] = ;
flag[i] = -; }
if (Xor[i] != ) {
int mid = (l + r) >> ;
Xor[i << ] ^= ;
Xor[i << | ] ^= ;
sum[i << ] = (mid - l + ) - sum[i << ];
sum[i << | ] = (r - mid) - sum[i << | ];
swap(lsum[][i << ], lsum[][i << ]);
swap(rsum[][i << ], rsum[][i << ]);
swap(msum[][i << ], msum[][i << ]);
swap(lsum[][i << | ], lsum[][i << | ]);
swap(rsum[][i << | ], rsum[][i << | ]);
swap(msum[][i << | ], msum[][i << | ]);
Xor[i] = ;
}
} void build(int l, int r, int i) {
flag[i] = -;
Xor[i] = ;
if (l == r) {
sum[i] = flag[i] = a[l];
msum[a[l]][i] = rsum[a[l]][i] = lsum[a[l]][i] = ;
msum[ - a[l]][i] = rsum[ - a[l]][i] = lsum[ - a[l]][i] = ;
return;
}
int mid = (l + r) >> ;
build(l, mid, i << );
build(mid + , r, i << | );
pushup(i, l, r);
}
void update(int l, int r, int pl, int pr, int type, int i) {
if (l >= pl && r <= pr) {
if (type == ) {
flag[i] = ;
sum[i] = ;
Xor[i] = ;
lsum[][i] = rsum[][i] = msum[][i] = r - l + ;
lsum[][i] = rsum[][i] = msum[][i] = ;
return;
}
if (type == ) { flag[i] = ;
sum[i] = (r-l+);
Xor[i] = ;
lsum[][i] = rsum[][i] = msum[][i] = ;
lsum[][i] = rsum[][i] = msum[][i] = r-l+;
return;
}
if(type==)
{
Xor[i]^=;
sum[i]=(r-l+)-sum[i];
swap(lsum[][i],lsum[][i]);
swap(rsum[][i],rsum[][i]);
swap(msum[][i],msum[][i]);
return;
}
return;
}
pushdown(i,l,r);
int mid=(l+r)>>;
if(pl<=mid)update(l,mid,pl,pr,type,i<<);
if(pr>mid)update(mid+,r,pl,pr,type,i<<|);
pushup(i,l,r);
}
int query1(int l,int r,int pl,int pr,int i)
{
if(l>=pl&&r<=pr)
return sum[i];
pushdown(i,l,r);
int mid=(l+r)>>;
int tmp=;
if(pl<=mid)tmp+=query1(l,mid,pl,pr,i<<);
if(pr>mid)tmp+=query1(mid+,r,pl,pr,i<<|);
pushup(i,l,r);
return tmp;
} int query2(int l,int r,int pl,int pr,int i)
{
if(l>=pl&&r<=pr)
{
return msum[][i];
}
pushdown(i,l,r);
int mid=(l+r)>>;
if(pr<=mid)return query2(l,mid,pl,pr,i<<);
else if(pl>mid)return query2(mid+,r,pl,pr,i<<|);
else
{
int tmp=;
if(mid-rsum[][i<<]+>=pl)
tmp+=rsum[][i<<];
else
tmp+=mid-pl+;
if(mid+lsum[][i<<|]<=pr)
tmp+=lsum[][i<<|];
else
tmp+=pr-mid; int maxn1=query2(l,mid,pl,mid,i<<);
int maxn2=query2(mid+,r,mid+,pr,i<<|);
tmp=max(tmp,maxn1);
tmp=max(tmp,maxn2);
return tmp;
}
}
int main() {
int n,m,tt;
scanf("%d",&tt);
while(tt--)
{
scanf("%d%d",&n,&m);
for(int i=;i<n;++i)
scanf("%d",&a[i]);
n--;
build(,n,); while(m--)
{
int x,y,z;
scanf("%d%d%d",&z,&x,&y);
if(z<=)update(,n,x,y,z,);
else if(z==)
{ printf("%d\n",query1(,n,x,y,));
}
else
printf("%d\n",query2(,n,x,y,));
}
}
return ;
}