POJ 2892 平衡树or线段树

题意：

给出直线上一系列的村庄，如果相邻村庄都没有被破坏，则两村庄是连接的，题目给出一系列的破坏操作，对指定号码的村庄进行破坏，还有一系列的询问操作，询问与指定号码的村庄直接相连或间接相连的村庄有几个，还有一个修复操作，是对最后破坏的村庄进行修复。

分析：

我们可以建立一棵平衡树，储存已经删除了的结点。

然后查询个数可以用平衡树找到比我大一点点的那个村庄和小一点点的那个村庄。

破坏的话就是插入了。

修复的话就是删除。

当然，线段树也可以实现这些操作。

插曲：

本来可以1A的。。。忘了删文件，又贡献WA一个。

第一次用类（对象）来写程序吖

code:

#include #include using namespace std;
const int N=1000000;
const int INF=0x7FFFFFFF;
int n,q,L[N],Lt=0,v[N];
class sbttype{
       public:
       int tot,root;
       struct treetype{int l,r,s,w;}tr[N];
       void Left(int &p){
            int t=tr[p].r;
            tr[p].r=tr[t].l;
            tr[t].l=p;
            tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
            p=t;
            tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
       }
       void Right(int &p){
            int t=tr[p].l;
            tr[p].l=tr[t].r;
            tr[t].r=p;
            tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
            p=t;
            tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
       }
       void Repair(int &p){
            bool flag=false;
            if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
              Right(p);
              flag=true;
            }
            if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
              Left(tr[p].l);
              Right(p);
              flag=true;
            }
            if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
              Left(p);
              flag=true;
            }
            if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
              Right(tr[p].r);
              Left(p);
              flag=true;
            }
            if (flag){
              Repair(tr[p].l);
              Repair(tr[p].r);
              Repair(p);
            }
       }
       void ins(int &p,int w){
            if (p==0){
              tr[++tot].l=0;
              tr[tot].r=0;
              tr[tot].s=1;
              tr[tot].w=w;
              p=tot;
              return;
            }
            if (w                      else ins(tr[p].r,w);
            Repair(p);
       }
       int del(int &p,int w){
           if (tr[p].w==w || tr[p].l==0 && w             int delnum=tr[p].w;
             if (tr[p].l==0 || tr[p].r==0) p=tr[p].l+tr[p].r;
                                      else tr[p].w=del(tr[p].l,INF);
             return delnum;
           }
           if (w                     else return del(tr[p].r,w);
       }
       int fewmin(int p,int w){
           if (p==0) return 0;
           if (w<=tr[p].w) return fewmin(tr[p].l,w);
           return max(tr[p].w,fewmin(tr[p].r,w));
       }
       int fewmax(int p,int w){
           if (p==0) return n+1;
           if (w>=tr[p].w) return fewmax(tr[p].r,w);
           return min(tr[p].w,fewmax(tr[p].l,w));
       }
}sbt;

int main(){
     freopen("input.txt","r",stdin);
     freopen("output.txt","w",stdout);
     scanf("%d%dn",&n,&q);
     sbt.root=0;
     sbt.tot=0;
     char ch;
     int x;
     for (int i=1;i<=q;i++){
         scanf("%c",&ch);
         if (ch==’R’){
           while (Lt>0 && v[L[Lt]]==0) Lt–;
           if (Lt>0){
             sbt.del(sbt.root,L[Lt]);
             v[L[Lt]]=0;
             Lt–;
           }
           scanf("n");
         }
         else if (ch==’Q’){
              scanf("%dn",&x);
              if (v[x]==1) {printf("0n");continue;}
              int tl=sbt.fewmin(sbt.root,x),tr=sbt.fewmax(sbt.root,x);
              printf("%dn",tr-tl-1);
         }
         else{
              scanf("%dn",&x);
              if (v[x]==1) continue;
              v[x]=1;
              sbt.ins(sbt.root,x);
              L[++Lt]=x;
         }
     }
    return 0;
}