Cogs 1672. [SPOJ375 QTREE]难存的情缘 LCT,树链剖分,填坑计划

problem.php?pid=1672

1672. [SPOJ375 QTREE]难存的情缘

★★★☆ 输入文件：qtree.in 输出文件：qtree.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

一天机房的夜晚，无数人在MC里奋斗着。。。

大家都知道矿产对于MC来说是多么的重要，但由于矿越挖越少，勇士们不得不跑到更远的地方挖矿，但这样路途上就会花费相当大的时间，导致挖矿效率低下。

cjj提议修一条铁路，大家一致同意。

大家都被CH分配了一些任务：

zjmfrank2012负责绘制出一个矿道地图，这个地图包括家（当然这也是一个矿，毕竟不把家掏空我们是不会走的），和无数个矿，所以大家应该可以想出这是一个无向无环图，也就是一棵树。

Digital_T和cstdio负责铺铁路。。所以这里没他们什么事，两位可以劳作去了。

这个时候song526210932和RMB突然发现有的矿道会刷怪，并且怪的数量会发生变化。作为采矿主力，他们想知道从一个矿到另一个矿的路上哪一段会最困难。。。（困难值用zjm的死亡次数表示）。

【输入格式】

输入文件的第一行有一个整数N，代表矿的数量。矿的编号是1到N。

接下来N-1行每行有三个整数a,b,c，代表第i号矿和第j号矿之间有一条路，在初始时这条路的困难值为c。

接下来有若干行，每行是“CHANGE i ti”或者“QUERY a b”，前者代表把第i条路（路按所给顺序从1到M编号）的困难值修改为ti，后者代表查询a到b所经过的道路中的最大困难值。

输入数据以一行“DONE”结束。

【输出格式】

对每个“QUERY”操作，输出一行一个正整数，即最大困难值。

【样例输入】

1 2 1

2 3 2

QUERY 1 2

CHANGE 1 3

QUERY 1 2

DONE

【样例输出】

【提示】

对于60%的数据，1<=N<=50

对于100%的数据，1<=N<=10000，1<=c<=1000000,1<=操作次数<=100000

【来源】

由GDFRWMY 改编自SPOJ 375 QTREE

数据by cstdio

题解：

直接LCT维护最大值即可。。。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define MAXN 10010
  4 struct node
  5 {
  6     int left,right,val;
  7 }tree[2*MAXN];
  8 int father[2*MAXN],rev[2*MAXN],mx[2*MAXN],Stack[2*MAXN];
  9 int read()
 10 {
 11     int s=0,fh=1;char ch=getchar();
 12     while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
 13     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
 14     return s*fh;
 15 }
 16 int isroot(int x)
 17 {
 18     return tree[father[x]].left!=x&&tree[father[x]].right!=x;
 19 }
 20 void pushdown(int x)
 21 {
 22     int l=tree[x].left,r=tree[x].right;
 23     if(rev[x]!=0)
 24     {
 25         rev[x]^=1;rev[l]^=1;rev[r]^=1;
 26         swap(tree[x].left,tree[x].right);
 27     }
 28 }
 29 void pushup(int x)
 30 {
 31     int l=tree[x].left,r=tree[x].right;
 32     mx[x]=x;
 33     if(tree[mx[l]].val>tree[mx[x]].val)mx[x]=mx[l];
 34     if(tree[mx[r]].val>tree[mx[x]].val)mx[x]=mx[r];
 35 }
 36 void rotate(int x)
 37 {
 38     int y=father[x],z=father[y];
 39     if(!isroot(y))
 40     {
 41         if(tree[z].left==y)tree[z].left=x;
 42         else tree[z].right=x;
 43     }
 44     if(tree[y].left==x)
 45     {
 46         father[x]=z;father[y]=x;tree[y].left=tree[x].right;tree[x].right=y;father[tree[y].left]=y;
 47     }
 48     else
 49     {
 50         father[x]=z;father[y]=x;tree[y].right=tree[x].left;tree[x].left=y;father[tree[y].right]=y;
 51     }
 52     pushup(y);pushup(x);
 53 }
 54 void splay(int x)
 55 {
 56     int top=0,i,y,z;Stack[++top]=x;
 57     for(i=x;!isroot(i);i=father[i])Stack[++top]=father[i];
 58     for(i=top;i>=1;i--)pushdown(Stack[i]);
 59     while(!isroot(x))
 60     {
 61         y=father[x];z=father[y];
 62         if(!isroot(y))
 63         {
 64             if((tree[y].left==x)^(tree[z].left==y))rotate(x);
 65             else rotate(y);
 66         }
 67         rotate(x);
 68     }
 69 }
 70 void access(int x)
 71 {
 72     int last=0;
 73     while(x!=0)
 74     {
 75         splay(x);
 76         tree[x].right=last;pushup(x);
 77         last=x;x=father[x];
 78     }
 79 }
 80 void makeroot(int x)
 81 {
 82     access(x);splay(x);rev[x]^=1;
 83 }
 84 void link(int u,int v)
 85 {
 86     makeroot(u);father[u]=v;splay(u);
 87 }
 88 void cut(int u,int v)
 89 {
 90     makeroot(u);access(v);splay(v);father[u]=tree[v].left=0;
 91 }
 92 int findroot(int x)
 93 {
 94     access(x);splay(x);
 95     while(tree[x].left!=0)x=tree[x].left;
 96     return x;
 97 }
 98 int main()
 99 {
100     freopen("qtree.in","r",stdin);
101     freopen("qtree.out","w",stdout);
102     int n,i,bb,ee,vv,a,b;
103     char fh[8];
104     n=read();
105     memset(mx,0,sizeof(mx));//瀛樻渶澶у€肩殑缂栧彿.
106     for(i=1;i<=n;i++)mx[i]=i;
107     for(i=1;i<n;i++)
108     {
109         bb=read();ee=read();vv=read();
110         tree[n+i].val=vv;
111         link(bb,n+i);link(ee,n+i);
112     }
113     while(1)
114     {
115         scanf("
%s",fh);
116         if(fh[0]=='D')break;
117         if(fh[0]=='Q')
118         {
119             a=read();b=read();
120             makeroot(a);access(b);splay(b);
121             printf("%d
",tree[mx[b]].val);
122         }
123         else
124         {
125             a=read();b=read();
126             makeroot(n+a);tree[n+a].val=b;
127         }
128     }
129     fclose(stdin);
130     fclose(stdout);
131     return 0;
132 }

View Code

树链剖分。。。此坑未填。。。