UESTC 1592 An easy problem B 线段树区间合并

An easy problem B 线段树区间合并

Source

2017 UESTC Training for Data Structures

UESTC 1592 An easy problem B

My Solution

题意：区间更新把该区间内所有的数异或1，区间查询该区间内最长连续1的长度。

线段树区间合并
每个节点维护十元组
int summid[4*MAXN][2], suml[4*MAXN][2], sumr[4*MAXN][2], ans[4*MAXN][2], lazy[4*MAXN], rev[4*MAXN];
summid[Ind][k]表示该区间的中间的最长连续k(0|1)的长度，
suml[Ind][k]描述该区间从左端点开始的最长连续k(0|1)的长度，
sumr[Ind][k]表示从该区间右端点结束的最长连续k(0|1)的长度，
ans[Ind][k]表示该区间的最长连续k(0|1)的长度，
lazy[Ind]为延迟操作的标记，
rev[Ind]为旋转(异或)操作的标记。

每次pushup的时候，刷新这十元组，
inline void pushupk(int l, int r, int Ind, int k)
{
int mid = (l + r) >> 1;
if(mid - l + 1 == summid[Ind<<1][k]) suml[Ind][k] = summid[Ind<<1][k] + suml[Ind<<1|1][k];
else suml[Ind][k] = suml[Ind<<1][k];
if(r - (mid+1) + 1 == summid[Ind<<1|1][k]) sumr[Ind][k] = sumr[Ind<<1][k] + summid[Ind<<1|1][k];
else sumr[Ind][k] = sumr[Ind<<1|1][k];
summid[Ind][k] = max(max(summid[Ind<<1][k], summid[Ind<<1|1][k]), sumr[Ind<<1][k] + suml[Ind<<1|1][k]);
ans[Ind][k] = max(max(ans[Ind<<1][k], ans[Ind<<1|1][k]), max(suml[Ind][k], sumr[Ind][k]));
ans[Ind][k] = max(ans[Ind][k], summid[Ind][k]);
}
inline void pushup(int l, int r, int Ind)
{
pushupk(l, r, Ind, 0);
pushupk(l, r, Ind, 1);
}

每次如果有被标记过的延迟标记这pushdown
inline void pushdownk(int Ind)
{
swap(suml[Ind][0], suml[Ind][1]);
swap(sumr[Ind][0], sumr[Ind][1]);
swap(summid[Ind][0], summid[Ind][1]);
swap(ans[Ind][0], ans[Ind][1]);
}
inline void pushdown(int Ind)
{
lazy[Ind<<1] ^= 1;
lazy[Ind<<1|1] ^= 1;
rev[Ind<<1] ^= 1;
rev[Ind<<1|1] ^= 1;
if(rev[Ind<<1]){
pushdownk(Ind<<1);
rev[Ind<<1] ^= 1;
}
if(rev[Ind<<1|1]){
pushdownk(Ind<<1|1);
rev[Ind<<1|1] ^= 1;
}
lazy[Ind] = 0;
}

查询的时候，可以建立5个全局int findans, lans, rans, midans, rl;
每次查询到该最小区间即if(a <= l && r <= b)的时候刷新这个全局的四元组，
这样就不需要给查询函数设定返回值了，写起来比较方便，
即直接对该查询区间分成的子区间进行合并，具体见代码。
复杂度 O(nlogn)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;
const int INF = -2e9+8;

