SPOJ/OTOCI.cc

   1 #include <cstdio>
   2 #include <algorithm>
   3
   4 #define REP(i,n) for (int i=1; i<=n; ++i)
   5
   6 const int maxn = 30000 + 10;
   7
   8 class node
   9 {
  10         static node* nil;
  11         #define nil node::nil
  12
  13         node *ch[2],*p;
  14         int sum,val;
  15         bool rev;
  16
  17         inline int sgn()
  18         {
  19                 return p->ch[0] == this ? 0 : p->ch[1] == this ? 1 : -1;
  20         }
  21
  22         inline void sc(int d, node* c) { ch[d] = c; c->p = this; }
  23
  24         inline void update()
  25         {
  26                 sum = ch[0]->sum + ch[1]->sum + val;
  27         }
  28
  29         inline void relax()
  30         {
  31                 if (rev)
  32                 {
  33                         std::swap(ch[0],ch[1]);
  34                         ch[0]->rev ^= 1, ch[1]->rev ^= 1;
  35                         rev = 0;
  36                 }
  37         }
  38
  39         inline void rotate(int d)
  40         {
  41                 node *x = p, *y = x->p;
  42                 if (~x->sgn()) y->sc(x->sgn(), this); else p = y;
  43                 x->sc(d, ch[d^1]), sc(d^1,x);
  44                 x->update();
  45         }
  46
  47         inline void rotate() { rotate(sgn()); }
  48         inline void zig() { rotate(0); }
  49         inline void zag() { rotate(1); }
  50
  51         inline void fix()
  52         {
  53                 if (~sgn()) p->fix();
  54                 relax();
  55         }
  56
  57         inline node* splay()
  58         {
  59                 fix();
  60                 while (~sgn()) rotate();
  61                 update();
  62                 return this;
  63         }
  64
  65         inline node* expose()
  66         {
  67                 node *x = this, *y = nil;
  68                 do
  69                 {
  70                         x->splay();
  71                         x->ch[1] = y, x->update();
  72                         y = x, x = x->p;
  73                 } while (x != nil);
  74                 return y;
  75         }
  76
  77         inline node* root()
  78         {
  79                 node *x;
  80                 for (x = expose(); x->relax(), x->ch[0] != nil; x = x->ch[0]);
  81                 return x;
  82         }
  83
  84         inline node* evert()
  85         {
  86                 expose()->rev ^= 1;
  87                 return this;
  88         }
  89
  90 public:
  91         inline node(int v = 0): p(nil), val(v)
  92         {
  93                 ch[0] = ch[1] = nil;
  94                 sum = rev = 0;
  95         }
  96
  97         bool link(node *v)
  98         {
  99                 if (root() == v->root()) return false; else
 100                 {
 101                         evert(), splay();
 102                         p = v;
 103                         return true;
 104                 }
 105         }
 106
 107         void modify(int x) { splay(), val = x; }
 108
 109         int query(node *x)
 110         {
 111                 if (root() != x->root()) return -1; else
 112                 {
 113                         expose();
 114                         node *y = nil;
 115                         int res = 0;
 116                         do
 117                         {
 118                                 x->splay();
 119                                 if (x->p == nil) return x->ch[1]->sum + x->val + y->sum;
 120                                 x->ch[1] = y, x->update();
 121                                 y = x, x = x->p;
 122                         } while (x != nil);
 123                 }
 124         }
 125 } *v[maxn], *nil = new node();
 126
 127 int main()
 128 {
 129         int n,tmp;
 130         std::scanf("%d",&n);
 131         REP(i,n)
 132                 std::scanf("%d",&tmp), v[i] = new node(tmp);
 133         int x,y,q;
 134         char opt[20];
 135         std::scanf("%d",&q);
 136         while (q--)
 137         {
 138                 std::scanf(" %s %d %d",opt,&x,&y);
 139                 int ans;
 140                 switch (opt[0])
 141                 {
 142                         case 'b':
 143                                 v[x]->link(v[y]) ? std::puts("yes") : std::puts("no");
 144                                 break;
 145                         case 'p':
 146                                 v[x]->modify(y);
 147                                 break;
 148                         case 'e':
 149                                 ans = v[x]->query(v[y]);
 150                                 ans == -1 ? std::puts("impossible") : std::printf("%d\n",ans);
 151                                 break;
 152                 }
 153         }
 154         return 0;
 155 }