Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

写了两天,依然TLE。大牛救救我!

Posted by fanhqme at 2009-04-25 19:57:45 on Problem 3580
In Reply To:splay竟然超时了。这题有什么特别需要注意的吗? Posted by:AllwaysLoser at 2009-04-25 14:37:17
/*
5
1 
2 
3 
4 
5
2
ADD 2 4 1
MIN 4 5
*/
// 5
#include <cstdio>
using namespace std;
#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=0;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+1;
     p->m=BigNum;
     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 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){
              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+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)break;
           if (p->lc->sz>key)p=p->lc;
           else{
                key-=p->lc->sz+1;
                p=p->rc;
           }
     }
     return p;  
}
void Del(int key){
     Tnode *p,*q,*oldroot;
     p=Find(key);
     if (p->lc==no && p->rc==no){
        if (p->type()==-1)p->fa->lc=no;
        else p->fa->rc=no;
        p=p->fa;
     }else if (p->lc==no){
        p->rc->fa=p->fa;
        if (p->type()==-1)p->fa->lc=p->rc;
        else p->fa->rc=p->rc;
        p=p->fa;
     }else{
           oldroot=root;
           root=p->lc;
           q=Find(p->sz-1);
           Splay(q);
           root=oldroot;
           p->lc->rc=p->rc;p->rc->fa=p->lc;
           p->lc->fa=p->fa;
           if (p->type()==-1)p->fa->lc=p->lc;
           else p->fa->rc=p->lc;
           p=p->lc;
     }
     for (q=p;q!=no;q=q->fa)Correct(q);
     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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator