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

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

好久没来了。除个草吧。

 

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;
}

 

Avatar_small
jnanabhumiap.in 说:
2024年1月09日 14:43

JNANABHUMI AP provides all latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources full information on each topic which can be accessed through Internet. To ensure that every readers get’s what important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who have passion to provide engaging content which is accurate, interesting and worthy to read. We are mope like a web community where you can find different information’s, resources, topics on day to day incidents or news. We provide you the finest of web content on each and every topics possible with help of editorial and content team.


登录 *


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