[ZOJ3324 Machine]线段树

【算法分析】
维护4个域：
fl:最左边的点是否在原位，
fr:最右边的点是否在原位，
c:这条线段被压下多少次
sum:这条线段上有多少个连续部分。
然后维护即可。
要注意到题目中一个很重要的条件：
r i j means the pressure acting on blocks from number i to j is released. i and j is always the effective range of an existing pressure (inclusive, 0 <= i <= j < n).
【CODE】
#include #include #include #include using namespace std;
const int N=200005;
int n,tot,LEN;
int xl[N];
struct opnode{int l,r,t;}op[N];
struct node{int l,r,fl,fr,c,sum;}tr[N*4];

int Find(int x){
int l=1,r=tot,mid;
while (l mid=(l+r)/2;
if (x>xl[mid]) l=mid+1;
else r=mid;
}
return l;
}

void input(){
cin >> LEN >> n;
char type;
for (int i=1;i<=n;i++){
type=getchar();
while (type==’ ‘ || type==’n’) type=getchar();
scanf("%d%d",&op[i].l,&op[i].r);
if (type==’p’) op[i].t=1;
else op[i].t=0;
}

tot=0;
for (int i=1;i<=n;i++){
xl[++tot]=op[i].l;
xl[++tot]=op[i].r;
if (op[i].l>0) xl[++tot]=op[i].l-1;
xl[++tot]=op[i].l+1;
xl[++tot]=op[i].r-1;
if (op[i].r }
sort(xl+1,xl+tot+1);
int nt=0;
for (int i=1;i<=tot;i++)
if (!nt || xl[i]!=xl[nt])
xl[++nt]=xl[i];
tot=nt;
for (int i=1;i<=n;i++){
op[i].l=Find(op[i].l);
op[i].r=Find(op[i].r);
}
}

void build(int p,int l,int r){
tr[p].l=l; tr[p].r=r; tr[p].fl=tr[p].fr=1; tr[p].c=0; tr[p].sum=1;
if (l==r) return;
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}

void update(int p){
if (tr[p].c) return;
tr[p].sum=tr[p*2].sum+tr[p*2+1].sum;
if (tr[p*2].fr && tr[p*2+1].fl) tr[p].sum–;
tr[p].fl=tr[p*2].fl; tr[p].fr=tr[p*2+1].fr;
}

void ins(int p,int l,int r){
if (r if (l<=tr[p].l && tr[p].r<=r){
tr[p].c++;
tr[p].sum=tr[p].fl=tr[p].fr=0;
return;
}
ins(p*2,l,r);
ins(p*2+1,l,r);
update(p);
}

void del(int p,int l,int r){
if (r if (l<=tr[p].l && tr[p].r<=r){
tr[p].c–;
if (!tr[p].c)
if (tr[p].l==tr[p].r) {tr[p].sum=tr[p].fl=tr[p].fr=1;}
else update(p);
return;
}
del(p*2,l,r);
del(p*2+1,l,r);
update(p);
}

int main(){
int Tc;
cin >> Tc;
for (int k=1;k<=Tc;k++){
printf("Case #%d:n",k);
input();
build(1,1,tot);
for (int i=1;i<=n;i++){
if (op[i].t) ins(1,op[i].l,op[i].r);
else del(1,op[i].l,op[i].r);
printf("%dn",tr[1].sum);
}
}
}