萌新求助开O2WA不开O2AC的代码
查看原帖
萌新求助开O2WA不开O2AC的代码
350270
CatFromMars楼主2024/7/18 21:43

如题,不知道哪里出问题了,希望巨佬可以帮忙看看 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;
	}
}
2024/7/18 21:43
加载中...