ZOJ 3324 Machine線分数区間連結
3374 ワード
作り方:比較的水的で、タイトルによると、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;
}