Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

splay竟然超时了。这题有什么特别需要注意的吗？

Posted by AllwaysLoser at 2009-04-25 14:37:17 on Problem 3580

我不明白了
/*
5
1 
2 
3 
4 
5
2
ADD 2 4 1
MIN 4 5
*/
// 5
#include <cstdio>
using namespace std;
#define NODEEXIT 1
#define NODEREVERSE 2
#define BigNum 1100000000
struct Tnode{
       int mark;
       int v,m,sz,delta;
       Tnode *fa,*lc,*rc;
       int type();
}_no,*no;
Tnode tpool[200000];
int tpc;
Tnode *root;
int Tnode::type(){
    if (fa==no)return 0;
    if (fa->lc==this)return -1;
    return 1;
}
inline Tnode* getNew(){Tnode *r;
       r=&(tpool[tpc++]);
       r->sz=1;r->mark=NODEEXIT;r->delta=0;
       return r;
}
void NoMark(Tnode *p){if (p==no)return;
     Tnode *t;
     if (p->mark&NODEREVERSE){
        t=p->lc;p->lc=p->rc;p->rc=t;
        if (p->lc!=no)p->lc->mark^=NODEREVERSE;
        if (p->rc!=no)p->rc->mark^=NODEREVERSE;
        p->mark&=~NODEREVERSE;
     }
     if (p->delta){
        if (p->lc!=no){
           p->lc->delta+=p->delta;
           p->lc->v+=p->delta;
           p->lc->m+=p->delta;
        }
        if (p->rc!=no){
           p->rc->delta+=p->delta;
           p->rc->v+=p->delta;
           p->rc->m+=p->delta;
        }
        p->delta=0;
     }
}
void Correct(Tnode *p){
     p->sz=p->lc->sz+p->rc->sz+((p->mark&NODEEXIT)&&1);
     p->m=BigNum;
     if (p->mark&NODEEXIT)p->m=p->v;
     if (p->lc->m+p->delta<p->m)p->m=p->lc->m+p->delta;
     if (p->rc->m+p->delta<p->m)p->m=p->rc->m+p->delta;
}
void zig(Tnode *p){
     if (root==p->fa)root=p;
     NoMark(p);
     p->fa->lc=p->rc;
     if (p->rc!=no)p->rc->fa=p->fa;
     p->rc=p->fa;
     p->fa=p->fa->fa;
     if (p->fa!=no){
        if (p->rc->type()==1)p->fa->rc=p;
        else p->fa->lc=p;
     }
     p->rc->fa=p;
     Correct(p->rc);
     Correct(p);
}
void zag(Tnode *p){
     if (root==p->fa){
        root=p;
     }
     NoMark(p);
     p->fa->rc=p->lc;
     if (p->lc!=no)p->lc->fa=p->fa;
     p->lc=p->fa;
     p->fa=p->fa->fa;
     if (p->fa!=no){
        if (p->lc->type()==1){
           p->fa->rc=p;
        }
        else {
             p->fa->lc=p;
        }
     }
     p->lc->fa=p;
     Correct(p->lc);
     Correct(p);
}
void Splay(Tnode *p){
     while (p!=root){
           if (p->fa==root){
              if (p->type()==-1)zig(p);
              else zag(p);
           }else if (p->fa->type()==-1){
                 if (p->type()==-1){
                    zig(p->fa);
                    zig(p);
                 }else{
                       zag(p);
                       zig(p);
                 }
           }else{
                 if (p->type()==-1){
                    zig(p);
                    zag(p);
                 }else{
                       zag(p->fa);
                       zag(p);
                 }
           }
     }
}
void showTree(Tnode *x,int delta=0,int rev=0){
     if (x==no)return;
     rev^=((x->mark&NODEREVERSE)&&1);
     if (rev){
        showTree(x->rc,x->delta+delta,rev);
        if (x->mark&NODEEXIT)printf("%d ",x->v+delta);
        showTree(x->lc,x->delta+delta,rev);
     }else{
           showTree(x->lc,x->delta+delta,rev);
           if (x->mark&NODEEXIT)printf("%d ",x->v+delta);
           showTree(x->rc,x->delta+delta,rev);
     }
}
void outTree(Tnode *x,int dep=0){
     for (int i=0;i<dep;i++)putchar(' ');
     if (x==no){
        puts("*");
        return;
     }
     if (x->fa!=no && x->fa->rc!=x && x->fa->lc!=x)putchar(2);
     printf("v=%d m=%d sz=%d ma=%d de=%d\n",x->v,x->m,x->sz,int(x->mark),x->delta);
     outTree(x->lc,dep+1);
     outTree(x->rc,dep+1);
}
void Ins(int key,int v){
     Tnode *p,*q;
     if (root==no){
        root=getNew();
        root->v=root->m=v;
        root->fa=root->lc=root->rc=no;
        return;
     }
     p=root;
     while (1){
           NoMark(p);
           if (p->lc->sz==key && !(p->mark&NODEEXIT)){
              p->mark|=NODEEXIT;
              p->v=v;
              break;
           }
           if (p->lc->sz>=key){
              if (p->lc==no){
                 p->lc=getNew();
                 p->lc->v=p->lc->m=v;
                 p->lc->fa=p;p->lc->lc=p->lc->rc=no;
                 p=p->lc;
                 break;
              }
              p=p->lc;
           }else{
                 key-=p->lc->sz+((p->mark&NODEEXIT)&&1);
                 if (p->rc==no){
                    p->rc=getNew();
                    p->rc->v=p->rc->m=v;
                    p->rc->fa=p;p->rc->lc=p->rc->rc=no;
                    p=p->rc;
                    break;
                 }
                 p=p->rc;
           }
     }
     for (q=p;q!=no;q=q->fa)Correct(q);
     Splay(p);
}
Tnode* Find(int key){
       Tnode *p;
       p=root;
       while (1){
           NoMark(p);
           if (p->lc->sz==key && (p->mark&NODEEXIT))break;
           if (p->lc->sz>key)p=p->lc;
           else{
                key-=p->lc->sz+((p->mark&NODEEXIT)&&1);
                p=p->rc;
           }
     }
     return p;  
}
void Del(int key){
     Tnode *p,*q;
     p=Find(key);
     p->mark&=~NODEEXIT;
     q=p;
     while (q!=no){
           Correct(q);
           q=q->fa;
     }
     Splay(p);
}
Tnode* cutTree(int x,int y){
       Tnode *px,*py;
       if (x && y<root->sz-1){
          py=Find(y+1);Splay(py);
          px=Find(x-1);Splay(px);
          root=px->rc;
          Splay(py);
          root=px;
          return py->lc;
       }else if (x==0 && y<root->sz-1){
             py=Find(y+1);
             Splay(py);
             return py->lc;
       }else if (x){
             px=Find(x-1);
             Splay(px);
             return px->rc;
       }else return root;
}
void Add(int x,int y,int v){
     if (x>y)return;
     Tnode *p,*q;
     if (x==y){
        p=Find(x);Splay(p);
        p->v+=v;Correct(p);
        return;
     }
     p=cutTree(x,y);
     p->v+=v;p->delta+=v;
     for (q=p;q!=no;q=q->fa)Correct(q);
}
void Reverse(int x,int y){
     Tnode *p;
     if (x>=y)return;
     p=cutTree(x,y);
     p->mark^=NODEREVERSE;
     Splay(p);
}
void Revolve(int x,int y,int d){
     if (x>=y)return;
     d%=(y-x+1);
     if (!d)return;
     Tnode *p,*oldroot,*t,*l;
     p=cutTree(x,y);
     oldroot=root;
     root=p;
     t=Find(0);Splay(t);
     if (y==x+d){
        l=t->lc;t->lc=t->rc;t->rc=l;
        root=oldroot;
        return;
     }
     l=Find(y-x-d);
     root=t->rc;
     Splay(l);
     t->lc=l->rc;
     l->rc->fa=t;
     l->rc=no;
     Correct(l);
     Correct(t);
     root=oldroot;
}
int getMin(int x,int y){
    Tnode *p;
    if (x>y)return BigNum;
    if (x==y){
       p=Find(x);Splay(p);
       return p->v;
    }
    p=cutTree(x,y);
    return p->m;
}
int res[100000],rc;
int main()
{
    no=&_no;no->mark=0;no->m=no->v=BigNum;no->sz=no->delta=0;no->fa=no->lc=no->rc=no;
    tpc=0;
    int N,x,y,d,M;
    char cmd[20];
    scanf("%d",&N);
    root=no;
    for (int i=0;i<N;i++){
        scanf("%d",&x);
        Ins(i,x);
    }
    scanf("%d",&M);
    rc=0;
    for (int i=0;i<M;i++){
        scanf("%s",cmd);
        switch (cmd[0]){
               case 'A':
                    scanf("%d %d %d",&x,&y,&d);
                    Add(x-1,y-1,d);
                    break;
               case 'I':
                    scanf("%d %d",&x,&d);
                    Ins(x,d);
                    break;
               case 'D':
                    scanf("%d",&x);
                    Del(x-1);
                    break;
               case 'M':
                    scanf("%d %d",&x,&y);
                    res[rc++]=getMin(x-1,y-1);
                    break;
               case 'R':
                    if (cmd[3]=='E'){
                       scanf("%d %d",&x,&y);
                       Reverse(x-1,y-1);
                    }else if (cmd[3]=='O'){
                          scanf("%d %d %d",&x,&y,&d);
                          Revolve(x-1,y-1,d);
                    }
                    break;
        }
    }
    for (int i=0;i<rc;i++)printf("%d\n",res[i]);
    getchar();getchar();
    return 0;
}

