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