求调10分

P2572 [SCOI2010] 序列操作

sinsop90 @ 2022-07-05 11:37:13

#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int rev[maxn << 2], tag[maxn << 2], n, T, a[maxn];
struct node {
    int left0, left1, middle0, middle1, right0, right1, sum;
    node () { left0 = left1 = middle0 = middle1 = right0 = right1 = sum = 0; }
}ansn[maxn << 2];
int ls(int p) {
    return p << 1;
}
int rs(int p) {
    return p << 1 | 1;
}
void f(int p, int l, int r, int k) {
    rev[p] = 0;
    ansn[p].sum = k * (r - l + 1);
    tag[p] = k;
    if(k) {
        ansn[p].left0 = ansn[p].right0 = ansn[p].middle0 = 0;
        ansn[p].left1 = ansn[p].right1 = ansn[p].middle1 = r - l + 1;
    }
    else {
        ansn[p].left0 = ansn[p].right0 = ansn[p].middle0 = r - l + 1;
        ansn[p].left1 = ansn[p].right1 = ansn[p].middle1 = 0;
    }
}
void f2(int p, int l, int r) {
    rev[p] ^= 1;
    ansn[p].sum = (r - l + 1) - ansn[p].sum;
    node res = ansn[p];
    ansn[p].left1 = res.left0;
    ansn[p].left0 = res.left1;
    ansn[p].right1 = res.right0;
    ansn[p].right0 = res.right1;
    ansn[p].middle1 = res.middle0;
    ansn[p].middle0 = res.middle1;
}   
void pushdown(int p, int l, int r) {
    if(tag[p] != -1) {
        rev[p] = 0;
        int mid = (l + r) >> 1;
        f(ls(p), l, mid, tag[p]);
        f(rs(p), mid + 1, r, tag[p]);
        tag[p] = -1;
    }
    if(rev[p]) {
        int mid = (l + r) >> 1;
        f2(ls(p), l, mid);
        f2(rs(p), mid + 1, r);
        rev[p] = 0;
    }
//  tag[p] = -1, rev[p] = 0;
}
void pushup(int p, int l, int r) {
    int mid = (l + r) >> 1;
    ansn[p].sum = ansn[ls(p)].sum + ansn[rs(p)].sum;
    if(ansn[ls(p)].left0 == mid - l + 1) ansn[p].left0 = ansn[ls(p)].left0 + ansn[rs(p)].left0;
    else ansn[p].left0 = ansn[ls(p)].left0;
    if(ansn[rs(p)].right0 == r - mid) ansn[p].right0 = ansn[rs(p)].right0 + ansn[ls(p)].right0;
    else ansn[p].right0 = ansn[rs(p)].right0;
    if(ansn[ls(p)].left1 == mid - l + 1) ansn[p].left1 = ansn[ls(p)].left1 + ansn[rs(p)].left1;
    else ansn[p].left1 = ansn[ls(p)].left1;
    if(ansn[rs(p)].right1 == r - mid) ansn[p].right1 = ansn[rs(p)].right1 + ansn[ls(p)].right1;
    else ansn[p].right1 = ansn[rs(p)].right1;
    ansn[p].middle0 = max(max(ansn[ls(p)].middle0, ansn[rs(p)].middle0), ansn[ls(p)].right0 + ansn[rs(p)].left0);
    ansn[p].middle1 = max(max(ansn[ls(p)].middle1, ansn[rs(p)].middle1), ansn[ls(p)].right1 + ansn[rs(p)].left1);
}
void modify(int p, int l, int r, int nl, int nr, int k) {
    pushdown(p, l, r);
    if(nl <= l && r <= nr) {
        f(p, l, r, k);
        return;
    }  
    int mid = (l + r) >> 1;
    if(nl <= mid) modify(ls(p), l, mid, nl, nr, k);
    if(nr > mid) modify(rs(p), mid + 1, r, nl, nr, k);
    pushup(p, l, r);
}
void reverse(int p, int l, int r, int nl, int nr) {
    pushdown(p, l, r);
    if(nl <= l && r <= nr) {
        f2(p, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    if(nl <= mid) reverse(ls(p), l, mid, nl, nr);
    if(nr > mid) reverse(rs(p), mid + 1, r, nl, nr);
    pushup(p, l, r);
}
int querysum(int p, int l, int r, int nl, int nr) {
    pushdown(p, l, r);
    if(nl <= l && r <= nr) return ansn[p].sum;
    int mid = (l + r) >> 1, res = 0;
    if(nl <= mid) res += querysum(ls(p), l, mid, nl, nr);
    if(nr > mid) res += querysum(rs(p), mid + 1, r, nl, nr);
    return res;
}

node querynum(int p, int l, int r, int nl, int nr) {
    pushdown(p, l, r);
    int mid = (l + r) >> 1;
    if(nl == l && nr == r) return ansn[p];
    if(nl > mid) return querynum(rs(p), mid + 1, r, nl, nr);
    else if(nr <= mid) return querynum(ls(p), l, mid, nl, nr);
    else {
        node res, lef = querynum(ls(p), l, mid, nl, mid), rig = querynum(rs(p), mid + 1, r, mid + 1, nr);
        res.sum = lef.sum + rig.sum;
        res.left0 = lef.left0, res.left1 = lef.left1;
        if(lef.left0 == mid - l + 1) res.left0 += rig.left0;
        if(lef.left1 == mid - l + 1) res.left1 += rig.left1;
        res.right0 = rig.right0, res.right1 = rig.right1;
        if(rig.right0 == r - mid) res.right0 += lef.right0;
        if(rig.right1 == r - mid) res.right1 += lef.right1;
        res.middle0 = max(max(lef.middle0, rig.middle0), lef.right0 + rig.left0);
        res.middle1 = max(max(lef.middle1, rig.middle1), lef.right1 + rig.left1);
        return res;
    }
}
int main() {
    memset(tag, -1, sizeof tag);
    scanf("%d%d", &n, &T);
    for(int i = 1;i <= n;i++) {
        scanf("%d", &a[i]);
        modify(1, 1, n + 1, i, i, a[i]);
    }
    while(T --) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        l++, r++;
        if(op == 0) modify(1, 1, n + 1, l, r, 0);
        if(op == 1) modify(1, 1, n + 1, l, r, 1);
        if(op == 2) reverse(1, 1, n + 1, l, r);
        if(op == 3) printf("%d\n", querysum(1, 1, n + 1, l, r));
        if(op == 4) printf("%d\n", querynum(1, 1, n + 1, l, r).middle1);
    }
}

|