当前位置：首页 -> 基础 -> c++编程基础

hdu 3487 Play with Chain (Splay树) 区间切割 插入 翻转(一)

2014-11-24 02:49:13 · 作者: · 浏览: 5
标签: hdu 3487 Play with Chain Splay 区间 切割 插入 翻转

hdu 3487 Play with Chain (Splay树) 区间切割 插入 翻转

关键注意：down 和 up


find，kth，next，pre， RTO等当有flip时，都要down

切割之后，up

插入之后，修改pre


指针：

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; #define FF(i, a, b) for(int i = (a); i < (b); ++i) #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FD(i, b, a) for(int i = (b); i >= (a); --i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(a, v) memset(a, v, sizeof(a)) #define PB push_back #define MP make_pair typedef long long LL; const int INF = 0x3f3f3f3f; const int maxn = 310000; #define ll x->ch[0] #define rr x->ch[1] #define KT (root->ch[1]->ch[0]) struct Node{ Node* ch[2]; int v; int s; int flip; Node(){} ///比较的是位序 int cmp(int x)/// { int ss = ch[0]->s; if (x == ss + 1) return -1; else return x < ss + 1   0 : 1; } void up() { s = ch[0]->s + ch[1]->s + 1; } void reverse() { swap(ch[0], ch[1]); flip ^= 1; } void pushdown() { if (flip) { ch[0]->reverse(); ch[1]->reverse(); flip = 0; } } }N[maxn], *null = &N[0]; vector
               
                ans; ///Splay维护一个序列 struct SplayTree{ Node *root; int tot; void Init(int n) { tot = 0; null->ch[0] = null->ch[1] = null; null->v = null->s = null->flip = 0; root = null; Newnode(root, -1); Newnode(root->ch[1], -1); Build(KT, 1, n); root->ch[1]->up(); root->up(); } void Newnode(Node* &x, int vv) { x = &N[++tot]; x->ch[0] = x->ch[1] = null; x->v = vv; x->s = 1; x->flip = 0; } void Build(Node* &x, int l, int r) { if (l > r) return ; int m = (l + r) >> 1; Newnode(x, m); Build(ll, l, m - 1); Build(rr, m + 1, r); x->up();//up } void Rotate(Node* &rt, int d) { Node* k = rt->ch[d ^ 1]; rt->ch[d ^ 1] = k->ch[d]; k->ch[d] = rt; rt->up(); k->up(); rt = k;//up } ///找到rt序列左数第k个元素并伸展到根 void Splay(Node* &rt, int k) { rt->pushdown();///pushdown int d = rt->cmp(k); if (d != -1) { if (d == 1) k -= rt->ch[0]->s + 1; Node* p = rt->ch[d]; p->pushdown();///pushdown int d2 = p->cmp(k); if (d2 != -1) { int k2 = k; if (d2 == 1) k2 -= p->ch[0]->s + 1; Splay(p->ch[d2], k2);///!!!!!!!!!!! if (d == d2) Rotate(rt, d ^ 1); else Rotate(rt->ch[d], d); } Rotate(rt, d ^ 1); } } void CUT() { int x, y, z; scanf("%d%d%d", &x, &y, &z); Node *tmp; Splay(root, x); Splay(root->ch[1], y - x + 2); tmp = KT; KT = null; root->ch[1]->up(); root->up();///!!! Splay(root, z + 1); Splay(root->ch[1], 1); KT = tmp; } void FLIP() { int x, y, z; scanf("%d%d", &x, &y); Splay(root, x); Splay(root->ch[1], y - x + 2); KT->reverse(); } void out(Node* x) { if (x == null) return ; x->pushdown();///pushdown out(ll); if (x->v > 0) ans.push_back(x->v); out(rr); } }sp; int main () { int n, m; char op[5]; ans.clear(); while (~scanf("%d%d", &n, &m)) { if (n == -1 && m == -1) break; sp.Init(n); for (int i = 1; i <= m; i++) { scanf("%s", op); if (op[0] == 'C') sp.CUT(); else sp.FLIP(); } sp.out(sp.root); int nn = ans.size(); REP(i, nn) { if(i) printf(" "); printf("%d", ans[i]); } printf("\n"); ans.clear(); } return 0; } /*** ///合并left和right。假设left的所有元素比right小。注意：right可以为null，left不可以 Node* Merge(Node* left, Node* right) { splay(left, left->s); left->ch[1] = right; left->up();//up return left; } ///把rt的前k小的节点放在left里，其它放在right里。1<= k <= rt->s.当k = o->s时，right = null void Split(Node* rt, int k, Node* &left, Node* &right) { splay(rt, k); left = rt; right = rt->ch[1]; left->ch[1] = null;/// left->up();//up } void solve(int a, int b) { Node *left, *right, *mid, *tmp_right; split(root, a, left, tmp_right);///!!! split(tmp_right, b - a + 1, mid, right); mid->flip ^= 1; root = merge(merge(left, right), mid); } void debug(Node* &o) { if(o == null) return ; printf("%d(",o->v); if(o->ch[0]!=null) printf("%d,",o->ch[0]->v); else printf("null,"); if(o->ch[1]!=null) printf("%d",o->ch[1]->v); else printf("null"); puts(")"); if(o->ch[0]!=null) debug(o->ch[0]); if(o->ch[1]!=null) debug(o->ch[1]); } */

数组： 

#pragma comment(linker, "/STACK:102400000000,102400000000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 using namespace std; //LOOP #define FF(i, a, b) for(int i = (a); i < (b); ++i) #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FED(i, b, a) for(int i = (b); i>= (a);