类似最大字段和 luoguP3071 [USACO13JAN]座位Seating

https://www.luogu.org/problem/P3071

AC代码：

https://www.luogu.org/blog/user33426/solution-p3071

莫名其妙RE：

#include<cstdio>
#include<iostream>

using namespace std;
#define MAX 500005
#define lson o<<1
#define rson o<<1|1

int n,m,ans,cnt;
int addv[MAX];
struct node{
    int lm,rm,xm;
    //从左到右的最大空位置的数
    //从右到左的
    //整个的 
}tr[MAX<<2];

inline int max(int x,int y) {
    return x>y?x:y;
}

void push_up(int o,int l,int r) {
    tr[o].xm = max(max(tr[lson].xm,tr[rson].xm ),tr[lson].rm + tr[rson].lm );
    int mid = (l+r)>>1;
    if(tr[lson].xm == mid-l+1) tr[o].lm = tr[lson].xm + tr[rson].lm ;
    else tr[o].lm = tr[lson].lm ;
    if(tr[rson].xm == r-mid) tr[o].rm = tr[rson].xm + tr[lson].rm ;
    else tr[o].rm = tr[rson].rm ;
}
void build(int o,int r) {
    if(l == r) {
        tr[o].lm = tr[o].rm = tr[o].xm = 1;
        return ;
    }
    int mid = (l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    push_up(o,r);
}

void pushtag(int o) {
    tr[o].lm = tr[o].rm = tr[o].xm = 0;
    addv[o] = 1;
}
void push_down(int o,int r) {
    if(addv[o] == 0) return ;
    int mid = (l+r)>>1;
    tr[lson].lm = tr[lson].rm = tr[lson].xm = addv[o]>0 ? 0 : (mid-l+1);  //-1为离开 
    tr[rson].lm = tr[rson].rm = tr[rson].xm = addv[o]>0 ? 0 : (r-mid); //1为坐下 
    addv[lson] = addv[rson] = addv[o];
    addv[o] = 0;
    return ;
} 

void insert(int o,int r,int a,int op) {//op=1表示前a个改为1，即前a个坐下， op=2表示后a个改为1 
//  printf("%d %d %d %d %d",o,r,a,op);
//  printf("n");
    if(a == 0) return ;
    if(r-l+1 == a) {pushtag(o); return ;}
    int mid = (l+r)>>1;
    push_down(o,r);
    if(op == 1) {
        if(tr[lson].xm >= a) insert(lson,mid,1);
        else if(tr[lson].rm + tr[rson].lm >= a) {
            insert(rson,a-tr[lson].rm,1); //这个顺序太莫名其妙了.... 
            insert(lson,tr[lson].rm,2);//因为是从前往后，所以lson肯定是坐下tr[lson].r个 
            }
        else insert(rson,1);//
    } else {
        if(tr[rson].xm >= a) insert(rson,2);
        else if(tr[lson].rm + tr[rson].lm >= a){
            insert(lson,a-tr[rson].lm,2);
            insert(rson,tr[rson].lm,1);
        }
        else insert(lson,2);
    }
    push_up(o,r);
}

void del(int o,int ql,int qr) {
    if(qr<l||r<ql) return;
    if(ql <= l && r <= qr) {
        tr[o].lm = tr[o].rm = tr[o].xm = (r-l+1);
        addv[o] = -1;
        return ;
    }
    int mid = (l+r)>>1;
    push_down(o,r);
    del(lson,ql,qr);
    del(rson,qr);
    push_up(o,r);
}

int main() {
    scanf("%d%d",&n,&m);
    build(1,1,n);
//  int tmp;
//  scanf("%d",&tmp);
//  printf("o : %d,%d",tmp,tr[tmp].lm);
    char cmd;
    while(m--) {
        cin>>cmd;
        if(cmd == 'A') {
            int a;
            scanf("%d",&a);
            if(tr[1].xm < a) ans++;
            else insert(1,n,1);
        } else {
            int x,y;
            scanf("%d%d",&x,&y);
            del(1,x,y);
        }
    }
    printf("%d",ans);
}