BZOJ3050: [Usaco2013 Jan]Seating【线段树】

dzy posted @ 2013年9月13日 22:17 in BZOJ with tags 线段树 bzoj , 1993 阅读

好久没来了。除个草吧。

 

m(m<=300,000)个操作。操作分2种:

1.A p,表示把编号最小的空着的长度为p的区间图上颜色。

2.L a b,表示把从a到b的区间(包括端点)全部擦干净(没颜色还是没颜色)。

Q:有多少个操作1不能实现?

 

USACO的GOLD题。喜闻乐见的数据结构题。

 

仔细YY一下就可以发现线段树即可。

每个节点维护左边开始连续空的个数,右边连续空的个数,整段里面连续空的个数。

up的时候合并一下就行。down的时候打标记。

 

具体实现操作一的时候,需要先递归查找一下操作的区间。自行脑补吧。

操作二就是打标记。

 

没了。

 

PS:顺利成为在bz上第6个A了这道题的棱,而且还r1了= =

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxt=2010000;
int n,m;
struct SegNode{
	int l0,r0,s0,m0,m1,all;
}t[maxt];
#define ls (x<<1)
#define rs (x<<1|1)
char buf[5120000],*pt=buf;
inline int getint(){
    int s=0; while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48;return s;
}inline char getop(){
	while(*pt!='A'&&*pt!='L')	pt++;	return *pt++;
}void update(int l,int r,int x){
	if(t[ls].all)	t[x].l0=t[ls].l0+t[rs].l0;	else	t[x].l0=t[ls].l0;
	if(t[rs].all)	t[x].r0=t[ls].r0+t[rs].r0;	else	t[x].r0=t[rs].r0;
	t[x].all=t[ls].all&t[rs].all;
	t[x].s0=t[x].l0;
	if(t[x].r0>t[x].s0)	t[x].s0=t[x].r0;
	if(t[ls].s0>t[x].s0)	t[x].s0=t[ls].s0;
	if(t[rs].s0>t[x].s0)	t[x].s0=t[rs].s0;
	if(t[ls].r0+t[rs].l0>t[x].s0)	t[x].s0=t[ls].r0+t[rs].l0;
}void down(int l,int r,int x){
	if(t[x].m1){
		t[ls]=t[rs]=(SegNode){0,0,0,0,1,0};
		t[x].m1=0;
	}if(t[x].m0){
		int mid=(l+r)>>1;
		t[ls]=(SegNode){mid-l+1,mid-l+1,mid-l+1,1,0,1};
		t[rs]=(SegNode){r-mid,r-mid,r-mid,1,0,1};
		t[x].m0=0;
	}
}void build(int l,int r,int x){
	if(l==r){
		t[x]=(SegNode){1,1,1,0,0,1};
		return; 
	}int mid=(l+r)>>1;
	build(l,mid,ls);
	build(mid+1,r,rs);
	update(l,r,x);
}void modify1(int L,int R,int l,int r,int x){
	if(L<=l && r<=R){
		t[x]=(SegNode){0,0,0,0,1,0};
		return;
	}down(l,r,x);
	int mid=(l+r)>>1;
	if(L<=mid)	modify1(L,R,l,mid,ls);
	if(mid<R)	modify1(L,R,mid+1,r,rs);
	update(l,r,x);
}void modify0(int L,int R,int l,int r,int x){
	if(L<=l && r<=R){
		t[x]=(SegNode){r-l+1,r-l+1,r-l+1,1,0,1};
		return;
	}down(l,r,x);
	int mid=(l+r)>>1;
	if(L<=mid)	modify0(L,R,l,mid,ls);
	if(mid<R)	modify0(L,R,mid+1,r,rs);
	update(l,r,x);
}SegNode ask(int L,int R,int l,int r,int x){
	if(L<=l && r<=R)	return t[x];
	down(l,r,x);
	int mid=(l+r)>>1;
	if(L>mid)	return ask(L,R,l,mid,ls);
	if(mid>=R)	return ask(L,R,mid+1,r,rs);
	SegNode a=ask(L,R,l,mid,ls),b=ask(L,R,mid+1,r,rs),c;
	if(a.all)	c.l0=a.l0+b.l0;	else	c.l0=a.l0;
	if(b.all)	c.r0=a.r0+b.r0;	else	c.r0=b.r0;
	c.all=a.all&b.all;
	c.s0=c.l0;
	if(c.r0>c.s0)	c.s0=c.r0;
	if(a.s0>c.s0)	c.s0=a.s0;
	if(b.s0>c.s0)	c.s0=b.s0;
	if(a.r0+b.l0>c.s0)	c.s0=a.r0+b.l0;
	return c;
}int find(int l,int r,int x,int num){
	if(t[x].l0>=num)	return l;
	down(l,r,x);
	int mid=(l+r)>>1;
	if(t[ls].s0>=num)	return find(l,mid,ls,num);
	if(t[ls].r0+t[rs].l0>=num)	return mid-t[ls].r0+1;
	return find(mid+1,r,rs,num);
}int main(){
	fread(buf,1,5120000,stdin);
	n=getint();	m=getint();
	build(1,n,1);
	char op[2];
	int x,y,an=0;
	while(m--){
		if(getop()=='A'){
			x=getint();
			if(ask(1,n,1,n,1).s0<x){
				an++;
				continue;
			}y=find(1,n,1,x);
			modify1(y,y+x-1,1,n,1);
		}else{
			x=getint();y=getint();
			modify0(x,y,1,n,1);
		}
	}cout << an << endl; 
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter