线段树复习

P2572 [SCOI2010]序列操作

这道题题解已经很多了

但是我还是想写一篇

纪念 调三天代码

思路

思路 很简单

struct node
{
    int len,sum,lazy,rev,lsum[2],rsum[2],maxl[2];
}tree[MAXN << 2];
len:长度

sum:1的个数

lazy:把[a, b]区间内的所有数全变成0/1标记

rev:反转标记

lsum[1/0]:记录从左边开始的最长连续1/0的个数

rsum[1/0]:记录从右边开始的最长连续1/0的个数

maxl[1/0]:记录区间内最长连续1/0的个数

然后 就正常的线段树操作了

主要是调试

调试要点

来说一些技巧

\(pushdown\)时 要么左区间,要么右区间

可以考虑 两次\(pushdown\)

每次传 现在区间标号 修改区间标号 修改区间长度

pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid);
r - mid ！！不要+1！！

类似的

update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
修改lsum[0],rsum[0],maxl[0]
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
修改lsum[1],rsum[1],maxl[1]

\(code\)

#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template<typename T>
inline T Read(T Type)
{
    T x = 0,f = 1;
    char a = getchar();
    while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
    while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
    return x * f;
}
const int MAXN = 100010;
struct segment_tree
{
    struct node
    {
        int len,sum,lazy,rev,lsum[2],rsum[2],maxl[2];
    }tree[MAXN << 2];
    void update(int k,int k1,int k2,int lenl,int lenr,int x) 
    {
        tree[k].maxl[x] = max(tree[k1].maxl[x],max(tree[k2].maxl[x],tree[k1].rsum[x] + tree[k2].lsum[x]));
        tree[k].lsum[x] = tree[k1].lsum[x];
        if(tree[k1].lsum[x] == lenl) tree[k].lsum[x] += tree[k2].lsum[x];
        tree[k].rsum[x] = tree[k2].rsum[x];
        if(tree[k2].rsum[x] == lenr) tree[k].rsum[x] += tree[k1].rsum[x];
        tree[k].sum = tree[k1].sum + tree[k2].sum;
    }
    void build(int k,int l,int r) 
    {
        if(l == r)
        {
            int x = tree[k].sum = Read(1);
            tree[k].maxl[x] = tree[k].lsum[x] = tree[k].rsum[x] = 1;
            tree[k].maxl[!x] = tree[k].lsum[!x] = tree[k].rsum[!x] = 0;
            tree[k].lazy = -1,tree[k].rev = 0;
            return;
        }
        int mid = l + r >> 1;
        tree[k].lazy = -1,tree[k].rev = 0;
        build(k << 1,l,mid);
        build(k << 1 | 1,mid + 1,r);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
    }
    void pushdown(int k,int k1,int len) 
    {
        if(tree[k].lazy != -1)
        {
            int x = tree[k1].lazy = tree[k].lazy;
            tree[k].rev = tree[k1].rev = 0;
            //lazy与rev的优先级务必考虑清楚 
            tree[k1].sum = (x == 1?len:0);
            tree[k1].maxl[x] = tree[k1].lsum[x] = tree[k1].rsum[x] = len;
            tree[k1].maxl[!x] = tree[k1].lsum[!x] = tree[k1].rsum[!x] = 0;
        }
        if(tree[k].rev)
        {
            if(tree[k1].lazy != -1) tree[k1].lazy = !tree[k1].lazy;
            else tree[k1].rev = !tree[k1].rev;
            //lazy与rev的优先级务必考虑清楚 
            //下传时，注意修改l/r区间的rev和lazy 此时仍得考虑优先级 
            tree[k1].sum = len - tree[k1].sum;
            swap(tree[k1].lsum[0],tree[k1].lsum[1]);
            swap(tree[k1].rsum[0],tree[k1].rsum[1]);
            swap(tree[k1].maxl[0],tree[k1].maxl[1]);
        }
    }
    void change(int k,int l,int r,int L,int R,int x) 
    {
        if(L <= l&&r <= R)
        {
            tree[k].lazy = x,tree[k].rev = 0; 
            tree[k].sum = (x == 1?r - l + 1:0);
            tree[k].maxl[x] = tree[k].lsum[x] = tree[k].rsum[x] = r - l + 1;
            tree[k].maxl[!x] = tree[k].lsum[!x] = tree[k].rsum[!x] = 0;
            return;
        }
        int mid = l + r >> 1;
        pushdown(k,k << 1,mid - l + 1);
        pushdown(k,k << 1 | 1,r - mid);
        tree[k].lazy = -1,tree[k].rev = 0;
        if(L <= mid) change(k << 1,l,mid,L,R,x);
        if(mid < R) change(k << 1 | 1,mid + 1,r,L,R,x);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
    }
    void inverse(int k,int l,int r,int L,int R) 
    {
        if(L <= l&&r <= R)
        {
            if(tree[k].lazy != -1) tree[k].lazy = !tree[k].lazy;
            else tree[k].rev = !tree[k].rev;
            tree[k].sum = r - l + 1 - tree[k].sum;
            swap(tree[k].lsum[0],tree[k].lsum[1]);
            swap(tree[k].rsum[0],tree[k].rsum[1]);
            swap(tree[k].maxl[0],tree[k].maxl[1]);
            return;
        }
        int mid = l + r >> 1;
        pushdown(k,k << 1,mid - l + 1);
        pushdown(k,k << 1 | 1,r - mid);
        tree[k].lazy = -1,tree[k].rev = 0;
        if(L <= mid) inverse(k << 1,l,mid,L,R);
        if(mid < R) inverse(k << 1 | 1,mid + 1,r,L,R);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
    }
    int query(int k,int l,int r,int L,int R) 
    {
        
        if(L <= l&&r <= R) return tree[k].sum;
        int mid = l + r >> 1;
        pushdown(k,k << 1,mid - l + 1);
        pushdown(k,k << 1 | 1,r - mid);
        tree[k].lazy = -1,tree[k].rev = 0;
        int ans = 0;
        if(L <= mid) ans = query(k << 1,l,mid,L,R);
        if(mid < R) ans += query(k << 1 | 1,mid + 1,r,L,R);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
        return ans;
    }
    node Sum(int k,int l,int r,int L,int R) 
    {
        if(L <= l&&r <= R) 
        {
            tree[k].len = r - l + 1;
            return tree[k];
        }
        int mid = l + r >> 1;
        pushdown(k,k << 1,mid - l + 1);
        pushdown(k,k << 1 | 1,r - mid);
        tree[k].lazy = -1,tree[k].rev = 0;
        node k1[2];
        memset(k1,0,sizeof(k1));
        if(L <= mid) k1[0] = Sum(k << 1,l,mid,L,R);
        if(mid < R) k1[1] = Sum(k << 1 | 1,mid + 1,r,L,R);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
        update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
        node k3;
        k3.maxl[1] = max(k1[0].maxl[1],max(k1[1].maxl[1],k1[0].rsum[1] + k1[1].lsum[1]));
        k3.lsum[1] = k1[0].lsum[1];
        if(k1[0].lsum[1] == k1[0].len) k3.lsum[1] += k1[1].lsum[1];
        k3.rsum[1] = k1[1].rsum[1];
        if(k1[1].rsum[1] == k1[1].len) k3.rsum[1] += k1[0].rsum[1];
        k3.len = k1[0].len + k1[1].len;
        //不要忘了算len 这行没写 只会wa两个点 
        return k3;
    }
}T;
int main()
{
    int n = Read(1),m = Read(1);
    memset(T.tree,0,sizeof(T.tree));
    T.build(1,1,n);
    while(m--)
    {
        int ans,op = Read(1),l = Read(1) + 1,r = Read(1) + 1;
        //不要忘了加1 
        switch(op)
        {
            case 0: T.change(1,1,n,l,r,0); break; 
            case 1: T.change(1,1,n,l,r,1); break; 
            case 2: T.inverse(1,1,n,l,r); break; 
            case 3: ans = T.query(1,1,n,l,r); printf("%d\n",ans); break; 
            case 4: ans = T.Sum(1,1,n,l,r).maxl[1]; printf("%d\n",ans); break; 
        }
    }
    return 0;
}

总结

这种毒瘤数据结构题

先静态查错

再对拍

然后求助

或者直接求助

帮助工具

如果还没调出来 可以尝试以下方式

小蒟蒻皮皮鱼 提供的对拍程序

#include<bit/stdc++.h>
using namespace std;
int main()
{
    while(1)
    {
        system("gen.exe");//这是你的数据生成器
        system("1.exe < data.in > 1.out");//这是你的程序 
        system("2.exe < data.in > 2.out");//这是题解或者需要对拍的暴力
        if(system("fc 1.out 2.out")) break;//对两个的输出进行比较，不一样就会终止程序 
    }
}

LJC00118 提供的

数据生成程序

线段树复习

原文：https://www.cnblogs.com/resftlmuttmotw/p/11811489.html