spoj Count on a tree【主席樹＋オンラインLCA】
10628.Count on a tree Problem code:COT
You are given a tree with N nodes.The tree nodes are numberred from 1 ト N.Each node has n integer weight.
We will ask you to perform the follwing operation:
u v k : ask for the kth minimum weight on the path from node u. トノイド v
Input
In the first line there re re two integers N and M.(N,M<=100000)
In the second line there are N integers.The ith integer denotes the weight of the ith node.
In the next N-1 ライン、each line contains two integers u. v,which describes an edge(u,v)
In the next M ライン、each line contains three integers u. v k,which means an operation asking for the kth minimum weight on the path from node u. トノイド v.
Output
For each operation,print its result.
Example
タイトル:ワーワーという簡単な読みやすい問題です.木の上の2つの間のすべての数は最小値を探しています.考え方もワーワーというのは簡単です.木の上に主席の木を作るということですか?初めて木をセットしたのです.コード量に驚きました.私は2つのWhileを180行に返します.午前中は基本的に分かりました.はい、コードを自分の前に使っていたテンプレートに押して、もう一度つなぎ合わせてみます.今は本当に主席の木の関数とオンラインLCAのアルゴリズムが分かりました.言ってもいいですか?混ぜては返します.先日RMQを使った時にLCAの遺留問題を忘れました.今回の問題はオフラインを使うべきではないです.このブログを参考にしました.リンクをクリックして、コードを分かりました.自分で書いたのも彼のテンプレートです.本当に簡単です.
ところで、主席の木は区間のk番目の小さい値を求めています.この問題の中に入れて、query関数を変えなければならない以外に、直接にそのまま運んで、使うのは孫大神のテンプレートです.構造体は左右の結点の書き方がはっきりしています.坑もquery関数の中にあります.実は最初からここの問題ではないかと疑っていました.すべての印刷できる配列を開けてみます.もう大丈夫です.queryをよく見ました.公共の祖先のRtは毎回再帰するべきではないです.話が通じません.
LCAは大丈夫です.でも、木を建てる関数は心を使わなければなりません.これから、つまりこの二週間です.一生懸命木をこすります.同じことだと思いますが、全然書けません.
You are given a tree with N nodes.The tree nodes are numberred from 1 ト N.Each node has n integer weight.
We will ask you to perform the follwing operation:
u v k : ask for the kth minimum weight on the path from node u. トノイド v
Input
In the first line there re re two integers N and M.(N,M<=100000)
In the second line there are N integers.The ith integer denotes the weight of the ith node.
In the next N-1 ライン、each line contains two integers u. v,which describes an edge(u,v)
In the next M ライン、each line contains three integers u. v k,which means an operation asking for the kth minimum weight on the path from node u. トノイド v.
Output
For each operation,print its result.
Example
Input:8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2 Output:
2
8
9
105
7 タイトル:ワーワーという簡単な読みやすい問題です.木の上の2つの間のすべての数は最小値を探しています.考え方もワーワーというのは簡単です.木の上に主席の木を作るということですか?初めて木をセットしたのです.コード量に驚きました.私は2つのWhileを180行に返します.午前中は基本的に分かりました.はい、コードを自分の前に使っていたテンプレートに押して、もう一度つなぎ合わせてみます.今は本当に主席の木の関数とオンラインLCAのアルゴリズムが分かりました.言ってもいいですか?混ぜては返します.先日RMQを使った時にLCAの遺留問題を忘れました.今回の問題はオフラインを使うべきではないです.このブログを参考にしました.リンクをクリックして、コードを分かりました.自分で書いたのも彼のテンプレートです.本当に簡単です.
ところで、主席の木は区間のk番目の小さい値を求めています.この問題の中に入れて、query関数を変えなければならない以外に、直接にそのまま運んで、使うのは孫大神のテンプレートです.構造体は左右の結点の書き方がはっきりしています.坑もquery関数の中にあります.実は最初からここの問題ではないかと疑っていました.すべての印刷できる配列を開けてみます.もう大丈夫です.queryをよく見ました.公共の祖先のRtは毎回再帰するべきではないです.話が通じません.
LCAは大丈夫です.でも、木を建てる関数は心を使わなければなりません.これから、つまりこの二週間です.一生懸命木をこすります.同じことだと思いますが、全然書けません.
/*********
spoj Count on a tree
2016.1.25
152576 2330ms
C++ (g++ 4.9.2)
*********/
#include
#include
#include
#include
#include
using namespace std;
#define maxn 200020
///=============
struct Node
{
int ls,rs,cnt;
}tr[maxn*40];
int cur,m,n,q,rt[maxn],b[maxn],sortb[maxn];
void tree_init()
{
cur=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
sortb[i]=b[i];
}
sort(sortb+1,sortb+1+n);
m=1;
for(int i=2;i<=n;i++)
{
if(sortb[i]!=sortb[m]) sortb[++m]=sortb[i];
}
}
int build(int l,int r)
{
int k=cur++;
if(l==r)
{
tr[k].cnt=0;
return k;
}
int mid=(l+r)>>1;
tr[k].ls=build(l,mid);
tr[k].rs=build(mid+1,r);
tr[k].cnt=0;
return k;
}
int update(int o,int l,int r,int pos,int val)
{
int k=cur++;
tr[k]=tr[o];
if(l==pos&&r==pos)
{
tr[k].cnt+=val;
return k;
}
int mid=(l+r)>>1;
if(pos<=mid) tr[k].ls=update(tr[o].ls,l,mid,pos,val);
else tr[k].rs=update(tr[o].rs,mid+1,r,pos,val);
tr[k].cnt=tr[tr[k].ls].cnt+tr[tr[k].rs].cnt;
return k;
}
///==============
///============== LCA
int dp[maxn*2][25],num;
bool vis[maxn];
struct Edge
{
int u,v,next;/// ， ！
}e[maxn<<1];
int tot,head[maxn];
void lca_init()
{
tot=0;
num=0;
memset(head,-1,sizeof(head));
memset(vis,false,sizeof(vis));
}
inline void add(int u,int v,int &k)
{
e[k].u=u;e[k].v=v;e[k].next=head[u];head[u]=k++;
e[k].u=v;e[k].v=u;e[k].next=head[v];head[v]=k++;
}
int ver[maxn*2],R[maxn*2],first[maxn];/// 、 、( )
// ， =2*n-1, ！
void dfs(int u,int pre,int dep)// vis ， pre
{
ver[++tot]=u;
first[u]=tot;
R[tot]=dep;
for(int k=head[u];k!=-1;k=e[k].next)
{
int v=e[k].v;
if(v==pre) continue;
/// dir[v]=dir[u]+w; ， = dir[]
dfs(v,u,dep+1);
ver[++tot]=u;
R[tot]=dep;
}
}
void ST(int n)
{
for(int i=1;i<=n;i++) dp[i][0]=i;
for(int j=1;(1< n) continue;
int a=dp[i][j-1],b=dp[i+(1<y) swap(x,y);
int res=RMQ(x,y);
return ver[res];
}
///=============LCA
///============= ： +
void dfs_build(int u,int pre)
{
int pos=lower_bound(sortb+1,sortb+1+m,b[u])-sortb;
rt[u]=update(rt[pre],1,m,pos,1);
for(int k=head[u];k!=-1;k=e[k].next)
{
int v=e[k].v;
if(v==pre) continue;
dfs_build(v,u);
}
}
int query(int l,int r,int o,int v,int Lca,int k)
{
/* if(l==r) return l;
int mid=(l+r)>>1;
int
int lca=rt[Lca];
if(k<=tmp) return query(l,mid,tr[o].ls,tr[v].ls,tr[lca].ls,k);
else return query(mid+1,r,tr[o].rs,tr[v].rs,tr[lca].rs,k-tmp);*/
int lca_root=rt[Lca];
int pos=lower_bound(sortb+1,sortb+1+m,b[Lca])-sortb;
while(l>1;
int tmp=tr[tr[v].ls].cnt+tr[tr[o].ls].cnt-2*tr[tr[lca_root].ls].cnt+(pos>=l&&pos<=mid);
if(tmp>=k)
{
o=tr[o].ls;v=tr[v].ls;lca_root=tr[lca_root].ls;
r=mid;
}
else
{
k-=tmp;
o=tr[o].rs;v=tr[v].rs;lca_root=tr[lca_root].rs;
l=mid+1;
}
}
return l;
}
///============
int main()
{
//freopen("cin.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(scanf("%d%d",&n,&q)==2)
{
tree_init();
lca_init();
for(int i=1;i n) continue;
printf("i=%d,j=%d,dp=%d
",i,j,dp[i][j]);
}
/* puts("7,4");
printf("%d
",sortb[query(1,m,rt[7],rt[4],LCA(7,4),1)]);
printf("%d
",sortb[query(1,m,rt[7],rt[4],LCA(7,4),2)]);
printf("%d
",sortb[query(1,m,rt[7],rt[4],LCA(7,4),3)]);
printf("%d
",sortb[query(1,m,rt[7],rt[4],LCA(7,4),4)]);
puts("5,8");
printf("%d
",sortb[query(1,m,rt[5],rt[8],LCA(5,8),1)]);
printf("%d
",sortb[query(1,m,rt[5],rt[8],LCA(5,8),2)]);
printf("%d
",sortb[query(1,m,rt[5],rt[8],LCA(5,8),3)]);
printf("%d
",sortb[query(1,m,rt[5],rt[8],LCA(5,8),4)]);
printf("%d
",sortb[query(1,m,rt[5],rt[8],LCA(5,8),5)]);
printf("%d
",sortb[query(1,m,rt[5],rt[8],LCA(5,8),6)]);
puts("");
printf("%d
",sortb[query(1,m,rt[6],rt[8],LCA(6,8),1)]);
printf("%d
",sortb[query(1,m,rt[6],rt[8],LCA(6,8),2)]);
printf("%d
",sortb[query(1,m,rt[6],rt[8],LCA(6,8),3)]);
printf("%d
",sortb[query(1,m,rt[6],rt[8],LCA(6,8),4)]);
printf("%d
",sortb[query(1,m,rt[6],rt[8],LCA(6,8),5)]);
printf("%d
",sortb[query(1,m,rt[6],rt[8],LCA(6,8),6)]);
puts("");
puts("2,8");
printf("%d
",sortb[query(1,m,rt[2],rt[8],LCA(2,8),1)]);
printf("%d
",sortb[query(1,m,rt[2],rt[8],LCA(2,8),2)]);
printf("%d
",sortb[query(1,m,rt[2],rt[8],LCA(2,8),3)]);
printf("%d
",sortb[query(1,m,rt[2],rt[8],LCA(2,8),4)]);
puts("1,8");
printf("%d
",sortb[query(1,m,rt[1],rt[8],LCA(1,8),1)]);
printf("%d
",sortb[query(1,m,rt[1],rt[8],LCA(1,8),2)]);
printf("%d
",sortb[query(1,m,rt[1],rt[8],LCA(1,8),3)]);
puts("");*/
}
return 0;
}