关于区间ans与区间最大前缀长度的一个小问题
查看原帖
关于区间ans与区间最大前缀长度的一个小问题
510137
skyboard楼主2021/8/15 11:28

如果一个区间的ans与这个区间的长度相等,那么这个区间的ans和这个区间的最大前缀长度相等吗

如果把pushup中最后两个if中的判定改成if(left.all == left.pre)和if(right.all == right.last),答案就错了,但按理来说这是等价的呀,请问佬们这是哪里出错了呢

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 200010;
int n,m;
struct Tree{
	int l,r;
	int pre,last,all,le,ri;
}tr[4 * N];
void pushup(int u){
	Tree &root = tr[u],&left = tr[u << 1],&right = tr[u << 1 | 1];
	root.le = left.le,root.ri = right.ri;
	if(left.ri == right.le){
		root.pre = left.pre,root.last = right.last;
		root.all = max(left.all,right.all);
	}
	else{
		root.all = max(left.all,right.all);
		root.all = max(root.all,left.last + right.pre);
		if(left.all == left.r - left.l + 1)
			root.pre = left.all + right.pre;
		else
			root.pre = left.pre;
		if(right.all == right.r - right.l + 1)
			root.last = right.all + left.last;
		else
			root.last = right.last;
	}
}
void build(int u,int l,int r){
	if(l == r) tr[u] = {l,r,1,1,1,0,0};
	else{
		tr[u] = {l,r};
		int mid = l + r >> 1;
		build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
		pushup(u);
	}
}
void modify(int u,int x){
	if(tr[u].l == tr[u].r && tr[u].l == x) tr[u].le ^= 1,tr[u].ri ^= 1;
	else{
		int mid = tr[u].l + tr[u].r >> 1;
		if(x <= mid) modify(u << 1,x);
		else modify(u << 1 | 1,x);
		pushup(u);
	}
}
int main(){
	cin >> n >> m;
	build(1,1,n);
	while(m --){
		int x;
		scanf("%d",&x);
		modify(1,x);
		cout << tr[1].all << endl;
	}
	return 0;
}
2021/8/15 11:28
加载中...