如果一个区间的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;
}