poj3237--Tree树链剖分

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 using namespace std;
  7 typedef unsigned long long ull;
  8 typedef long long ll;
  9 const int inf = 0x3f3f3f3f;
 10 const double eps = 1e-8;
 11 const int maxn = 1e5+10;
 12 struct
 13 {
 14     int to,next;
 15 }e[maxn<<1];
 16 int head[maxn],edge;
 17 void add(int x,int y)
 18 {
 19     e[edge].to = y;
 20     e[edge].next = head[x];
 21     head[x] = edge++;
 22 }
 23 int son[maxn],fa[maxn],siz[maxn],dep[maxn];
 24 void dfs(int root)
 25 {
 26     siz[root] = 1;
 27     son[root] = 0;
 28     for (int i = head[root]; i > 0; i = e[i].next)
 29     {
 30         if (fa[root] != e[i].to)
 31         {
 32             dep[e[i].to] = dep[root] + 1;
 33             fa[e[i].to] = root;
 34             dfs(e[i].to);
 35             if (siz[e[i].to] > siz[son[root]])
 36                 son[root] = e[i].to;
 37             siz[root] += siz[e[i].to];
 38         }
 39     }
 40 }
 41 int tot,top[maxn],li[maxn<<2],pos[maxn];
 42 void build(int root,int father)
 43 {
 44     top[root] = father;
 45     pos[root] = tot;
 46     li[tot++] = root;
 47     if (son[root] > 0)
 48         build(son[root],top[root]);
 49     for (int i = head[root]; i > 0; i = e[i].next)
 50         if (fa[root] != e[i].to && son[root] != e[i].to)
 51             build(e[i].to,e[i].to);
 52 }
 53 
 54 int minv[maxn<<2],maxv[maxn<<2], tt[maxn],lazy[maxn<<2];
 55 void build_Segtree(int l,int r,int o)
 56 {
 57     lazy[o] = 0;
 58     if (l == r)
 59     {
 60         minv[o] = tt[li[l]];
 61         maxv[o] =tt[li[l]];
 62         return;
 63     }
 64     int mid = (l + r) >> 1;
 65     build_Segtree(l,mid,o<<1);
 66     build_Segtree(mid+1,r,o<<1|1);
 67     minv[o] = min(minv[o<<1],minv[o<<1|1]);
 68     maxv[o] = max(maxv[o<<1],maxv[o<<1|1]);
 69 }
 70 char op[10];
 71 int val;
 72 inline void push_down(int l,int r,int o)
 73 {
 74     if (lazy[o]&&l!=r)
 75     {
 76         maxv[o<<1] = -maxv[o<<1];
 77         minv[o<<1] = -minv[o<<1];
 78         maxv[o<<1|1] = -maxv[o<<1|1];
 79         minv[o<<1|1] = -minv[o<<1|1];
 80         swap(maxv[o<<1],minv[o<<1]);
 81         swap(maxv[o<<1|1],minv[o<<1|1]);
 82         lazy[o<<1] ^= 1;
 83         lazy[o<<1|1] ^= 1;
 84         lazy[o] = 0;
 85     }
 86 }
 87 void update(int l,int r,int o,int ua,int ub)
 88 {
 89     if (ua <= l && ub >= r)
 90     {
 91         if (op[0] == 'N')
 92         {
 93             maxv[o] = -maxv[o];
 94             minv[o] = -minv[o];
 95             swap(maxv[o],minv[o]);
 96             lazy[o] ^= 1;
 97         }
 98         if (op[0] == 'C')
 99             minv[o] = maxv[o]  = val,lazy[o] = 0;
100         return;
101     }
102     //if (op[0] == 'N')
103     push_down(l,r,o);
104     int mid = (l + r) >> 1;
105     if (ua <= mid)
106         update(l,mid,o<<1,ua,ub);
107     if (ub > mid)
108         update(mid+1,r,o<<1|1,ua,ub);
109     minv[o] = min(minv[o<<1],minv[o<<1|1]);
110     maxv[o] = max(maxv[o<<1],maxv[o<<1|1]);
111 }
112 
113 int query(int l,int r,int o,int ua,int ub)
114 {
115     if (ua <= l && ub >= r)
116         return maxv[o];
117     int mid = (l + r) >> 1;
118     push_down(l,r,o);
119     int t1 = -inf,t2 = -inf;
120     if (ua <= mid)
121         t1 = query(l,mid,o<<1,ua,ub);
122     if (ub > mid)
123         t2 = query(mid+1,r,o<<1|1,ua,ub);
124     minv[o] = min(minv[o<<1],minv[o<<1|1]);
125     maxv[o] = max(maxv[o<<1],maxv[o<<1|1]);
126     return max(t1,t2);
127 }
128 
129 int get_max(int ua,int ub)
130 {
131     int f1 = top[ua];
132     int f2 = top[ub];
133     int tmp = -inf;
134     while (f1 != f2)
135     {
136         if (dep[f1] < dep[f2])
137             swap(ua,ub),swap(f1,f2);
138         tmp = max(tmp,query(1,tot,1,pos[f1],pos[ua]));
139         ua = fa[f1];
140         f1 = top[ua];
141     }
142     if (ua == ub)
143         return tmp;
144     if (dep[ua]  > dep[ub])
145         swap(ua,ub);
146     return tmp = max(tmp,query(1,tot,1,pos[son[ua]],pos[ub]));
147 }
148 void get_negate(int ua,int ub)
149 {
150     int f1 = top[ua];
151     int f2 = top[ub];
152     while (f1 != f2)
153     {
154         if (dep[f1] < dep[f2])
155             swap(ua,ub),swap(f1,f2);
156         update(1,tot,1,pos[f1],pos[ua]);
157         ua = fa[f1];
158         f1 = top[ua];
159     }
160     if (dep[ua] > dep[ub])
161         swap(ua,ub);
162     if (ua == ub)
163         return;
164     update(1,tot,1,pos[son[ua]],pos[ub]);
165 }
166 
167 int d[maxn][3];
168 void init()
169 {
170     int root,n;
171     scanf ("%d",&n);
172     root = (n + 1) >> 1;
173     edge = tot = 1;
174     memset(siz,0,sizeof(siz));
175     memset(head,0,sizeof(head));
176     fa[root] = dep[root] = 0;
177     for (int i = 1; i )
178     {
179         scanf ("%d%d%d",&d[i][0],&d[i][1],&d[i][2]);
180         add(d[i][1],d[i][0]);
181         add(d[i][0],d[i][1]);
182     }
183     dfs(root);
184     build(root,root);
185     build_Segtree(1,tot,1);
186     op[0] = 'C';
187     for (int i = 1; i )
188     {
189         if (dep[d[i][0]] 1]])
190             swap(d[i][0],d[i][1]);
191         tt[d[i][0]] = val = d[i][2];
192         update(1,tot,1,pos[d[i][0]],pos[d[i][0]]);
193     }
194 }
195 int main(void)
196 {
197     freopen("in.txt","r",stdin);
198     int t;
199     scanf ("%d",&t);
200     while (t--)
201     {
202         init();
203         while (scanf ("%s",op),op[0] != 'D')
204         {
205             int x,y;
206             scanf ("%d%d",&x,&y);
207             if (op[0] == 'Q'&&x!=y)
208                 printf("%d\n",get_max(x,y));
209             if (op[0] == 'Q' && x == y)
210                 printf("0\n");
211             if (op[0] == 'C')
212             {
213                 val = y;
214                 update(1,tot,1,pos[d[x][0]],pos[d[x][0]]);
215             }
216             if (op[0] == 'N'&&x!=y)
217                 get_negate(x,y);
218         }
219     }
220     return 0;
221 }
222 
223 
224 /*
225 1
226 11
227 2 1 1
228 2 4 2
229 2 3 3
230 1 5 4
231 3 6 5
232 3 7 6
233 7 8 7
234 4 9 8
235 9 10 9
236 10 11 10
237 N 2 10
238 Query 4 10
239 DONE
240 
241 */