1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
const int up=0;
const int left=1;
const int down=2;
const int right=3;
inline int turn(int direct){
    switch(direct){
        case up:return down;
        case down:return up;
        case left:return right;
        case right:return left;
    }
}
struct Unit{
    Unit* links[4];
    Unit(){for(int i=0;i<4;++i)links[i]=NULL;}
    void insert(Unit* node, int direct){
        int back=turn(direct);
        node->links[direct]=links[direct];
        node->links[back]=this;
        links[direct]->links[back]=node;
        links[direct]=node;
    }
    void cut(){
        for(int i=0;i<4;++i){
            int back=turn(i);
            links[i]->links[back]=links[back];
        }
    }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX