萌新求助qwq只有10分

P2572 [SCOI2010] 序列操作

abjfj @ 2019-10-28 21:51:49

看到题解都是用了两个标记那么只用一个标记可不可以呢

#include<iostream>
#include<cstdio>
#define int long long 
#define maxn 100001
using namespace std;
struct Tree 
{
    int l1,l0,r1,r0,s1,s0,m1,m0;
};
void read(int &x)
{
    x = 0;int f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = (x<<3) + (x<<1) + ch -'0'; 
        ch = getchar();
    }
    x = x*f;
}
int n,m;
Tree t[maxn<<2];int tag[maxn<<2];
//tag == 1 把所有数变为1
//tag == 2 把所有数变为0 
//tag == 3 把所有数取反 
void pushup(int now,int l,int r)
{
    int mid = (l+r)>>1;
    t[now].s1 = t[now<<1].s1 + t[now<<1|1].s1;
    t[now].s0 = t[now<<1].s0 + t[now<<1|1].s0;
    t[now].l0 = t[now<<1].l0;t[now].r0 = t[now<<1|1].r0;
    t[now].l1 = t[now<<1].l1;t[now].r1 = t[now<<1|1].r1;
    t[now].m1 = max(t[now<<1].m1,t[now<<1|1].m1);
    t[now].m1 = max(t[now].m1,t[now<<1].r1 + t[now<<1|1].l1);
    t[now].m0 = max(t[now<<1].m0,t[now<<1|1].m0);
    t[now].m0 = max(t[now].m0,t[now<<1].r0 + t[now<<1|1].l0);
    if(t[now<<1].s1 == (mid-l+1))
    {
        t[now].l1 = t[now<<1].s1 + t[now<<1|1].l1;
    }
    if(t[now<<1|1].s1 == (r-mid))
    {
        t[now].r1 = t[now<<1|1].s1 + t[now<<1].r1;
    }
    t[now].m1 = max(t[now].m1,t[now].l1);t[now].m1 = max(t[now].m1,t[now].r1);
    if(t[now<<1].s1 == 0)
    {
        t[now].l0 = (mid-l+1) + t[now<<1|1].l0;
    }
    if(t[now<<1|1].s1 == 0)
    {
        t[now].r0 = (r-mid) + t[now<<1].r0;
    }
    t[now].m0 = max(t[now].m0,t[now].l0);t[now].m0 = max(t[now].m0,t[now].r0);
}   
void pushdown(int now,int l,int r)
{
    if(l == r)
    {
        tag[now] = 0;
        return;
    }
    int mid = (l+r)>>1;
    if(tag[now] == 1)
    {
        t[now<<1].s0 = t[now<<1].l0 = t[now<<1].r0 = 0;
        t[now<<1].s1 = t[now<<1].r1 = t[now<<1].l1 = (mid-l+1);
        t[now<<1].m1 = (mid-l+1);
        t[now<<1].m0 = 0;
        t[now<<1|1].s0 = t[now<<1|1].l0 = t[now<<1|1].r0 = 0;
        t[now<<1|1].s1 = t[now<<1|1].r1 = t[now<<1|1].l1 = (r-mid);
        t[now<<1|1].m1 = (r-mid);
        t[now<<1|1].m0 = 0;
        tag[now<<1] = tag[now<<1|1] = 1;
        tag[now] = 0;
        return;
    }
    if(tag[now] == 2)
    {
        t[now<<1].s0 = t[now<<1].l0 = t[now<<1].r0 = (mid-l+1);
        t[now<<1].s1 = t[now<<1].r1 = t[now<<1].l1 = 0;
        t[now<<1].m1 = 0;
        t[now<<1].m0 = (mid-l+1);
        t[now<<1|1].s0 = t[now<<1|1].l0 = t[now<<1|1].r0 = (r-mid);
        t[now<<1|1].s1 = t[now<<1|1].r1 = t[now<<1|1].l1 = 0;
        t[now<<1|1].m1 = 0;
        t[now<<1|1].m0 = (r-mid);
        tag[now<<1] = tag[now<<1|1] = 2;
        tag[now] = 0;
        return;
    }
    if(tag[now] == 3)
    {
        //分而治之
        // 左！ 
        int templ = t[now<<1].l1,tempr = t[now<<1].r1,temps = t[now<<1].s1,tempm = t[now<<1].m1;
        t[now<<1].l1 = t[now<<1].l0;t[now<<1].r1 = t[now<<1].r0;t[now<<1].s1 = t[now<<1].s0;
        t[now<<1].l0 = templ;t[now<<1].r0 = tempr;t[now<<1].s0 = temps;
        t[now<<1].m1 = t[now<<1].m0;
        t[now<<1].m0 = tempm;
        // 右！ 
        templ = t[now<<1|1].l1,tempr = t[now<<1|1].r1,temps = t[now<<1|1].s1,tempm = t[now<<1|1].m1;
        t[now<<1|1].l1 = t[now<<1|1].l0;t[now<<1|1].r1 = t[now<<1|1].r0;t[now<<1|1].s1 = t[now<<1|1].s0;
        t[now<<1|1].l0 = templ;t[now<<1|1].r0 = tempr;t[now<<1|1].s0 = temps;
        t[now<<1|1].m1 = t[now<<1|1].m0;
        t[now<<1|1].m0 = tempm;
        tag[now<<1] = tag[now<<1|1] = 3;
        tag[now] = 0;
        return;
    }
}
void build(int now,int l,int r)
{
    if(l == r)
    {
        read(t[now].s1);
        if(t[now].s1 == 1)
        {
            t[now].l1 = t[now].r1 = t[now].m1 = 1;
        }
        else
        {
            t[now].s0 = t[now].l0 = t[now].r0 = t[now].m0 = 1;
        }
        return;
    }
    int mid = (l+r)>>1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    pushup(now,l,r);
}
void change0(int now,int l,int r,int LL,int RR)
{
    if(LL <= l && RR >= r)
    {
        tag[now] = 2;
        t[now].s0 = t[now].l0 = t[now].r0 = (r-l+1);
        t[now].s1 = t[now].r1 = t[now].l1 = 0;
        t[now].m1 = 0;
        t[now].m0 = (r-l+1);
        return;
    }
    if(tag[now])pushdown(now,l,r);
    int mid = (l+r)>>1;
    if(LL <= mid)
    {
        change0(now<<1,l,mid,LL,RR);
    }
    if(RR > mid)
    {
        change0(now<<1|1,mid+1,r,LL,RR);
    }
    pushup(now,l,r);
}
void change1(int now,int l,int r,int LL,int RR)
{
    if(LL <= l && RR >= r)
    {
        tag[now] = 1;
        t[now].s1 = t[now].l1 = t[now].r1 = (r-l+1);
        t[now].s0 = t[now].l0 = t[now].r0 = 0;
        t[now].m1 = (r-l+1);
        t[now].m0 = 0;
        return;
    }
    if(tag[now])pushdown(now,l,r);
    int mid = (l+r)>>1;
    if(LL <= mid)
    {
        change1(now<<1,l,mid,LL,RR);
    }
    if(RR > mid)
    {
        change1(now<<1|1,mid+1,r,LL,RR);
    }
    pushup(now,l,r);
}
void changefan(int now,int l,int r,int LL,int RR)
{
    if(LL <= l && RR >= r)
    {
        tag[now] = 3;
        int templ = t[now].l1,tempr = t[now].r1,temps = t[now].s1,tempm = t[now].m1;
        t[now].l1 = t[now].l0;t[now].r1 = t[now].r0;t[now].s1 = t[now].s0;
        t[now].l0 = templ;t[now].r0 = tempr;t[now].s0 = temps;
        t[now].m1 = t[now].m0;
        t[now].m0 = tempm;
        return;
    }
    if(tag[now])pushdown(now,l,r);
    int mid = (l+r)>>1;
    if(LL <= mid)
    {
        changefan(now<<1,l,mid,LL,RR);
    }
    if(RR > mid)
    {
        changefan(now<<1|1,mid+1,r,LL,RR);
    }
    pushup(now,l,r);
}
int querysum(int now,int l,int r,int LL,int RR)
{
    if(LL <= l && RR >= r)
    {
        return t[now].s1;
    }
    if(tag[now])pushdown(now,l,r);
    int ans = 0;
    int mid = (l+r)>>1;
    if(LL <= mid)
    {
        ans += querysum(now<<1,l,mid,LL,RR);
    }
    if(RR > mid)
    {
        ans += querysum(now<<1|1,mid+1,r,LL,RR);
    }
    return ans;
}
Tree querym(int now,int l,int r,int LL,int RR)
{
    if(LL <= l && RR >= r)
    {
        return t[now];
    }
    if(tag[now])pushdown(now,l,r);
    Tree ans;
    Tree L,R;
    int mid = (l+r)>>1;
    if(LL > mid)
    {
        return querym(now<<1|1,mid+1,r,LL,RR);
    }
    if(RR <= mid)
    {
        return querym(now<<1,l,mid,LL,RR);
    }
    L = querym(now<<1,l,mid,LL,RR);
    R = querym(now<<1|1,mid+1,r,LL,RR);
    ans.m1 = max(L.m1,R.m1);
    ans.m1 = max(ans.m1,L.r1 + R.l1);
    ans.l1 = L.l1;ans.r1 = R.r1;
    if(L.l1 == (mid-l+1))
    {
        ans.l1 = L.l1 + R.l1;
    }
    if(R.r1 == (r-mid))
    {
        ans.r1 = R.r1 + L.r1;
    }
    ans.m1 = max(ans.m1,ans.l1);
    ans.m1 = max(ans.m1,ans.r1);
    return ans;
}
signed main()
{
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout); 
    read(n),read(m);
    build(1,1,n);
    for(int i = 1; i <= m; i++)
    {
        //changefan(1,1,n,1,n);
        //changefan(1,1,n,1,n);
        int opt,l,r;
        read(opt),read(l),read(r);
        l++,r++;
        if(opt == 0)
        {
            change0(1,1,n,l,r);
        }
        if(opt == 1)
        {
            change1(1,1,n,l,r);
        }
        if(opt == 2)
        {
            changefan(1,1,n,l,r);
        }
        if(opt == 3)
        {
            printf("%lld\n",querysum(1,1,n,l,r));
        }
        if(opt == 4)
        {
            printf("%lld\n",querym(1,1,n,l,r).m1);
        }
        //统计有多少个连续的1
        //统计有多少个连续的0 
    }
    return 0;
}

