[整体二分]网络管理

网络管理

Time Limit: 50 Sec Memory Limit: 162 MB

Description

M公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。
　　为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。
　　该网络的结构由N个路由器和N-1条高速光缆组成。
　　每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部门进行通信联络。
　　该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信。
　　高速光缆的数据传输速度非常快，以至于利用光缆传输的延迟时间可以忽略。
　　但是由于路由器老化，在这些路由器上进行数据交换会带来很大的延迟。
　　而两个路由器之间的通信延迟时间则与这两个路由器通信路径上所有路由器中最大的交换延迟时间有关。
　　作为M公司网络部门的一名实习员工，现在要求你编写一个简单的程序来监视公司的网络状况。
　　该程序能够随时更新网络状况的变化信息（路由器数据交换延迟时间的变化），并且根据询问给出两个路由器通信路径上延迟第k大的路由器的延迟时间。
　　你的程序从输入文件中读入N个路由器和N-1条光缆的连接信息，每个路由器初始的数据交换延迟时间Ti，以及Q条询问（或状态改变）的信息。
　　并依次处理这Q条询问信息，它们可能是：
　　　　1. 由于更新了设备，或者设备出现新的故障，使得某个路由器的数据交换延迟时间发生了变化；
　　　　2. 查询某两个路由器a和b之间的路径上延迟第k大的路由器的延迟时间。

Input

第一行为两个整数N和Q，分别表示路由器总数和询问的总数。
　　第二行有N个整数，第i个数表示编号为i的路由器初始的数据延迟时间Ti。
　　紧接着N-1行，每行包含两个整数x和y，表示有一条光缆连接路由器x和路由器y。
　　紧接着是Q行，每行三个整数k、a、b。
　　如果k=0，则表示路由器a的状态发生了变化，它的数据交换延迟时间由Ta变为b。
　　如果k>0，则表示询问a到b的路径上所经过的所有路由器（包括a和b）中延迟第k大的路由器的延迟时间。

Output

对于每一个第二种询问（k>0），输出一行。
　　包含一个整数为相应的延迟时间。
　　如果路径上的路由器不足k个，则输出信息“invalid request!”。

Sample Input

5 5
　5 1 2 3 4
　3 1
　2 1
　4 3
　5 3
　2 4 5
　0 1 2
　2 2 3
　2 1 4
　3 3 5

Sample Output

3
　2
　2
　invalid request!

HINT

N,Q<=80000，任意一个路由器在任何时刻都满足延迟时间小于10^8。
　　对于所有询问满足0<=K<=N。

Main idea

求树上两点路径间第k大的树，需要支持单点修改权值。

Solution

我们一看到这道题，序列的话其实就是BZOJ1901改成求第k大。

我们基于这个思路，从整体二分考虑，然后我们运用树链剖分和线段树。

对于一个点，如果价值>=M的话就把这个点的位置+1权值，然后线段树区间求和就可以找出这个询问 在当前执行的L,M中 有几个>=M的数，由于是树结构，所以这个应该运用树链剖分来在线段树上加。

之后跟静态查询Kth一样判断一下贡献，整体二分继续往下分治即可。

这题思路简单，实现稍微有一点细节需要注意，算是一道经典的数据结构题。(≧▽≦)/

Code

#include<bits/stdc++.h>
using namespace std;

const int ONE=160005;
const int INF=1e8+1;

int n,m;
int x,y,k;
int a[ONE];
int next[ONE*2],first[ONE],go[ONE*2],tot;
int Num,res,cnt;
int record[ONE];
int Ans[ONE];

struct power
{
    int cnt,opt,cur;
    int pos,value;
    int l,r,k;
}oper[ONE*10],qL[ONE*10],qR[ONE*10];

