NKOJ 2251 网络管理（树链剖分+树套树（树状数组+主席树））

发表于 |
字数统计: 1,967字 | 阅读时长 ≈ 9min

P2251【动态树】网络管理

问题描述

M公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信。 高速光缆的数据传输速度非常快，以至于利用光缆传输的延迟时间可以忽略。但是由于路由器老化，在这些路由器上进行数据交换会带来很大的延迟。而两个路由器之间的通信延迟时间则与这两个路由器通信路径上所有路由器中最大的交换延迟时间有关。

作为M公司网络部门的一名实习员工，现在要求你编写一个简单的程序来监视公司的网络状况。该程序能够随时更新网络状况的变化信息（路由器数据交换延迟时间的变化），并且根据询问给出两个路由器通信路径上延迟第k大的路由器的延迟时间。

【任务】 你的程序从输入文件中读入N个路由器和N-1条光缆的连接信息，每个路由器初始的数据交换延迟时间Ti，以及Q条询问（或状态改变）的信息。并依次处理这Q条询问信息，它们可能是： 1. 由于更新了设备，或者设备出现新的故障，使得某个路由器的数据交换延迟时间发生了变化。 2. 查询某两个路由器a和b之间的路径上延迟第k大的路由器的延迟时间。

输入格式

第一行为两个整数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大的路由器的延迟时间。
注意a可以等于b，此时路径上只有一个路由器。

输出格式

对于每一个第二种询问（k>0），输出一行。包含一个整数为相应的延迟时间。如果路径上的路由器不足k个，则输出信息“invalid request!”（全部小写不包含引号，两个单词之间有一个空格）。

样例输入

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

样例输出

3
2
2
invalid request!

提示

10% 测试数据满足N<=8000,Q<=3000
40% 测试数据满足所有询问中1<=K<=5 。即路由器的延迟时间不会发生变化。
100% 测试数据满足N,Q<=80000，任意一个路由器在任何时刻都满足延迟时间小于106。对于所有询问满足0<=K<=N 。

此题显然树链剖分，然后求区间第K大，用树套树维护，为了好写，当然选择树状数组+主席树，主要是处理不连续区间中的第K大的问题，考虑一下求动态区间第K大的做法，实际上可以将树状数组中会用到的值先提前存到数组中，然后直接采取与静态区间第K小一样的做法即可。具体不太好描述，可以参见代码领悟一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 200005
#define M 20000005
using namespace std;
const int T=1e6;
int n,q,Ti[N],Ai[N],VT,dep[N],son[N],fa[N],top[N],id[N];
int tot,rt[N],ls[M],rs[M],v[M];
int TOT,LA[N],NE[N],EN[N];
int A[N],B[N],c1,c2;
void ADD(int x,int y)
{
    TOT++;
    EN[TOT]=y;
    NE[TOT]=LA[x];
    LA[x]=TOT;
}
int FHE(int x,int f)
{
    int i,y,t=0,s=1,tmp;
    fa[x]=f;
    dep[x]=dep[f]+1;
    for(i=LA[x];i;i=NE[i])
    {
        y=EN[i];
        if(y!=f)
        {
            tmp=FHE(y,x);s+=tmp;
            if(s>t)t=s,son[x]=y;
        }
    }
    return s;
}
void CHE(int x,int f)
{
    int i,y;
    top[x]=f;
    id[x]=++VT;
    Ai[VT]=Ti[x];
    if(son[x])CHE(son[x],f);
    for(i=LA[x];i;i=NE[i])
    {
        y=EN[i];
        if(y!=fa[x]&&y!=son[x])CHE(y,y);
    }
}
int CO(int p)
{
    int o=++tot;
    ls[o]=ls[p];
    rs[o]=rs[p];
    v[o]=v[p];
    return o;
}
int ADD(int p,int l,int r,int k,int d)
{
    int o=CO(p);v[o]+=d;
    if(l==r)return o;
    int mid=l+r>>1;
    if(k<=mid)ls[o]=ADD(ls[p],l,mid,k,d);
    else rs[o]=ADD(rs[p],mid+1,r,k,d);
    return o;
}
int GA(int p,int l,int r,int x,int y)
{
    if(x<=l&&y>=r)return v[p];
    int mid=l+r>>1,s=0;
    if(x<=mid&&y>=l)s+=GA(ls[p],l,mid,x,y);
    if(x<=r&&y>mid)s+=GA(rs[p],mid+1,r,x,y);
    return s;
}
void MD(int x,int k,int d)
{for(int i=x;i<=n;i+=(i&-i))rt[i]=ADD(rt[i],0,T,k,d);}
void GSA(int x)
{for(int i=x;i;i-=(i&-i))A[++c1]=rt[i];}
void GSB(int x)
{for(int i=x;i;i-=(i&-i))B[++c2]=rt[i];}
int Gcnt(int x,int y)
{
    int ans=0;c1=c2=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans+=dep[x]-dep[top[x]]+1;
        GSA(id[x]);GSB(id[top[x]]-1);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans+=dep[y]-dep[x]+1;
    GSA(id[y]);GSB(id[x]-1);
    return ans;
}
int Work(int k,int l,int r)
{
    if(l==r)return l;
    int i,sum=0,mid=l+r>>1;//sum为右儿子代表的权值区间的cnt
    for(i=1;i<=c1;i++)sum+=v[rs[A[i]]];
    for(i=1;i<=c2;i++)sum-=v[rs[B[i]]];
    if(sum>=k)//全部走到右儿子
    {
        for(i=1;i<=c1;i++)A[i]=rs[A[i]];
        for(i=1;i<=c2;i++)B[i]=rs[B[i]];
        return Work(k,mid+1,r);
    }
    else//全部走到左儿子
    {
        for(i=1;i<=c1;i++)A[i]=ls[A[i]];
        for(i=1;i<=c2;i++)B[i]=ls[B[i]];
        return Work(k-sum,l,mid);
    }
}
void Solve(int k,int x,int y)
{
    if(Gcnt(x,y)<k){printf("invalid request!\n");return;}
    printf("%d\n",Work(k,0,T));
}
int main_main()
{
    int i,x,y,k;
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++)scanf("%d",&Ti[i]);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        ADD(x,y);ADD(y,x);
    }
    FHE(1,0);CHE(1,1);
    for(i=1;i<=n;i++)MD(i,Ai[i],1);
    while(q--)
    {
        scanf("%d%d%d",&k,&x,&y);
        if(k==0)
        {
            x=id[x];
            MD(x,Ai[x],-1);
            Ai[x]=y;
            MD(x,Ai[x],1);
        }
        else Solve(k,x,y);
    }
}
const int main_stack=16;
char my_stack[256<<20];
int main() {
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");
  main_main();
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");
  return 0;
}