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 l, 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, l, r);

}

void pushtag(int o) {

	tr[o].lm = tr[o].rm = tr[o].xm = 0;

	addv[o] = 1;

}

void push_down(int o, int l, 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 l, int r, int a, int op) {//op=1表示前a个改为1，即前a个坐下， op=2表示后a个改为1

//	printf("%d %d %d %d %d", o, l, 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, l, r);

	if(op == 1) {

		if(tr[lson].xm >= a) insert(lson, l, mid, a, 1);

		else if(tr[lson].rm + tr[rson].lm >= a) {

			insert(rson, mid+1, r, a-tr[lson].rm , 1); //这个顺序太莫名其妙了....

			insert(lson, l, mid+1, tr[lson].rm , 2);//因为是从前往后，所以lson肯定是坐下tr[lson].r个

			}

		else insert(rson, mid+1, r, a, 1);//

	} else {

		if(tr[rson].xm >= a) insert(rson, mid+1, r, a, 2);

		else if(tr[lson].rm + tr[rson].lm >= a){

			insert(lson, l, mid, a-tr[rson].lm , 2);

			insert(rson, mid+1, r, tr[rson].lm , 1);

		}

		else insert(lson, l, mid, a, 2);

	}

	push_up(o, l, r);

}

void del(int o, int l, int r, 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, l, r);

	del(lson, l, mid, ql, qr);

	del(rson, mid+1, r, ql, qr);

	push_up(o,l,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, 1, n, a, 1);

		} else {

			int x, y;

			scanf("%d%d",&x, &y);

			del(1, 1, n, x, y);

		}

	}

	printf("%d",ans);

}
巴特西

luoguP3071 [USACO13JAN]座位Seating

最新文章

热门文章