by abjfj @ 2019-10-29 07:52:09

懂了如果只有一个标记的话下传时会影响其他标记。

by abjfj @ 2019-10-29 07:53:36

那么在翻转这个标记下传时先下传其他标记其结果是超时

#include<iostream>
#include<cstdio>
#define int long long 
#define maxn 100001
using namespace std;
struct Tree 
{
    int l1,l0,r1,r0,s1,s0,m1,m0;
};
void read(int &x)
{
    x = 0;int f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = (x<<3) + (x<<1) + ch -'0'; 
        ch = getchar();
    }
    x = x*f;
}
int n,m;
Tree t[maxn<<2];int tag[maxn<<2];
//tag == 1 把所有数变为1
//tag == 2 把所有数变为0 
//tag == 3 把所有数取反 
void pushup(int now,int l,int r)
{
    int mid = (l+r)>>1;
    t[now].s1 = t[now<<1].s1 + t[now<<1|1].s1;
    t[now].s0 = t[now<<1].s0 + t[now<<1|1].s0;
    t[now].l0 = t[now<<1].l0;t[now].r0 = t[now<<1|1].r0;
    t[now].l1 = t[now<<1].l1;t[now].r1 = t[now<<1|1].r1;
    t[now].m1 = max(t[now<<1].m1,t[now<<1|1].m1);
    t[now].m1 = max(t[now].m1,t[now<<1].r1 + t[now<<1|1].l1);
    t[now].m0 = max(t[now<<1].m0,t[now<<1|1].m0);
    t[now].m0 = max(t[now].m0,t[now<<1].r0 + t[now<<1|1].l0);
    if(t[now<<1].s1 == (mid-l+1))
    {
        t[now].l1 = t[now<<1].s1 + t[now<<1|1].l1;
    }
    if(t[now<<1|1].s1 == (r-mid))
    {
        t[now].r1 = t[now<<1|1].s1 + t[now<<1].r1;
    }
    t[now].m1 = max(t[now].m1,t[now].l1);t[now].m1 = max(t[now].m1,t[now].r1);
    if(t[now<<1].s1 == 0)
    {
        t[now].l0 = (mid-l+1) + t[now<<1|1].l0;
    }
    if(t[now<<1|1].s1 == 0)
    {
        t[now].r0 = (r-mid) + t[now<<1].r0;
    }
    t[now].m0 = max(t[now].m0,t[now].l0);t[now].m0 = max(t[now].m0,t[now].r0);
}   
void pushdown(int now,int l,int r)
{
    if(l == r)
    {
        tag[now] = 0;
        return;
    }
    int mid = (l+r)>>1;
    if(tag[now] == 1)
    {
        t[now<<1].s0 = t[now<<1].l0 = t[now<<1].r0 = 0;
        t[now<<1].s1 = t[now<<1].r1 = t[now<<1].l1 = (mid-l+1);
        t[now<<1].m1 = (mid-l+1);
        t[now<<1].m0 = 0;
        t[now<<1|1].s0 = t[now<<1|1].l0 = t[now<<1|1].r0 = 0;
        t[now<<1|1].s1 = t[now<<1|1].r1 = t[now<<1|1].l1 = (r-mid);
        t[now<<1|1].m1 = (r-mid);
        t[now<<1|1].m0 = 0;
        tag[now<<1] = tag[now<<1|1] = 1;
        tag[now] = 0;
        return;
    }
    if(tag[now] == 2)
    {
        t[now<<1].s0 = t[now<<1].l0 = t[now<<1].r0 = (mid-l+1);
        t[now<<1].s1 = t[now<<1].r1 = t[now<<1].l1 = 0;
        t[now<<1].m1 = 0;
        t[now<<1].m0 = (mid-l+1);
        t[now<<1|1].s0 = t[now<<1|1].l0 = t[now<<1|1].r0 = (r-mid);
        t[now<<1|1].s1 = t[now<<1|1].r1 = t[now<<1|1].l1 = 0;
        t[now<<1|1].m1 = 0;
        t[now<<1|1].m0 = (r-mid);
        tag[now<<1] = tag[now<<1|1] = 2;
        tag[now] = 0;
        return;
    }
    if(tag[now] == 3)
    {
        //分而治之
        // 左！ 
        int templ = t[now<<1].l1,tempr = t[now<<1].r1,temps = t[now<<1].s1,tempm = t[now<<1].m1;
        t[now<<1].l1 = t[now<<1].l0;t[now<<1].r1 = t[now<<1].r0;t[now<<1].s1 = t[now<<1].s0;
        t[now<<1].l0 = templ;t[now<<1].r0 = tempr;t[now<<1].s0 = temps;
        t[now<<1].m1 = t[now<<1].m0;
        t[now<<1].m0 = tempm;
        // 右！ 
        templ = t[now<<1|1].l1,tempr = t[now<<1|1].r1,temps = t[now<<1|1].s1,tempm = t[now<<1|1].m1;
        t[now<<1|1].l1 = t[now<<1|1].l0;t[now<<1|1].r1 = t[now<<1|1].r0;t[now<<1|1].s1 = t[now<<1|1].s0;
        t[now<<1|1].l0 = templ;t[now<<1|1].r0 = tempr;t[now<<1|1].s0 = temps;
        t[now<<1|1].m1 = t[now<<1|1].m0;
        t[now<<1|1].m0 = tempm;
        if(tag[now<<1])pushdown(now<<1,l,mid);
        if(tag[now<<1|1])pushdown(now<<1|1,mid+1,r);
        tag[now<<1] = tag[now<<1|1] = 3;
        tag[now] = 0;
        return;
    }
}
void build(int now,int l,int r)
{
    if(l == r)
    {
        read(t[now].s1);
        if(t[now].s1 == 1)
        {
            t[now].l1 = t[now].r1 = t[now].m1 = 1;
        }
        else
        {
            t[now].s0 = t[now].l0 = t[now].r0 = t[now].m0 = 1;
        }
        return;
    }
    int mid = (l+r)>>1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    pushup(now,l,r);
}
void change0(int now,int l,int r,int LL,int RR)
{
    if(LL <= l && RR >= r)
    {
        //if(tag[now])pushdown(now,l,r);
        tag[now] = 2;
        t[now].s0 = t[now].l0 = t[now].r0 = (r-l+1);
        t[now].s1 = t[now].r1 = t[now].l1 = 0;
        t[now].m1 = 0;
        t[now].m0 = (r-l+1);
        return;
    }
    if(tag[now])pushdown(now,l,r);
    int mid = (l+r)>>1;
    if(LL <= mid)
    {
        change0(now<<1,l,mid,LL,RR);
    }
    if(RR > mid)
    {
        change0(now<<1|1,mid+1,r,LL,RR);
    }
    pushup(now,l,r);
}
void change1(int now,int l,int r,int LL,int RR)
{
    if(LL <= l && RR >= r)
    {
        //if(tag[now])pushdown(now,l,r);
        tag[now] = 1;
        t[now].s1 = t[now].l1 = t[now].r1 = (r-l+1);
        t[now].s0 = t[now].l0 = t[now].r0 = 0;
        t[now].m1 = (r-l+1);
        t[now].m0 = 0;
        return;
    }
    if(tag[now])pushdown(now,l,r);
    int mid = (l+r)>>1;
    if(LL <= mid)
    {
        change1(now<<1,l,mid,LL,RR);
    }
    if(RR > mid)
    {
        change1(now<<1|1,mid+1,r,LL,RR);
    }
    pushup(now,l,r);
}
void changefan(int now,int l,int r,int LL,int RR)
{
    if(LL <= l && RR >= r)
    {
        if(tag[now])pushdown(now,l,r);
        tag[now] = 3;
        int templ = t[now].l1,tempr = t[now].r1,temps = t[now].s1,tempm = t[now].m1;
        t[now].l1 = t[now].l0;t[now].r1 = t[now].r0;t[now].s1 = t[now].s0;
        t[now].l0 = templ;t[now].r0 = tempr;t[now].s0 = temps;
        t[now].m1 = t[now].m0;
        t[now].m0 = tempm;
        return;
    }
    if(tag[now])pushdown(now,l,r);
    int mid = (l+r)>>1;
    if(LL <= mid)
    {
        changefan(now<<1,l,mid,LL,RR);
    }
    if(RR > mid)
    {
        changefan(now<<1|1,mid+1,r,LL,RR);
    }
    pushup(now,l,r);
}
int querysum(int now,int l,int r,int LL,int RR)
{
    if(LL <= l && RR >= r)
    {
        return t[now].s1;
    }
    if(tag[now])pushdown(now,l,r);
    int ans = 0;
    int mid = (l+r)>>1;
    if(LL <= mid)
    {
        ans += querysum(now<<1,l,mid,LL,RR);
    }
    if(RR > mid)
    {
        ans += querysum(now<<1|1,mid+1,r,LL,RR);
    }
    pushup(now,l,r);
    return ans;
}
Tree querym(int now,int l,int r,int LL,int RR)
{
    if(LL <= l && RR >= r)
    {
        return t[now];
    }
    if(tag[now])pushdown(now,l,r);
    Tree ans;
    Tree L,R;
    int mid = (l+r)>>1;
    if(LL > mid)
    {
        return querym(now<<1|1,mid+1,r,LL,RR);
    }
    if(RR <= mid)
    {
        return querym(now<<1,l,mid,LL,RR);
    }
    L = querym(now<<1,l,mid,LL,RR);
    R = querym(now<<1|1,mid+1,r,LL,RR);
    ans.m1 = max(L.m1,R.m1);
    ans.m1 = max(ans.m1,L.r1 + R.l1);
    ans.l1 = L.l1;ans.r1 = R.r1;
    if(L.l1 == (mid-l+1))
    {
        ans.l1 = L.l1 + R.l1;
    }
    if(R.r1 == (r-mid))
    {
        ans.r1 = R.r1 + L.r1;
    }
    ans.m1 = max(ans.m1,ans.l1);
    ans.m1 = max(ans.m1,ans.r1);
    pushup(now,l,r);
    return ans;
}
signed main()
{
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout); 
    read(n),read(m);
    build(1,1,n);
    for(int i = 1; i <= m; i++)
    {
        changefan(1,1,n,1,n);
        changefan(1,1,n,1,n);
        int opt,l,r;
        read(opt),read(l),read(r);
        l++,r++;
        if(opt == 0)
        {
            change0(1,1,n,l,r);
        }
        if(opt == 1)
        {
            change1(1,1,n,l,r);
        }
        if(opt == 2)
        {
            changefan(1,1,n,l,r);
        }
        if(opt == 3)
        {
            printf("%lld\n",querysum(1,1,n,l,r));
        }
        if(opt == 4)
        {
            printf("%lld\n",querym(1,1,n,l,r).m1);
        }
        //统计有多少个连续的1
        //统计有多少个连续的0 
    }
    return 0;
}

by abjfj @ 2019-10-29 14:37:53

换成了两个标记，搞过去了，此贴完结

by resftlmuttmotw @ 2019-11-06 12:48:11

@abjfj

那您帮我康康吧

https://www.luogu.org/discuss/show/163760

by abjfj @ 2019-11-06 13:59:55

@resftlmuttmotw 加油！