为什么?这和AC代码有什么区别?
查看原帖
为什么?这和AC代码有什么区别?
782395
qiuzilai楼主2024/8/21 20:36

为什么错?

#include <bits/stdc++.h>
using namespace std;
const int MX  = 500010;
const int INF = 1e9;
int n, m;
struct Node {
	int s[2], p, v;
	int rev;
	int same, sze, sum, ms;
	int ls, rs;
	
	void init(int vv, int pp) {
		s[0] = s[1] = 0;
		p = pp, v = vv;
		rev = same = 0;
		sze = 1;
		sum = ms = v;
		ls = rs = max(v, 0);
	}
}tr[MX];
int root, nods[MX], tt;
int w[MX];

void pushup(int x) {
	Node &u = tr[x];
	Node &l = tr[u.s[0]];
	Node &r = tr[u.s[1]];
	
	u.sze = l.sze + r.sze + 1;
	u.sum = l.sum + r.sum + u.v;
	u.ls  = max(l.ls, l.sum+u.v+r.ls);
	u.rs  = max(r.rs, r.sum+u.v+l.rs);
	u.ms  = max(max(l.ms, r.ms), l.rs+u.v+r.ls); 
} 

void pushdown(int x) {
	auto &u = tr[x];
	auto &l = tr[u.s[0]];
	auto &r = tr[u.s[1]];
	if(u.same) {
		u.same = u.rev = 0;
		if(u.s[0]) l.same = 1, l.v = u.v, l.sum = l.v * l.sze;
		if(u.s[1]) r.same = 1, r.v = u.v, r.sum = r.v * r.sze;
		if(u.v > 0) {
			if(u.s[0]) l.ms = l.ls = l.rs = l.sum;
			if(u.s[1]) r.ms = r.ls = r.rs = r.sum;
		} else {
			if(u.s[0]) l.ms = l.v, l.ls = l.rs = 0;
			if(u.s[1]) r.ms = r.v, r.ls = r.rs = 0;
		}
	} else if(u.rev) {
		u.rev = 0, l.rev ^= 1, r.rev ^= 1;
		swap(l.ls, l.rs);
		swap(r.ls, r.rs);
		swap(l.s[0], l.s[1]);
		swap(r.s[0], r.s[1]);
	}
} 

void rotate(int x) {
	int y = tr[x].p;
	int z = tr[y].p;
	int k = tr[y].s[1] == x;
	
	tr[z].s[tr[z].s[1] == y] = x;
	tr[x].p = z;
	tr[y].s[k] = tr[x].s[k^1];
	tr[tr[x].s[k^1]].p = y;
	tr[x].s[k^1] = y;
	tr[y].p = x;
	
	pushup(y);
	pushup(x);
}

void splay(int x, int k) {
	while(tr[x].p != k) {
		int y = tr[x].p;
		int z = tr[y].p;
		if(z != k) {
			if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) {
				rotate(x);
			} else {
				rotate(y);
			}
		}
		rotate(x);
	}
	if(!k) root = x;
}

int Build(int l, int r, int p) {
	int mid = l+r>>1;
	int u = nods[tt--];
	tr[u].init(w[mid], p);
	if(l < mid) {
		tr[u].s[0] = Build(l, mid-1, u);
	}
	if(mid < r) {
		tr[u].s[1] = Build(mid+1, r, u);
	}
	pushup(u);
	return u;
} 

void dfs(int u) {
	if(tr[u].s[0]) {
		dfs(tr[u].s[0]);
	} 
	if(tr[u].s[1]) {
		dfs(tr[u].s[1]);
	}
	nods[++tt] = u;
}

int get_k(int k) {
	int u = root;
	while(u) {
		pushdown(u);	
		if(tr[tr[u].s[0]].sze >= k) {
//			cout << 1;
//			system("pause");
			u = tr[u].s[0];
		} else if(tr[tr[u].s[0]].sze+1 == k) {
			return u; 
		} else {
			k -= tr[tr[u].s[0]].sze + 1;
			u = tr[u].s[1];
		}
	}
}

int main() {
	for(int i=1; i<=MX; i++) {
		nods[++tt] = i;
	}
	scanf("%d%d", &n, &m);
	tr[0].ms = -INF;
	w[0] = w[n+1] = -INF;
	for(int i=1; i<=n; i++) {
		scanf("%d", &w[i]);
	}
	root = Build(0, n+1, 0);
	char op[20];
	while(m--) {
		scanf("%s", op);
		if(!strcmp(op, "INSERT")) {
			int posi, tot;
			scanf("%d%d", &posi, &tot);
			for(int i=0; i<tot; i++) {
				scanf("%d", &w[i]);
			} 
			int l = get_k(posi+1); 
			int r = get_k(posi+2);
			splay(l, 0);
			splay(r, l);
			int u = Build(0, tot-1, r);
			tr[r].s[0] = u;
			pushup(r);
			pushup(l); 
		} else if(!strcmp(op, "DELETE")) {
			int posi, tot;
			scanf("%d%d", &posi, &tot);
			int l = get_k(posi);
			int r = get_k(posi+tot+1);
			splay(l, 0);
			splay(r, l);
			dfs(tr[r].s[0]);
			tr[r].s[0] = 0;
			pushup(r);
			pushup(l);
		} else if(!strcmp(op, "MAKE-SAME")) {
			int posi, tot, c;
			scanf("%d%d%d", &posi, &tot, &c);
			int l = get_k(posi);
			int r = get_k(posi+tot+1);
			splay(l, 0);
			splay(r, l);
			Node &son = tr[tr[r].s[0]];
			son.same = 1;
			son.v = c;
			son.sum = c*son.sze;
			
			if(c > 0) {
				son.ms = son.ls = son.rs = son.sum;
			} else {
				son.ms = c, son.ls = son.rs = 0;
			}
			pushup(r);
			pushup(l);
		} else if(!strcmp(op, "REVERSE")) {
			int posi, tot;
			scanf("%d%d", &posi, &tot);
			int l = get_k(posi);
			int r = get_k(posi+tot+1);
			splay(l, 0);
			splay(r, l);
			Node &son = tr[tr[r].s[0]];
			son.rev ^= 1;
			swap(son.ls, son.rs);
			swap(son.s[0], son.s[1]);
			pushup(r);
			pushup(l);
		} else if(!strcmp(op, "GET-SUM")) {
			int posi, tot;
			scanf("%d%d", &posi, &tot);
			int l = get_k(posi);
			int r = get_k(posi+tot+1);		
			splay(l, 0);
			splay(r, l);
			printf("%d\n", tr[tr[r].s[0]].sum);
		} else {
			printf("%d\n", tr[root].ms);
		}
	}
	return 0;
} 
2024/8/21 20:36
加载中...