int summid[4*MAXN][2], suml[4*MAXN][2], sumr[4*MAXN][2], ans[4*MAXN][2], lazy[4*MAXN], rev[4*MAXN];
int findans, lans, rans, midans, rl;
int sz;
inline void pushdownk(int Ind)
{
    swap(suml[Ind][0], suml[Ind][1]);
    swap(sumr[Ind][0], sumr[Ind][1]);
    swap(summid[Ind][0], summid[Ind][1]);
    swap(ans[Ind][0], ans[Ind][1]);
}
inline void pushdown(int Ind)
{
    lazy[Ind<<1] ^= 1;
    lazy[Ind<<1|1] ^= 1;
    rev[Ind<<1] ^= 1;
    rev[Ind<<1|1] ^= 1;
    if(rev[Ind<<1]){
        pushdownk(Ind<<1);
        rev[Ind<<1] ^= 1;
    }
    if(rev[Ind<<1|1]){
        pushdownk(Ind<<1|1);
        rev[Ind<<1|1] ^= 1; } lazy[Ind] = 0; } inline void pushupk(int l, int r, int Ind, int k) { int mid = (l + r) >> 1;
    if(mid - l + 1 == summid[Ind<<1][k]) suml[Ind][k] = summid[Ind<<1][k] + suml[Ind<<1|1][k];
    else suml[Ind][k] = suml[Ind<<1][k];
    if(r - (mid+1) + 1 == summid[Ind<<1|1][k]) sumr[Ind][k] = sumr[Ind<<1][k] + summid[Ind<<1|1][k];
    else sumr[Ind][k] = sumr[Ind<<1|1][k];
    summid[Ind][k] = max(max(summid[Ind<<1][k], summid[Ind<<1|1][k]), sumr[Ind<<1][k] + suml[Ind<<1|1][k]);
    ans[Ind][k] = max(max(ans[Ind<<1][k], ans[Ind<<1|1][k]), max(suml[Ind][k], sumr[Ind][k]));
    ans[Ind][k] = max(ans[Ind][k], summid[Ind][k]);
}
inline void pushup(int l, int r, int Ind)
{
    pushupk(l, r, Ind, 0);
    pushupk(l, r, Ind, 1);
}
inline void _Modify(int a, int b, int l, int r, int Ind, int d){
    if(a <= l && r <= b){ lazy[Ind] ^= d; rev[Ind] ^= d; if(rev[Ind]){ pushdownk(Ind); rev[Ind] ^= 1; } return; } int mid = (l + r) >> 1;
    if(lazy[Ind]) pushdown(Ind);
    if(a <= mid){ _Modify(a, b, l, mid, Ind<<1, d); } if(b > mid){ _Modify(a, b, mid + 1, r,Ind<<1|1, d); }
    pushup(l, r, Ind);
}
inline void _Query(int a, int b, int l, int r, int Ind){
    if(a <= l && r <= b){ if(findans == INF){ findans = ans[Ind][1]; lans = suml[Ind][1]; rans = sumr[Ind][1]; midans = summid[Ind][1]; rl = r - l + 1; return; } if(rl == midans) lans = midans + suml[Ind][1]; midans = max(max(midans, summid[Ind][1]), rans + suml[Ind][1]); if(r - l + 1 == summid[Ind][1]) rans = rans + summid[Ind][1]; else rans = sumr[Ind][1]; findans = max(max(findans, ans[Ind][1]), max(rans, rans)); findans = max(findans, midans); rl += r - l + 1; return; } int mid = (l + r) >> 1;
    if(lazy[Ind]) pushdown(Ind);
    if(a <= mid) { _Query(a, b, l, mid, Ind<<1); } if(b > mid) { _Query(a, b, mid + 1, r, Ind<<1|1);} pushup(l, r, Ind); } inline void _Build(int l, int r, int Ind){ if(l == r){ lazy[Ind] = 0; rev[Ind] = 0; suml[Ind][0] = sumr[Ind][0] = summid[Ind][0] = ans[Ind][0] = 1; return; } int mid = (l + r) >> 1;
    _Build(l, mid, Ind<<1);
    _Build(mid + 1, r,Ind<<1|1);
    pushup(l, r, Ind);
}
inline void Modify(int a, int b, int d){return _Modify(a, b, 1, sz, 1, d);}
inline void Query(int a, int b) {return _Query(a, b, 1, sz, 1);}
inline void Build(){return _Build(1, sz, 1);}

int main()
{
    #ifdef LOCAL
    freopen("b.txt", "r", stdin);
    //freopen("b.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n, m, i, x, t, l, r;
    scanf("%d", &n);
    sz = n;
    Build();
    for(i = 1; i <= n; i++){
        scanf("%d", &x);
        Modify(i, i, x);
    }
    scanf("%d", &m);
    while(m--){
        scanf("%d%d%d", &t, &l, &r);
        if(t == 0){
            findans = lans = rans = midans = INF;
            Query(l, r);
            printf("%dn", findans);
        }
        else{
            Modify(l, r, 1);
        }
    }

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx