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
Input:
8 5
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 
一日にこのような問題だけをして、やっと6666ができました.
タイトル:ワーワーという簡単な読みやすい問題です.木の上の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; }
今夜は夢を見ないで試合を見てください.