F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 2588 >> RE到要哭QAQ
Mychael @ 2017-12-02 21:46:17
[ Quote ] [ Edit ] [ Delete ] 1#
求dalao帮忙QAQ【79行主席树】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 100005,maxm = 5000005,INF = 1000000000;
inline LL RD(){
LL out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}
return out * flag;
}
int N,M,A[maxn],id[maxn],V[maxn],H[maxn],dep[maxn],fa[maxn][20],n = 0;
int siz = 0,rt[maxn],pos;
int head[maxn],nedge = 0;
struct EDGE{int to,next;}edge[2 * maxn];
struct node{LL sum;int ls,rs;}e[maxm];
inline void add(int u,int v){
edge[nedge] = (EDGE){v,head[u]}; head[u] = nedge++;
edge[nedge] = (EDGE){u,head[v]}; head[v] = nedge++;
}
inline bool cmp(const int& a,const int& b){return A[a] < A[b];}
void build(int& u,int pre,int l,int r){
u = ++siz; e[u] = e[pre]; e[u].sum++;
if (l == r) return;
int mid = l + r >> 1;
if (mid >= pos) build(e[u].ls,e[pre].ls,l,mid);
else build(e[u].rs,e[pre].rs,mid + 1,r);
}
int Query(int r1,int r2,int r3,int r4,int l,int r,int k){
if (l == r) return l;
int mid = l + r >> 1,temp = e[e[r1].ls].sum + e[e[r2].ls].sum - e[e[r3].ls].sum - e[e[r4].ls].sum;
if (temp >= k) return Query(e[r1].ls,e[r2].ls,e[r3].ls,e[r4].ls,l,mid,k);
else return Query(e[r1].rs,e[r2].rs,e[r3].rs,e[r4].rs,mid + 1,r,k - temp);
}
inline int Lca(int u,int v){
if (dep[u] < dep[v]) swap(u,v);
int d = dep[u] - dep[v];
for (int i = 0; (1 << i) <= d; i++)
if ((1 << i) & d) u = fa[u][i];
if (u == v) return u;
for (int i = (int)log(N); i >= 0; i--)
if (fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i];
return fa[u][0];
}
void dfs(int u,int f,int d){
fa[u][0] = f; pos = V[u]; dep[u] = ++d;
build(rt[u],rt[f],1,n);
Redge(u) if (edge[k].to != f) dfs(edge[k].to,u,d);
}
void init2(){REP(i,19) REP(u,N) fa[u][i] = fa[fa[u][i - 1]][i - 1];}
void init(){
memset(head,-1,sizeof(head));
N = RD(); M = RD();
REP(i,N) A[i] = RD(),id[i] = i;
REP(i,N - 1) add(RD(),RD());
sort(id + 1,id + 1 + N,cmp);
V[id[1]] = ++n; H[n] = A[id[1]];
for (int i = 2; i <= N; i++) V[id[i]] = A[id[i]] == A[id[i - 1]] ? n : ++n,H[n] = A[id[i]];
}
void solve(){
int u,v,k,lca,last = 0;
while (M--){
u = last ^ RD(); v = RD(); k = RD(); lca = Lca(u,v);
printf("%d",last = H[Query(rt[u],rt[v],rt[lca],rt[fa[lca][0]],1,n,k)]);
if (M) printf("\n");
}
}
int main(){
init();
dfs(1,0,0);
init2();
solve();
return 0;
}
stl @ 2017-12-03 02:46:37
[ Quote ] [ Edit ] [ Delete ] 2#
对拍死调啊你贴个代码一般没人会帮你看的
[Top] [Previous Page] [Next Page]

HOME Back