妹子求调线段树,有hack数据但是找不出来哪里不对/kk

P2572 [SCOI2010] 序列操作

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);即可


|