一個地方wa了3發(fā)，找了一組數(shù)組發(fā)現(xiàn)的錯誤，太蠢，就是兩個人數(shù)作交換寫成了 a=b ,b=a。最近智商真是感人。這道題是由spoj375這題改編的，多了一個取反的操作，這個操作只需要多維護一個最小值就行了。然后就是簡單的樹鏈剖分+線段樹的區(qū)間操作。沒什么好說的，直接上代碼（過幾天把LCT學習了，可能回頭再來補這題）。

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <map> #define LL long long #define FOR(i,x,y) for(int i = x;i < y;i ++) #define IFOR(i,x,y) for(int i = x;i > y;i --) #define lrt rt<<1 #define rrt rt<<1|1 #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define INF 0x3fffffff #define MAXN 110000using namespace std;int n;int val0[MAXN],val[MAXN];int edge_cnt,head[MAXN];struct Edge{int u,v,idd;int nt; }edge[MAXN<<1];void add_edge(int u,int v,int idd){edge[edge_cnt].u = u;edge[edge_cnt].v = v;edge[edge_cnt].idd = idd;edge[edge_cnt].nt = head[u];head[u] = edge_cnt ++; }int top[MAXN],sz[MAXN],fa[MAXN],w[MAXN],son[MAXN],dep[MAXN],id[MAXN]; int totw; map <int,int> mat;void dfs1(int u,int father,int depth){sz[u] = 1; fa[u] = father; dep[u] = depth;int idd = -1,maxx = -1;for(int i = head[u];i != -1;i = edge[i].nt){int v = edge[i].v;if(v == father) continue;id[v] = edge[i].idd;dfs1(v,u,depth+1);sz[u] += sz[v];if(sz[v] > maxx){maxx = sz[v]; idd = v;}}son[u] = idd; }void dfs2(int u,int father){if(son[u] == -1) return;top[son[u]] = top[u];w[son[u]] = ++totw;val[totw] = val0[id[son[u]]];mat[id[son[u]]] = totw;dfs2(son[u],u);for(int i = head[u];i != -1;i = edge[i].nt){int v = edge[i].v;if(v == father) continue;if(v == son[u]) continue;top[v] = v;w[v] = ++totw;val[totw] = val0[id[v]];mat[id[v]] = totw;dfs2(v,u);} }struct Tree{int l,r;int maxx,minx;int lazy; }tree[MAXN<<2];void UpDate_Flip(int rt){tree[rt].lazy ^= 1;int tem = tree[rt].maxx;tree[rt].maxx = -tree[rt].minx;tree[rt].minx = -tem; }void PushDown(int rt){if(tree[rt].lazy){UpDate_Flip(lrt);UpDate_Flip(rrt);tree[rt].lazy = 0;} }void PushUp(int rt){tree[rt].minx = min(tree[lrt].minx,tree[rrt].minx);tree[rt].maxx = max(tree[lrt].maxx,tree[rrt].maxx); }void Build(int rt,int l,int r){tree[rt].l = l; tree[rt].r = r;tree[rt].lazy = 0;if(l == r){tree[rt].maxx = tree[rt].minx = val[l];return;}int mid = (l+r)>>1;Build(lson);Build(rson);PushUp(rt); }void Modify(int rt,int x,int value){if(tree[rt].l == tree[rt].r){tree[rt].maxx = tree[rt].minx = value;return;}PushDown(rt);int mid = (tree[rt].l + tree[rt].r)>>1;if(x <= mid) Modify(lrt,x,value);else Modify(rrt,x,value);PushUp(rt); }void Negate(int rt,int l,int r){if(tree[rt].l == l && tree[rt].r == r){UpDate_Flip(rt);return;}PushDown(rt);int mid = (tree[rt].l + tree[rt].r)>>1;if(r <= mid) Negate(lrt,l,r);else if(l > mid) Negate(rrt,l,r);else{Negate(lson);Negate(rson);}PushUp(rt); }int Query(int rt,int l,int r){if(tree[rt].l == l && tree[rt].r == r){return tree[rt].maxx;}PushDown(rt);int mid = (tree[rt].l + tree[rt].r)>>1;if(r <= mid) return Query(lrt,l,r);else if(l > mid) return Query(rrt,l,r);else{return max(Query(lson),Query(rson));} }void C_Negate(int l,int r){while(top[l] != top[r]){if(dep[top[l]] >= dep[top[r]]){Negate(1,w[top[l]],w[l]);l = fa[top[l]];}else{Negate(1,w[top[r]],w[r]);r = fa[top[r]];}}if(l == r) return;if(dep[l] >= dep[r]){Negate(1,w[r]+1,w[l]);}else Negate(1,w[l]+1,w[r]); }int C_Query(int l,int r){int ans = -INF;while(top[l] != top[r]){if(dep[top[l]] >= dep[top[r]]){ans = max(ans,Query(1,w[top[l]],w[l]));l = fa[top[l]];}else{ans = max(ans,Query(1,w[top[r]],w[r]));r = fa[top[r]];}}if(l == r) return ans;if(dep[l] >= dep[r]){return max(ans,Query(1,w[r]+1,w[l]));}elsereturn max(ans,Query(1,w[l]+1,w[r])); }int main() {//freopen("test.in","r",stdin);int T;scanf("%d",&T);while(T--){scanf("%d",&n);edge_cnt = 0;memset(head,-1,sizeof(head));int u,v,value;FOR(i,1,n){scanf("%d%d%d",&u,&v,&value);val0[i] = value;add_edge(u,v,i);add_edge(v,u,i);}dfs1(1,-1,1);totw = 0;top[1] = 1;dfs2(1,-1);Build(1,1,totw);char op[10];while(~scanf("%s",op) && strcmp(op,"DONE")){if(!strcmp(op,"QUERY")){int l,r;scanf("%d%d",&l,&r);printf("%d\n",C_Query(l,r));}else if(!strcmp(op,"CHANGE")){int x,value;scanf("%d%d",&x,&value);Modify(1,mat[x],value);}else{int l,r;scanf("%d%d",&l,&r);C_Negate(l,r);}}}return 0; }

版權聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉載。

轉載于:https://www.cnblogs.com/hqwhqwhq/p/4811884.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的POJ 3237 树链剖分学习(树链剖分小结)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。