标签存档：数据结构

题意：

给定N个二元组(Ki,Ai)

让你建立一棵笛卡尔树。

这个笛卡尔树实际上就是一个Treap.

k为二叉排序树的关键字，a为堆的关键字，堆是一个小根堆。

分析：

直接Treap会TLE,因为他给定了关键值，会退化成O(n^2)

然后我们可以根据Ki把结点从小到大排序，

然后每次都是最右边插入新的结点，

然后维护只需要左旋（他们叫右旋= =我觉得向左比较形象）

只有左旋的话我们可以注意到两个性质：

1、那么就是旋转以后，我这个结点不会增加新的儿子。

2、旋转以后，我必然是下一次插入的点的父结点。

别问我问什么。。。手画一下。。。证明这东西不是我这个级别做的事

然后我们可以注意到，从根开始连续向右到底这条路径可以看成一个栈！

每次左旋，就是一次出栈操作。

每次加结点，就是一次入栈操作。

于是，加结点和左旋操作数都<=n

所以，证明了这个算法的复杂度是：O(N)！

  

HINT

1A。

code：

#include #include #define N 60000
using namespace std;
struct re{int k,a,wz;}d[N];
struct trtype{int l,r,fa,zz;}tr[N];
int n,tot,mr,locate[N];

void left(int t){
    int p=tr[t].fa;
    tr[p].r=tr[t].l;
    tr[tr[t].l].fa=p;
    tr[t].l=p;
    tr[0].l=0; tr[0].r=0; tr[0].fa=0; tr[0].zz=0;
    if (tr[tr[p].fa].l==p) tr[tr[p].fa].l=t;
    if (tr[tr[p].fa].r==p) tr[tr[p].fa].r=t;
    tr[t].fa=tr[p].fa;
    tr[p].fa=t;
}   

void work(){
    tot=1; mr=1; tr[1].l=0; tr[1].r=0; tr[1].fa=0; tr[1].zz=1;
    for (int i=2;i<=n;i++){
        tot++;
        tr[tot].l=0; tr[tot].r=0; tr[tot].zz=i; tr[tot].fa=mr; tr[mr].r=tot;
        mr=tot;
        int now=tot;
        while (tr[now].fa!=0 && d[tr[tr[now].fa].zz].a>d[i].a)
          left(now);
    }   
}   

inline int wz(int x){
    return d[tr[x].zz].wz;
}   

void print(){
    printf("YESn");
    for (int i=1;i<=tot;i++) locate[d[tr[i].zz].wz]=i;
    for (int i=1;i<=n;i++){
        int t=locate[i];
        printf("%d %d %dn",wz(tr[t].fa),wz(tr[t].l),wz(tr[t].r));
    }   
}   

bool cmp(re x,re y){
    if (x.k    return false;
}   

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&d[i].k,&d[i].a);
        d[i].wz=i;
    }
    sort(&d[1],&d[n+1],cmp);
    work();
    print();
    return 0;
}   

题目：

http://www.wzoi.org/usaco/16%5C107.asp

总的来说就是给定一个数列(n<=100000)。

求一段连续的子数列，使得其中的数都xor在一起以后，得到的值最大。

分析：

自己想的原创算法吖

首先我们先分析一下xor这个运算的性质。

易得y=y xor t xor t（即偶数次xor同一个数，结果和原来一样）

于是我们可以设s[i]表示从a[1]xor到a[i]的值。(定义s[0]=0)

如果我们需要某一段[i,j]的xor值，就可以这样求s[j] xor s[i-1]，因为a[1]到a[i-1]的数被xor了两次！

这样，问题转化为：求max(s[i] xor s[j])，其中i∈[0,j]，j∈[1,n]。

于是现在要求的是取两个数的xor值最大！

首先我们应该明白，对于一个数字，我们可以把它看成一个长度为20的字符串(题目给的a[i]<=2^21-1)！

那么我们怎么比较这些字符串的大小呢？

很明显，我们是从首位扫到末尾！

于是假设我们现在枚举j，即已经确定了s[j]，然后在[0,j]的范围类找一个s[i] xor s[j]最大。

因为是当成字符串，我们用Trie树来储存那些数字！

然后从首位开始：

1、如果我这个s[j]的这一位是0，那么另外一个配对最好是1，

因为这样xor会得到1。如果找不到那就只能到0那边去。

2、如果我这个s[j]的这一位是1，那么另外一个配对最好是0，

理由同上。

因为越前的位在大小上影响更大，所以我们这样就贪心的走一遍Trie树，

所得的结果就是和s[j]配对最大的s[i]。

然后统计每个j对应的最大值，输出结果即可。

HINT

UASCO给的空间比较小，用指针可以过，但静态空间的Trie就不能开到极限那么大，开小一点就能过。

code：

/*
ID:jie22221
TASK:cowxor
LANG:C++
*/
#include const int N=111111;
struct treetype{int l,r,dep;}T[5*N];
struct gtp{int x,y,next;}g[N];
int n,a[N],s[N],ans=-1,ansi=0,ansj=0,tot,root,e=0,ls[5*N];

void addedge(int x,int y){
       e++;
       g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}

