萌新求助开O2WA不开O2AC的代码

P2572 [SCOI2010] 序列操作

CatFromMars @ 2024-07-18 21:43:33

如题,不知道哪里出问题了,希望巨佬可以帮忙看看 qwq

///dasfsdafadsf
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
struct piar {
    int qz, hz, lx, sum;
};

int a[N * 4 + 10], n, m;
int cxr[N * 4 + 10], col[N * 4 + 10];
int sum[N * 4 + 10][3], qz[N * 4 + 10][3], hz[N * 4 + 10][3], lx[N * 4 + 10][3];
int ls(int x) {
    return 2 * x;
}
int rs(int x) {
    return 2 * x + 1;
}
void tagcxr(int x) {
    if(col[x] != -1) col[x] ^= 1;
    else cxr[x] ^= 1;
    swap(sum[x][0], sum[x][1]);
    swap(qz[x][0], qz[x][1]);
    swap(hz[x][0], hz[x][1]);
    swap(lx[x][0], lx[x][1]);
}
void tagcol(int x, int s, int t, int cl) {
    cxr[x] = 0, col[x] = cl;
    sum[x][cl] = qz[x][cl] = hz[x][cl] = lx[x][cl] = t - s + 1;
    sum[x][1 - cl] = qz[x][1 - cl] = hz[x][1 - cl] = lx[x][1 - cl] = 0;
}
void push_down(int x, int s, int t) {
    int mid = (s + t) >> 1;
    if(col[x] != -1) {
        tagcol(ls(x), s, mid, col[x]);
        tagcol(rs(x), mid + 1, t, col[x]);
        col[x] = -1;
    }
    if(cxr[x]) {
        tagcxr(ls(x));
        tagcxr(rs(x));
        cxr[x] = 0;
    }
    return ;
}
void push_up(int x, int s, int t) {
    for(int p = 0; p < 2; p++)
        sum[x][p] = sum[ls(x)][p] + sum[rs(x)][p];

    int mid = (s + t) >> 1;

    for(int p = 0; p < 2; p++)
        if(sum[ls(x)][p] == mid - s + 1)
            qz[x][p] = sum[ls(x)][p] + qz[rs(x)][p];
        else qz[x][p] = qz[ls(x)][p];

    for(int p = 0; p < 2; p++)
        if(sum[rs(x)][p] == t - mid)
            hz[x][p] = sum[rs(x)][p] + hz[ls(x)][p];
        else hz[x][p] = hz[rs(x)][p];

    for(int p = 0; p < 2; p++)
        lx[x][p] = max(max(lx[ls(x)][p], lx[rs(x)][p]), 
            hz[ls(x)][p] + qz[rs(x)][p]);
}
void upcol(int ql, int qr, int s, int t, int now, int val) {
    if(ql <= s && t <= qr) {
        tagcol(now, s, t, val);
        return ;
    }
    int mid = (s + t) >> 1;
    push_down(now, s, t);
    if(ql <= mid) upcol(ql, qr, s, mid, ls(now), val);
    if(qr > mid) upcol(ql, qr, mid + 1, t, rs(now), val);
    push_up(now, s, t);
}
void upcxr(int ql, int qr, int s, int t, int now) {
    if(ql <= s && t <= qr) {
        tagcxr(now);
        return ;
    }
    int mid = (s + t) >> 1;
    push_down(now, s, t);
    if(ql <= mid) upcxr(ql, qr, s, mid, ls(now));
    if(qr > mid) upcxr(ql, qr, mid + 1, t, rs(now));
    push_up(now, s, t);
}
int qry1(int ql, int qr, int s, int t, int now) {
    if(ql <= s && t <= qr) return sum[now][1];
    int mid = (s + t) >> 1, rest = 0;
    push_down(now, s, t);
    if(ql <= mid) rest += qry1(ql, qr, s, mid, ls(now));
    if(qr > mid) rest += qry1(ql, qr, mid + 1, t, rs(now));
    return rest;
}
piar qry2(int ql, int qr, int s, int t, int now) {
    if(ql <= s && t <= qr) {
        piar tmp;
        tmp.qz = qz[now][1];
        tmp.hz = hz[now][1];
        tmp.lx = lx[now][1];
        tmp.sum = sum[now][1];
        return tmp;
    }
    int mid = (s + t) >> 1;
    piar L, R, rest;
    L.qz = L.hz = L.lx = R.qz = R.hz = R.lx = 0;
    push_down(now, s, t);
    if(ql <= mid) L = qry2(ql, qr, s, mid, ls(now));
    if(qr > mid) R = qry2(ql, qr, mid + 1, t, rs(now));

    if(L.sum == mid - s + 1) rest.qz = L.sum + R.qz;
    else rest.qz = L.qz;
    if(R.sum == t - mid) rest.hz = R.sum + L.hz;
    else rest.hz = R.hz;
    rest.lx = max(L.lx, max(R.lx, L.hz + R.qz));

    return rest;
}

void build(int l, int r, int x) {
    cxr[x] = 0, col[x] = -1;
    if(l == r) {
        sum[x][a[l]] = qz[x][a[l]] = 
        hz[x][a[l]] = lx[x][a[l]] = 1;
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls(x));
    build(mid + 1, r, rs(x));
    push_up(x, l, r);
}

int main() {
    cin >> n >> m;
    for(int p = 1; p <= n; p++)
        cin >> a[p];
    build(1, n, 1); 

    for(int p = 1; p <= m; p++) {
        int opt, l, r; cin >> opt >> l >> r;
        l++, r++;
        if(!opt) upcol(l, r, 1, n, 1, 0);
        else if(opt == 1) upcol(l, r, 1, n, 1, 1);
        else if(opt == 2) upcxr(l, r, 1, n, 1);
        else if(opt == 3) cout << qry1(l, r, 1, n, 1) << endl;
        else if(opt == 4) cout << qry2(l, r, 1, n, 1).lx << endl;
    }
}

by _buzhidao_ @ 2024-07-18 22:53:03

@CatFromMars UB


by CatFromMars @ 2024-07-18 22:53:55

@buzhidao 有巨佬帮忙找到问题了,L.R.sum 没有赋初值,,,


by _buzhidao_ @ 2024-07-18 22:54:24

@CatFromMars 6


|