struct point
{
    int f,son,size,dep;
    int top,seg;
}S[ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

void Add(int u,int v)
{
    next[++tot]=first[u];   first[u]=tot;   go[tot]=v;
    next[++tot]=first[v];   first[v]=tot;   go[tot]=u;
}

namespace Sgt
{
    struct power
    {
        int value;
    }Node[ONE*4];

    void Update(int i,int l,int r,int L,int x)
    {
        if(l==r)
        {
            Node[i].value+=x;
            return;
        }

        int mid=(l+r)>>1;
        if(L<=mid) Update(i<<1,l,mid,L,x);
        else Update(i<<1|1,mid+1,r,L,x);
        Node[i].value=Node[i<<1].value + Node[i<<1|1].value;
    }

    void Query(int i,int l,int r,int L,int R)
    {
        if(L<=l && r<=R)
        {
            res+=Node[i].value;
            return;
        }

        int mid=(l+r)/2;
        if(L<=mid) Query(i<<1,l,mid,L,R);
        if(mid+1<=R) Query(i<<1|1,mid+1,r,L,R);
    }
}

namespace Hld
{
    void First()
    {
        S[1].top=S[0].seg=S[1].seg=1;
    }

    void Dfs1(int u,int father)
    {
        S[u].dep=S[father].dep+1;
        S[u].f=father;
        S[u].size=1;
        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(v==father) continue;
            Dfs1(v,u);
            S[u].size+=S[v].size;
            if(S[v].size > S[S[u].son].size) S[u].son=v;
        }
    }

    void Dfs2(int u,int father)
    {
        if(S[u].son)
        {
            int v=S[u].son;
            S[v].top=S[u].top;
            S[v].seg=++S[0].seg;
            Dfs2(v,u);
        }
        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(v==father || S[u].son==v) continue;
            S[v].top=v;
            S[v].seg=++S[0].seg;
            Dfs2(v,u);
        }
    }

    void Solve(int x,int y)
    {
        int Tx=S[x].top,Ty=S[y].top;
        while(Tx!=Ty)
        {
            if(S[Tx].dep < S[Ty].dep)
            {
                swap(x,y);
                swap(Tx,Ty);
            }
            Sgt::Query(1,1,n,S[Tx].seg,S[x].seg);
            x=S[Tx].f;
            Tx=S[x].top;
        }
        if(S[x].dep > S[y].dep) swap(x,y);
        Sgt::Query(1,1,n,S[x].seg,S[y].seg);
    }
}

void Solve(int l,int r,int L,int R)//第k大
{
    if(l>r) return;
    if(L==R)
    {
        for(int i=l;i<=r;i++)
            if(oper[i].opt==3)
                Ans[oper[i].cnt] = L-1;
        return;
    }

    int M=(L+R)>>1;

    for(int i=l;i<=r;i++)
    {
        if(oper[i].opt==1 && oper[i].value>=M)
            Sgt::Update(1,1,n,S[oper[i].pos].seg,1);
        if(oper[i].opt==2 && oper[i].value>=M)
            Sgt::Update(1,1,n,S[oper[i].pos].seg,-1);
        if(oper[i].opt==3)
        {
            res=0;
            Hld::Solve(oper[i].l,oper[i].r);
            record[i] = res;
        }
    }

    for(int i=l;i<=r;i++)
    {
        if(oper[i].opt==1 && oper[i].value>=M)
            Sgt::Update(1,1,n,S[oper[i].pos].seg,-1);
        if(oper[i].opt==2 && oper[i].value>=M)
            Sgt::Update(1,1,n,S[oper[i].pos].seg,1);
    }

    int l_num=0,r_num=0;
    for(int i=l;i<=r;i++)
    {
        if(oper[i].opt!=3)
        {
            if(oper[i].value >= M)
                qR[++r_num]=oper[i];
            else
                qL[++l_num]=oper[i];
        }
        else
        {
            if(oper[i].cur + record[i] >= oper[i].k)
                qR[++r_num]=oper[i];
            else
            {
                qL[++l_num]=oper[i];
                qL[l_num].cur+=record[i];
            }
        }
    }

    int t=l;
    for(int i=1;i<=l_num;i++) oper[t++]=qL[i];
    for(int i=1;i<=r_num;i++) oper[t++]=qR[i];

    Solve(l,l+l_num-1,L,M);
    Solve(l+l_num,r,M+1,R);
}

int main()
{
    n=get();    m=get();
    for(int i=1;i<=n;i++)
    {
        a[i]=get();
        oper[++cnt].opt=1;  oper[cnt].pos=i;    oper[cnt].value=a[i];
    }

    for(int i=1;i<n;i++)
    {
        x=get();    y=get();
        Add(x,y);
    }

    Hld::First();
    Hld::Dfs1(1,0); Hld::Dfs2(1,0);

    for(int i=1;i<=m;i++)
    {
        k=get();    x=get();    y=get();
        if(k==0)
        {
            oper[++cnt].opt=2;  oper[cnt].pos=x;    oper[cnt].value=a[x];
            oper[++cnt].opt=1;  oper[cnt].pos=x;    oper[cnt].value=y;
            a[x]=y;
        }
        else
        {
            oper[++cnt].opt=3;  oper[cnt].l=x;  oper[cnt].r=y;  oper[cnt].k=k;
            oper[cnt].cnt=++Num;
        }
    }

    Solve(1,cnt,0,INF);

    for(int i=1;i<=Num;i++)
    {
        if(Ans[i]!=-1) printf("%d",Ans[i]);
        else printf("invalid request!");
        printf("\n");
    }
}