ZOJ 3324 Machine線分数区間連結

作り方:比較的水的で、タイトルによると、R操作のたびに凹んだ位置だけに対して、結点は1つの区間の中で高さが最も小さい区間を記録すればよい.

#include<cstdio>
#include<cstring>
#include<algorithm>
#define left l,m,x<<1
#define right m+1,r,x<<1|1
const int LMT=80003;
using namespace std;
struct li
{
	int l,r;
	char ord;
}line[20003];
int sum[LMT<<2],lsum[LMT<<2],rsum[LMT<<2],cov[LMT<<2],lev[LMT<<2],myx[LMT],cnt;
void build(int l,int r,int x)
{
	sum[x]=1;
	lsum[x]=rsum[x]=r-l+1;
	cov[x]=lev[x]=0;
	if(l==r)return;
	int m=(l+r)>>1;
	build(left);build(right);
}
inline int min(int a,int b)
{
	return a<b?a:b;
}
void act(int ope,int x)
{
	lev[x]+=ope;
	cov[x]+=ope;
}
void cut(int x)
{
	if(cov[x])
	{
		act(cov[x],x<<1);
		act(cov[x],x<<1|1);
		cov[x]=0;
	}
}
void pushup(int x,int len)
{
	lev[x]=min(lev[x<<1],lev[x<<1|1]);
	if(lev[x<<1]==lev[x<<1|1])
	{
		lsum[x]=lsum[x<<1];rsum[x]=rsum[x<<1|1];
		sum[x]=sum[x<<1]+sum[x<<1|1];
		if(lsum[x<<1]==len-(len>>1))lsum[x]+=lsum[x<<1|1];
		if(rsum[x<<1|1]==len>>1)rsum[x]+=rsum[x<<1];
		if(rsum[x<<1]&&lsum[x<<1|1])sum[x]--;
	}
	else if(lev[x<<1]<lev[x<<1|1])
	{
		sum[x]=sum[x<<1];
		lsum[x]=lsum[x<<1];
		rsum[x]=0;
	}
	else
	{
		sum[x]=sum[x<<1|1];
		lsum[x]=0;
		rsum[x]=rsum[x<<1|1];
	}
}
void update(int op,int L,int R,int l,int r,int x)
{
	if(L<=l&&r<=R)
	{
		cov[x]+=op;lev[x]+=op;
		return ;
	}
	cut(x);
	int m=(l+r)>>1;
	if(L<=m)update(op,L,R,left);
	if(R>m)update(op,L,R,right);
	pushup(x,r-l+1);
}
int find(int x)
{
	int m,l=0,r=cnt-1;
	while(l<=r)
	{
		m=(l+r)>>1;
		if(myx[m]==x)return m;
		if(myx[m]>x)r=m-1;
		else l=m+1;
	}
	return -1;
}
int main(void)
{
	int T,n,i,t,I,m;
	scanf("%d",&T);
	for(I=1;I<=T;I++)
	{
		cnt=0;
		scanf("%d%d",&n,&m);
		myx[cnt++]=0;
		myx[cnt++]=n-1;
		for(i=0;i<m;i++)
		{
			line[i].ord=getchar();
			while(line[i].ord!='p'&&line[i].ord!='r')line[i].ord=getchar();
			scanf("%d%d",&line[i].l,&line[i].r);
			myx[cnt++]=line[i].l;
			myx[cnt++]=line[i].r;
		}
		sort(myx,myx+cnt);
		t=1;
		for(i=1;i<cnt;i++)if(myx[i]!=myx[i-1])myx[t++]=myx[i];
		cnt=t;
		for(i=1;i<t;i++)
			if(myx[i]-myx[i-1]>1)myx[cnt++]=myx[i-1]+1;
        sort(myx,myx+cnt);
		printf("Case #%d:
",I);
		build(0,cnt-1,1);
		for(i=0;i<m;i++)
		{
			line[i].l=find(line[i].l);
			line[i].r=find(line[i].r);
			update(line[i].ord=='r'?-1:1,line[i].l,line[i].r,0,cnt-1,1);
			printf("%d
",sum[1]*(lev[1]==0));
		}
	}
	return 0;
}