void add(int &p,int x,int dep,int link){
     if (p==0){
       tot++;
       p=tot;
       T[p].l=0;
       T[p].r=0;
       T[p].dep=dep;
     }
     if (dep==-1){
       addedge(p,link);
       return;
     }
     if (((1<                     else add(T[p].l,x,dep-1,link);
}

void init(){
     scanf("%d",&n);
     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
     for (int i=1;i<=n;i++){
         s[i]=s[i-1]^a[i];
         if (a[i]>ans){
           ans=a[i];
           ansi=i;
           ansj=i;
         }
         if (s[i]>ans){
           ans=s[i];
           ansi=1;
           ansj=i;
         }
     }
     tot=1;
     root=1;
     T[1].l=0;
     T[1].r=0;
     T[1].dep=22;
}

inline bool flag(int x,int y,int z){
       if (x>ans) return true;
       if (x       if (z       if (z>ansj) return false;
       if (z-y       return false;
}

void work(){
     add(root,s[1],22,1);
     for (int i=2;i<=n;i++){
         int p=root,now=0;
         for (int j=22;j>=0;j–)
           if ((s[i]|(1<               if (T[p].l!=0) {p=T[p].l; now|=1<                         else p=T[p].r;
             }
           else {
               if (T[p].r!=0) {p=T[p].r; now|=1<                         else p=T[p].l;
               }
           if (flag(now,g[ls[p]].y+1,i)){
              ans=now;
              ansi=g[ls[p]].y+1;
              ansj=i;
           }
         add(root,s[i],22,i);
     }
}

void print(){
     printf("%d %d %dn",ans,ansi,ansj);
}

int main(){
    freopen("cowxor.in","r",stdin);
    freopen("cowxor.out","w",stdout);
    init();
    work();
    print();
    return 0;
}

题意：

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

分析：

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

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

破坏的话就是插入了。

修复的话就是删除。

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

插曲：

本来可以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;
}

题意：

有一个大水桶，里面有N层。从上至下标为1、2、3…层。

如果破坏某一层（需要一定代价），那么水就会流到下一层。

另外，如果某一层的水量超过了他能负荷的水量。也会自动爆炸。。。水就会自动流到下一层。

现在你是恐怖分子，求怎样花费最少，可以破坏掉第N层。

分析：

首先水不可能是断流的。因为这样上面一层就没有任何意义了。

所以我们可以枚举水开始下流在哪一层。如果中间遇到水量不够自动破坏，就需要破坏掉这一层（即付出相应花费）。

这样到达每一个层的水量就是sum(i,j)其中i为开始流的层，j表示当前层。

我们发现这满足单调性。我们把i从N枚举到1。再用堆or平衡树维护即可。

因为i减1不会破坏他们的大小关系。

code:

#include #include using namespace std;
const int N=20000;
const int INF=0x7FFFFFFF;
struct headtype{int limit,w,p,i;} heap[100000];
int n,tot=0,water[N],limit[N],p[N],Swater=0,outtime[N];

void init(){
     scanf("%d",&n);
     for (int i=1;i<=n;i++)
       scanf("%d%d%d",&water[i],&limit[i],&p[i]);
}

inline int f(int t){
       return (heap[t].limit-heap[t].w);
}

void up(int k){
     while (k>1 && f(k/2)>f(k)){
           swap(heap[k],heap[k/2]);
           k/=2;
     }
}

void down(int k){
     while (k*2<=tot){
           int t;
           if (k*2+1<=tot && f(k*2+1)                                         else t=k*2;
           if (f(t)           k=t;
     }
}

void ins(int W,int L,int P,int i){
     tot++;
     heap[tot].w=W;
     heap[tot].limit=L;
     heap[tot].p=P;
     heap[tot].i=i;
     up(tot);
}

void del(){
     heap[1]=heap[tot];
     tot–;
     down(1);
}

void work(){
     int ans=INF,now=0,ansi=0;
     for (int i=n;i>=1;i–){
         Swater+=water[i];
         now+=p[i];
         ins(water[i]-Swater,limit[i],p[i],i);
         while (tot>0 && heap[1].w+Swater>heap[1].limit){
               now-=heap[1].p;
               outtime[heap[1].i]=i;
               del();
         }
         if (now           ans=now;
           ansi=i;
         }
     }
     for (int i=ansi;i<=n;i++)
       if (outtime[i]}

int main(){
    init();
    work();
}

题目：

https://www.spoj.pl/problems/PRO/

题意描述：

总共N天，每天取已加入的数的最大值和最小值相减并累加到ans，并删掉这两个数。

数据保证每天至少有两个数可以删。

解题分析：

这题可以建两个堆，然后按题意模拟，但是用平衡树更方便。

我用的是SBT。比堆更简短。

插曲：

WA到2B去了。。。原来是要用INT64

code:

#include #include #include #define N 1000000
using namespace std;
struct sbttype{int l,r,w,s;}tr[N];
int a[N],tot=0,n,root=0;

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<=tr[p].w) ins(tr[p].l,w);
               else ins(tr[p].r,w);
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    repair(p);
}

int del(int &p,int w){
    tr[p].s–;
    if (tr[p].w==w || tr[p].l==0 && w<=tr[p].w || tr[p].r==0 && w>tr[p].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,0x7FFFFFFF);
        return delnum;
    }
    if (w<=tr[p].w) return del(tr[p].l,w);
               else return del(tr[p].r,w);
}

int getmax(int k){
    int p=k;
    while (tr[p].r!=0) p=tr[p].r;
    return tr[p].w;
}

int getmin(int k){
    int p=k;
    while (tr[p].l!=0) p=tr[p].l;
    return tr[p].w;
}

int main(){
      while (cin >> n){
        tot=0; root=0;
        long long ans=0;
        for (int i=1;i<=n;i++){
            int num;
            scanf("%d",&num);
            for (int j=1;j<=num;j++){
                int tmp;
                scanf("%d",&tmp);
                ins(root,tmp);
            }
            int tx=getmax(root),ty=getmin(root);
            ans+=(tx-ty);
            del(root,tx);
            del(root,ty);
        }
        cout << ans << endl;
      }
    return 0;
}