bzoj 3551[ONTAK 2010]Peaks強化版(kruskal,議長樹,dfs序)
20494 ワード
Description
【タイトル説明】同3545
Input
第1行の3つの数N,M,Q.
2行目N個目、i個目h_i
次にM行、各行3個の数a b cは、aからbまでの困難値cの双方向経路を示す.
次に、Q行は、行ごとに3つの数v x kであり、問い合わせのセットを表す.v=v xor lastans,x=x xor lastans,k=k xor lastans.lastans=-1の場合は変わりません.
Output
同3545
【考え方】
Kruskal+議長ツリー+dfsシーケンス
kruskal再構成ツリーという方法QWQ.kruskalがサブツリーをマージするときにextノードを新規作成し、2本のサブツリーの共通のルートにし、エッジ権を重み値にします.
新しくできた木の性質:
質問に対して,vのポイント重み値がxを超えない最小の祖先を見つけ,その祖先をルートとするサブツリー内のすべての点とvが条件を満たし,次いで,dfsシーケンスに基づいて議長ツリーを構築して処理できるk番目の大きな問題を見つけた.
【コード】
1 #include<cstdlib>
2 #include<queue>
3 #include<vector>
4 #include<cstdio>
5 #include<cstring>
6 #include<iostream>
7 #include<algorithm>
8 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)
9 using namespace std;
10
11 typedef long long ll;
12 const int N = 200005;
13 const int M = 5100005;
14 const int D = 17;
15
16 struct Edge {
17 int u,v,w;
18 bool operator < (const Edge& rhs) const {
19 return w<rhs.w;
20 }
21 };
22 struct LEdge { int v,nxt;
23 };
24 struct Tnode{
25 int lc,rc,sum;
26 }T[M];
27
28 ll read() {
29 char c=getchar();
30 ll f=1,x=0;
31 while(!isdigit(c)) {
32 if(c=='-') f=-1; c=getchar();
33 }
34 while(isdigit(c))
35 x=x*10+c-'0',c=getchar();
36 return x*f;
37 }
38
39 int n,m,q,sz,tot,dfsc;
40 int hash[N],h[N],rt[N],val[N],bin[N];
41 int p[N],dep[N],fa[N][D],mx[N][D],L[N],R[N];
42
43 Edge es[N<<1]; LEdge e[N<<1];
44 int en=-1,front[N];
45 void adde(int u,int v)
46 {
47 en++; e[en].v=v; e[en].nxt=front[u]; front[u]=en;
48 }
49 int ifind(int u)
50 {
51 return u==p[u]? u: p[u]=ifind(p[u]);
52 }
53 void update(int l,int r,int x,int& y,int num)
54 {
55 T[y=++sz]=T[x];
56 T[y].sum++;
57 if(l>=r) return ;
58 int mid=(l+r)>>1;
59 if(num<=mid) update(l,mid,T[x].lc,T[y].lc,num);
60 else update(mid+1,r,T[x].rc,T[y].rc,num);
61 }
62 int query(int l,int r,int a,int b,int rk)
63 {
64 int mid=(l+r)>>1;
65 if(l>=r) return mid;
66 int now=T[T[b].rc].sum-T[T[a].rc].sum;
67 if(rk<=now) return query(mid+1,r,T[a].rc,T[b].rc,rk);
68 else return query(l,mid,T[a].lc,T[b].lc,rk-now);
69 }
70 void dfs(int u)
71 {
72 L[u]=++dfsc;
73 update(0,tot,rt[L[u]-1],rt[L[u]],h[u]);
74 FOR(i,1,D-1) {
75 fa[u][i]=fa[fa[u][i-1]][i-1];
76 mx[u][i]=max(mx[u][i-1],mx[fa[u][i-1]][i-1]);
77 }
78 for(int i=front[u];i>=0;i=e[i].nxt) {
79 int v=e[i].v;
80 dep[v]=dep[u]+1,
81 dfs(v);
82 }
83 R[u]=dfsc;
84 }
85 int find_root(int u,int x)
86 {
87 for(int i=D-1;i>=0;i--)
88 if(fa[u][i] && mx[u][i]<=x)
89 u=fa[u][i];
90 return u;
91 }
92
93 int main()
94 {
95 //reopen("in.in","r",stdin);
96 //freopen("out.out","w",stdout);
97
98 memset(front,-1,sizeof(front));
99 n=read(),m=read(),q=read();
100 FOR(i,1,n) h[i]=read(),hash[i]=h[i];
101 int u,v,w,x,k,ans=0;
102 FOR(i,1,m) {
103 u=read(),v=read(),w=read();
104 es[i]=(Edge){u,v,w};
105 }
106
107 FOR(i,1,2*n) p[i]=i;
108 sort(hash+1,hash+n+1);
109 tot=unique(hash+1,hash+n+1)-hash-1;
110 FOR(i,1,n)
111 h[i]=lower_bound(hash+1,hash+tot+1,h[i])-hash;
112
113 sort(es+1,es+m+1);
114 FOR(i,1,m) {
115 Edge e=es[i];
116 int x=ifind(e.u),y=ifind(e.v);
117 if(x!=y) {
118 int ext=++n;
119 fa[x][0]=fa[y][0]=ext;
120 mx[x][0]=mx[y][0]=e.w;
121 p[x]=p[y]=ext;
122 adde(ext,x),adde(ext,y);
123 }
124 }
125
126 dfs(n);
127
128 FOR(i,1,q) {
129 v=read(),x=read(),k=read();
130 v^=ans,x^=ans,k^=ans;
131 int root=find_root(v,x);
132 if(R[root]-L[root]+1<k) puts("-1"),ans=0;
133 else {
134 ans=query(0,tot,rt[L[root]-1],rt[R[root]],k);
135 if(!ans) puts("-1");
136 else printf("%d
",ans=hash[ans]);
137 }
138 }
139 return 0;
140 }