Followed by:

写了两天，依然TLE。大牛救救我！ (7637) fanhqme 2009-04-25 19:57:45
求救！对各位大牛顶礼膜拜，救救我吧！ (8) AllwaysLoser 2009-04-25 20:40:08
精诚所至金石为开，发帖向路过的大牛们求救！ (3) fanhqme 2009-05-01 14:03:01
精诚所至金石为开，发帖向路过的大牛们求救！ (8094) AllwaysLoser 2009-05-01 14:03:56
精诚所至金石为开，恳请过路的大牛帮帮忙！ (25) AllwaysLoser 2009-05-01 21:50:18
精诚所至金石为开，虔诚苦等热心大牛！ (4) AllwaysLoser 2009-05-02 14:53:18
精诚所至金石为开，感动不了测评机就让我感动各位路过的神牛吧！ (20) AllwaysLoser 2009-05-08 20:07:15
我来说说。。。 (200) IceKingdom 2009-06-01 22:11:09
- 膜拜大牛！感谢热心人，等我ac以后一定会再重重感谢您的！ (0) fanhqme 2009-09-26 21:18:31
神牛啊……威武！ (8868) yc5_yc 2012-12-08 17:22:38

Post your reply here:

User ID:
Password:
Title:

Content:

> 我不明白了
> /*
> 5
> 1 
> 2 
> 3 
> 4 
> 5
> 2
> ADD 2 4 1
> MIN 4 5
> */
> // 5
> #include <cstdio>
> using namespace std;
> #define NODEEXIT 1
> #define NODEREVERSE 2
> #define BigNum 1100000000
> struct Tnode{
>        int mark;
>        int v,m,sz,delta;
>        Tnode *fa,*lc,*rc;
>        int type();
> }_no,*no;
> Tnode tpool[200000];
> int tpc;
> Tnode *root;
> int Tnode::type(){
>     if (fa==no)return 0;
>     if (fa->lc==this)return -1;
>     return 1;
> }
> inline Tnode* getNew(){Tnode *r;
>        r=&(tpool[tpc++]);
>        r->sz=1;r->mark=NODEEXIT;r->delta=0;
>        return r;
> }
> void NoMark(Tnode *p){if (p==no)return;
>      Tnode *t;
>      if (p->mark&NODEREVERSE){
>         t=p->lc;p->lc=p->rc;p->rc=t;
>         if (p->lc!=no)p->lc->mark^=NODEREVERSE;
>         if (p->rc!=no)p->rc->mark^=NODEREVERSE;
>         p->mark&=~NODEREVERSE;
>      }
>      if (p->delta){
>         if (p->lc!=no){
>            p->lc->delta+=p->delta;
>            p->lc->v+=p->delta;
>            p->lc->m+=p->delta;
>         }
>         if (p->rc!=no){
>            p->rc->delta+=p->delta;
>            p->rc->v+=p->delta;
>            p->rc->m+=p->delta;
>         }
>         p->delta=0;
>      }
> }
> void Correct(Tnode *p){
>      p->sz=p->lc->sz+p->rc->sz+((p->mark&NODEEXIT)&&1);
>      p->m=BigNum;
>      if (p->mark&NODEEXIT)p->m=p->v;
>      if (p->lc->m+p->delta<p->m)p->m=p->lc->m+p->delta;
>      if (p->rc->m+p->delta<p->m)p->m=p->rc->m+p->delta;
> }
> void zig(Tnode *p){
>      if (root==p->fa)root=p;
>      NoMark(p);
>      p->fa->lc=p->rc;
>      if (p->rc!=no)p->rc->fa=p->fa;
>      p->rc=p->fa;
>      p->fa=p->fa->fa;
>      if (p->fa!=no){
>         if (p->rc->type()==1)p->fa->rc=p;
>         else p->fa->lc=p;
>      }
>      p->rc->fa=p;
>      Correct(p->rc);
>      Correct(p);
> }
> void zag(Tnode *p){
>      if (root==p->fa){
>         root=p;
>      }
>      NoMark(p);
>      p->fa->rc=p->lc;
>      if (p->lc!=no)p->lc->fa=p->fa;
>      p->lc=p->fa;
>      p->fa=p->fa->fa;
>      if (p->fa!=no){
>         if (p->lc->type()==1){
>            p->fa->rc=p;
>         }
>         else {
>              p->fa->lc=p;
>         }
>      }
>      p->lc->fa=p;
>      Correct(p->lc);
>      Correct(p);
> }
> void Splay(Tnode *p){
>      while (p!=root){
>            if (p->fa==root){
>               if (p->type()==-1)zig(p);
>               else zag(p);
>            }else if (p->fa->type()==-1){
>                  if (p->type()==-1){
>                     zig(p->fa);
>                     zig(p);
>                  }else{
>                        zag(p);
>                        zig(p);
>                  }
>            }else{
>                  if (p->type()==-1){
>                     zig(p);
>                     zag(p);
>                  }else{
>                        zag(p->fa);
>                        zag(p);
>                  }
>            }
>      }
> }
> void showTree(Tnode *x,int delta=0,int rev=0){
>      if (x==no)return;
>      rev^=((x->mark&NODEREVERSE)&&1);
>      if (rev){
>         showTree(x->rc,x->delta+delta,rev);
>         if (x->mark&NODEEXIT)printf("%d ",x->v+delta);
>         showTree(x->lc,x->delta+delta,rev);
>      }else{
>            showTree(x->lc,x->delta+delta,rev);
>            if (x->mark&NODEEXIT)printf("%d ",x->v+delta);
>            showTree(x->rc,x->delta+delta,rev);
>      }
> }
> void outTree(Tnode *x,int dep=0){
>      for (int i=0;i<dep;i++)putchar(' ');
>      if (x==no){
>         puts("*");
>         return;
>      }
>      if (x->fa!=no && x->fa->rc!=x && x->fa->lc!=x)putchar(2);
>      printf("v=%d m=%d sz=%d ma=%d de=%d\n",x->v,x->m,x->sz,int(x->mark),x->delta);
>      outTree(x->lc,dep+1);
>      outTree(x->rc,dep+1);
> }
> void Ins(int key,int v){
>      Tnode *p,*q;
>      if (root==no){
>         root=getNew();
>         root->v=root->m=v;
>         root->fa=root->lc=root->rc=no;
>         return;
>      }
>      p=root;
>      while (1){
>            NoMark(p);
>            if (p->lc->sz==key && !(p->mark&NODEEXIT)){
>               p->mark|=NODEEXIT;
>               p->v=v;
>               break;
>            }
>            if (p->lc->sz>=key){
>               if (p->lc==no){
>                  p->lc=getNew();
>                  p->lc->v=p->lc->m=v;
>                  p->lc->fa=p;p->lc->lc=p->lc->rc=no;
>                  p=p->lc;
>                  break;
>               }
>               p=p->lc;
>            }else{
>                  key-=p->lc->sz+((p->mark&NODEEXIT)&&1);
>                  if (p->rc==no){
>                     p->rc=getNew();
>                     p->rc->v=p->rc->m=v;
>                     p->rc->fa=p;p->rc->lc=p->rc->rc=no;
>                     p=p->rc;
>                     break;
>                  }
>                  p=p->rc;
>            }
>      }
>      for (q=p;q!=no;q=q->fa)Correct(q);
>      Splay(p);
> }
> Tnode* Find(int key){
>        Tnode *p;
>        p=root;
>        while (1){
>            NoMark(p);
>            if (p->lc->sz==key && (p->mark&NODEEXIT))break;
>            if (p->lc->sz>key)p=p->lc;
>            else{
>                 key-=p->lc->sz+((p->mark&NODEEXIT)&&1);
>                 p=p->rc;
>            }
>      }
>      return p;  
> }
> void Del(int key){
>      Tnode *p,*q;
>      p=Find(key);
>      p->mark&=~NODEEXIT;
>      q=p;
>      while (q!=no){
>            Correct(q);
>            q=q->fa;
>      }
>      Splay(p);
> }
> Tnode* cutTree(int x,int y){
>        Tnode *px,*py;
>        if (x && y<root->sz-1){
>           py=Find(y+1);Splay(py);
>           px=Find(x-1);Splay(px);
>           root=px->rc;
>           Splay(py);
>           root=px;
>           return py->lc;
>        }else if (x==0 && y<root->sz-1){
>              py=Find(y+1);
>              Splay(py);
>              return py->lc;
>        }else if (x){
>              px=Find(x-1);
>              Splay(px);
>              return px->rc;
>        }else return root;
> }
> void Add(int x,int y,int v){
>      if (x>y)return;
>      Tnode *p,*q;
>      if (x==y){
>         p=Find(x);Splay(p);
>         p->v+=v;Correct(p);
>         return;
>      }
>      p=cutTree(x,y);
>      p->v+=v;p->delta+=v;
>      for (q=p;q!=no;q=q->fa)Correct(q);
> }
> void Reverse(int x,int y){
>      Tnode *p;
>      if (x>=y)return;
>      p=cutTree(x,y);
>      p->mark^=NODEREVERSE;
>      Splay(p);
> }
> void Revolve(int x,int y,int d){
>      if (x>=y)return;
>      d%=(y-x+1);
>      if (!d)return;
>      Tnode *p,*oldroot,*t,*l;
>      p=cutTree(x,y);
>      oldroot=root;
>      root=p;
>      t=Find(0);Splay(t);
>      if (y==x+d){
>         l=t->lc;t->lc=t->rc;t->rc=l;
>         root=oldroot;
>         return;
>      }
>      l=Find(y-x-d);
>      root=t->rc;
>      Splay(l);
>      t->lc=l->rc;
>      l->rc->fa=t;
>      l->rc=no;
>      Correct(l);
>      Correct(t);
>      root=oldroot;
> }
> int getMin(int x,int y){
>     Tnode *p;
>     if (x>y)return BigNum;
>     if (x==y){
>        p=Find(x);Splay(p);
>        return p->v;
>     }
>     p=cutTree(x,y);
>     return p->m;
> }
> int res[100000],rc;
> int main()
> {
>     no=&_no;no->mark=0;no->m=no->v=BigNum;no->sz=no->delta=0;no->fa=no->lc=no->rc=no;
>     tpc=0;
>     int N,x,y,d,M;
>     char cmd[20];
>     scanf("%d",&N);
>     root=no;
>     for (int i=0;i<N;i++){
>         scanf("%d",&x);
>         Ins(i,x);
>     }
>     scanf("%d",&M);
>     rc=0;
>     for (int i=0;i<M;i++){
>         scanf("%s",cmd);
>         switch (cmd[0]){
>                case 'A':
>                     scanf("%d %d %d",&x,&y,&d);
>                     Add(x-1,y-1,d);
>                     break;
>                case 'I':
>                     scanf("%d %d",&x,&d);
>                     Ins(x,d);
>                     break;
>                case 'D':
>                     scanf("%d",&x);
>                     Del(x-1);
>                     break;
>                case 'M':
>                     scanf("%d %d",&x,&y);
>                     res[rc++]=getMin(x-1,y-1);
>                     break;
>                case 'R':
>                     if (cmd[3]=='E'){
>                        scanf("%d %d",&x,&y);
>                        Reverse(x-1,y-1);
>                     }else if (cmd[3]=='O'){
>                           scanf("%d %d %d",&x,&y,&d);
>                           Revolve(x-1,y-1,d);
>                     }
>                     break;
>         }
>     }
>     for (int i=0;i<rc;i++)printf("%d\n",res[i]);
>     getchar();getchar();
>     return 0;
> }

Home Page Go Back To top