dk_qwq @ 2022-10-28 19:42:55
#include<iostream>
#include<cstdio>
#define inf 0x3f3f3f3f
using namespace std;
template<typename T>
inline T read(){
T x=0,p=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') p=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*p;
}
const int N=1e5+5;
struct Node_t{
int sum;
int L_MAX,R_MAX;
int ans;
Node_t(int siz=0):sum(siz),L_MAX(siz),R_MAX(siz),ans(siz){}
friend Node_t operator+(const Node_t& a,const Node_t& b){
Node_t ans;
ans.sum=a.sum+b.sum;
ans.L_MAX=a.L_MAX,ans.R_MAX=b.R_MAX;
ans.ans=max(max(a.ans,b.ans),a.R_MAX+b.L_MAX);
if(a.L_MAX==a.sum&&a.R_MAX==a.sum&&a.sum) ans.L_MAX+=b.L_MAX;
if(b.L_MAX==b.sum&&b.R_MAX==b.sum&&b.sum) ans.R_MAX+=a.R_MAX;
ans.ans=max(ans.ans,max(ans.L_MAX,ans.R_MAX));
return ans;
}
};
struct tree{
int l,r;
int lazy;
Node_t d[2];
tree():lazy(inf),d(){}
void set_col(int col){
if(col==-1) {swap(d[0],d[1]);return ;}
d[col^1]=Node_t();
d[col]=Node_t(r-l+1);
}
friend tree operator+(const tree& a,const tree& b){
tree ans;
ans.l=a.l,ans.r=b.r;
ans.d[0]=a.d[0]+b.d[0],ans.d[1]=a.d[1]+b.d[1];
return ans;
}
}t[N<<2];
int col[N];
void build(int o,int l,int r){
if(l==r) {
t[o].l=t[o].r=l;
t[o].set_col(col[l]);
return ;
}
int mid=(l+r)>>1;
build(o<<1,l,mid),build(o<<1|1,mid+1,r);
t[o]=t[o<<1]+t[o<<1|1];
}
void push(int o,int col){
t[o].set_col(col);
if(t[o].lazy==-1&&col==-1){
t[o].lazy=inf;
return ;
}
t[o].lazy=col;
}
void pushdown(int o){
if(t[o].lazy==inf) return ;
push(o<<1,t[o].lazy),push(o<<1|1,t[o].lazy);
t[o].lazy=inf;
}
void change(int o,int ql,int qr,int col){
if(ql<=t[o].l&&t[o].r<=qr){
push(o,col);
return ;
}
pushdown(o);
int mid=(t[o].l+t[o].r)>>1;
if(ql<=mid) change(o<<1,ql,qr,col);
if(mid<qr) change(o<<1|1,ql,qr,col);
t[o]=t[o<<1]+t[o<<1|1];
}
int sum(int o,int ql,int qr){
if(ql<=t[o].l&&t[o].r<=qr) return t[o].d[1].sum;
pushdown(o);
int mid=(t[o].l+t[o].r)>>1;
int ans=0;
if(ql<=mid) ans+=sum(o<<1,ql,qr);
if(mid<qr) ans+=sum(o<<1|1,ql,qr);
t[o]=t[o<<1]+t[o<<1|1];
return ans;
}
Node_t ask(int o,int ql,int qr){
if(ql<=t[o].l&&t[o].r<=qr) return t[o].d[1];
pushdown(o);
int mid=(t[o].l+t[o].r)>>1;
Node_t l,r;
if(ql<=mid) l=ask(o<<1,ql,qr);
if(mid<qr) r=ask(o<<1|1,ql,qr);
t[o]=t[o<<1]+t[o<<1|1];
return l+r;
}
int n,Q;
int main() {
// freopen("data.in","r",stdin);
// freopen("P2572.out","w",stdout);
n=read<int>(),Q=read<int>();
for(int i=1;i<=n;i++) col[i]=read<int>();
build(1,1,n);
while(Q--){
int opt=read<int>();
int l=read<int>()+1,r=read<int>()+1;
if(opt==0||opt==1) change(1,l,r,opt);
if(opt==2) change(1,l,r,-1);
if(opt==3) printf("%d\n",sum(1,l,r));
if(opt==4) printf("%d\n",ask(1,l,r).ans);
}
}
.in
10 5
1 1 1 0 1 0 1 0 1 0
1 0 7
2 3 3
2 1 6
0 6 7
3 0 9
.out
3
by dk_qwq @ 2022-10-28 19:43:59
不是妹子,但悬赏关注/kk不是btd
by 155TuT @ 2022-10-28 20:07:47
@dkqwq 建树里面
if(l==r){
t[o].l=t[o].r=l;
t[o].set_col(col[l]);
return ;
}
外面线段左右端点也需要更新
by 155TuT @ 2022-10-28 20:08:34
void build(int o,int l,int r){
t[o].l=l;t[o].r=r;
if(l==r) {
//t[o].l=t[o].r=l;
t[o].set_col(col[l]);
return ;
}
int mid=(l+r)>>1;
build(o<<1,l,mid),build(o<<1|1,mid+1,r);
t[o]=t[o<<1]+t[o<<1|1];
}
by dk_qwq @ 2022-10-28 20:15:31
@155TuT 重载+号了
by 155TuT @ 2022-10-28 20:52:45
@dkqwq 我在发完以后就后悔了,被我看不懂的神犇操作折服
by Phobia @ 2022-10-28 22:14:12
@dkqwq
void change(int o, int ql, int qr, int col) {
if (ql <= t[o].l && t[o].r <= qr) {
push(o, col);
return;
}
pushdown(o);
int mid = (t[o].l + t[o].r) >> 1;
if (ql <= mid) change(o << 1, ql, qr, col);
if (mid < qr) change(o << 1 | 1, ql, qr, col);
t[o] = t[o << 1] + t[o << 1 | 1];
}
改为
void change(int o, int ql, int qr, int col) {
pushdown(o);
if (ql <= t[o].l && t[o].r <= qr) {
push(o, col);
return;
}
int mid = (t[o].l + t[o].r) >> 1;
if (ql <= mid) change(o << 1, ql, qr, col);
if (mid < qr) change(o << 1 | 1, ql, qr, col);
t[o] = t[o << 1] + t[o << 1 | 1];
}
by dk_qwq @ 2022-10-29 07:46:31
@31144bmsh 还是不对
by dk_qwq @ 2022-10-29 07:52:14
已过,在push
函数前面加入if(col==-1&&t[o].lazy!=-1) pushdown(o);
即可