题目描述
M公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信。 高速光缆的数据传输速度非常快，以至于利用光缆传输的延迟时间可以忽略。但是由于路由器老化，在这些路由器上进行数据交换会带来很大的延迟。而两个路由器之间的通信延迟时间则与这两个路由器通信路径上所有路由器中最大的交换延迟时间有关。作为M公司网络部门的一名实习员工，现在要求你编写一个简单的程序来监视公司的网络状况。该程序能够随时更新网络状况的变化信息（路由器数据交换延迟时间的变化），并且根据询问给出两个路由器通信路径上延迟第k大的路由器的延迟时间。
【任务】 你的程序从输入文件中读入N个路由器和N-1条光缆的连接信息，每个路由器初始的数据交换延迟时间Ti，以及Q条询问（或状态改变）的信息。并依次处理这Q条询问信息，它们可能是：
- 由于更新了设备，或者设备出现新的故障，使得某个路由器的数据交换延迟时间发生了变化。
- 查询某两个路由器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!”（全部小写不包含引号，两个单词之间有一个空格）。
输入输出样例
输入样例#1：
|
1 2 3 4 5 6 7 8 9 10 11 |
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 |
输出样例#1：
|
1 2 3 4 |
3 2 2 invalid request! |
说明
测试数据满足N,Q<=80000,任意一个路由器在任何时刻都满足延迟时间小于10^8。对于所有询问满足0<=K<=N 。
链上第k大问题，带修改。
终于把3个月前咕掉的数据结构体补了，
实际上是我写的树套树常数太大40分没得卡进去，
然而再次写的时候还是花了1.5小时码代码+0.5小时多的debug。
一开始写的树链剖分树套树\(O(n^4logn) \) 据说能过但是写了写只有40分
然后想到可以用整体二分达到 \(O(n^3logn) \)
Solution
对于一个修改操作，我们拆成两个操作，
|
1 2 3 |
q[++tot]=(node){0,-1,val[y],y,1};//加一个减去原先贡献的操作 val[y]=z;//val[i]表示i的点权，修改 q[++tot]=(node){0,1,val[y],y,1}; |
这道题是树上的问题…
树剖！
树剖肯定是要的，这辈子都不会抛弃树剖的。
主席树又不会，只能打打树剖才能转换为区间上的问题的样子呢。
|
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 153 154 155 156 157 158 159 160 161 162 163 164 165 166 |
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; //struct Tree_Chain; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } const int maxn=5e5+10; struct E{ int next,to; }tu[maxn*2]; int head[maxn],cnt,tot; int n,m,qwq; long long val[maxn]; void add(int next,int to){ tu[cnt].next=head[next]; tu[cnt].to=to; head[next]=cnt++; } int top[maxn],rnk[maxn],sz[maxn],son[maxn],fa[maxn],tid[maxn],dep[maxn],tim; void dfs1(int x,int father,int deep){//树剖 sz[x]=1; fa[x]=father; dep[x]=deep; for(int i=head[x];~i;i=tu[i].next){ int u=tu[i].to; if(u==father)continue; dfs1(u,x,deep+1); sz[x]+=sz[u]; if(son[x]==-1||sz[son[x]]<sz[u]){ son[x]=u; } } } void dfs2(int x,int tp){ top[x]=tp; tid[x]=++tim; rnk[tim]=x; if(son[x]==-1)return; dfs2(son[x],tp); for(int i=head[x];~i;i=tu[i].next){ int u=tu[i].to; if(u==fa[x]||u==son[x])continue; dfs2(u,u); } } int sumv[maxn*4];//线段树 #define lson (o<<1) #define rson (o<<1|1) void pushup(int o){ sumv[o]=sumv[lson]+sumv[rson]; } void change(int o,int l,int r,int x,int v){ if(l==r){ sumv[o]+=v; return; } int mid=(l+r)>>1; if(x<=mid)change(lson,l,mid,x,v); else change(rson,mid+1,r,x,v); pushup(o); } int query(int o,int l,int r,int l1,int r1){ if(l>=l1&&r<=r1){ return sumv[o]; } if(l>r1||r<l1)return 0; int mid=(l+r)>>1; return query(lson,l,mid,l1,r1)+query(rson,mid+1,r,l1,r1); } int query_path(int x,int y){ int ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); ans+=query(1,1,n,tid[top[x]],tid[x]); x=fa[top[x]]; } if(tid[x]>tid[y])swap(x,y); ans+=query(1,1,n,tid[x],tid[y]); return ans; }//树剖 struct node{ long long x,y,k,id,type; }q[maxn],q1[maxn],q2[maxn]; long long ans[maxn]; void solve(int L,int R,int l,int r){//q1表示答案在l~mid，q2表示答案在mid+1~r内 if(L>R)return; if(l==r){ for(int i=L;i<=R;i++)if(q[i].type==2)ans[q[i].id]=l; return; } int mid=(l+r)>>1; int cnt1=0,cnt2=0; for(int i=L;i<=R;i++){ if(q[i].type==1){ if(q[i].k>mid){ change(1,1,n,tid[q[i].id],q[i].y); q2[++cnt2]=q[i]; } else q1[++cnt1]=q[i]; } else{ int ret=query_path(q[i].x,q[i].y); if(ret>=q[i].k)q2[++cnt2]=q[i];//大于mid的数字个数>=q[i].k，说明实际答案比mid大 else{ q[i].k-=ret;//减去贡献 q1[++cnt1]=q[i]; } } } for(int i=1;i<=cnt2;i++){ if(q2[i].type==1)change(1,1,n,tid[q2[i].id],-q2[i].y); }//清除 for(int i=1;i<=cnt1;i++)q[L+i-1]=q1[i]; for(int i=1;i<=cnt2;i++)q[L+cnt1+i-1]=q2[i]; solve(L,L+cnt1-1,l,mid); solve(L+cnt1,R,mid+1,r); }//整体二分 int num; long long a[maxn],map_rnk[maxn],pos;//a数组用来存将要被离散化的数字,pos存询问个数...很乱sry int main(){ memset(head,-1,sizeof(head)); memset(son,-1,sizeof(son)); n=read(),m=read(); for(int i=1;i<=n;i++){ val[i]=read(); q[++tot]=(node){0,1,val[i],i,1}; a[++num]=val[i]; } for(int i=1;i<n;i++){ int x=read(),y=read(); add(x,y); add(y,x); } dfs1(1,0,0); dfs2(1,1); for(int i=1;i<=m;i++){ int x=read(),y=read(),z=read(); if(x==0){ q[++tot]=(node){0,-1,val[y],y,1}; val[y]=z; q[++tot]=(node){0,1,val[y],y,1}; a[++num]=z; } else{ q[++tot]=(node){y,z,x,++pos,2};//贼坑的数据输入格式... } }/*以下为离散化*/ sort(a+1,a+1+num); int qaq=unique(a+1,a+1+num)-a-1; for(int i=1;i<=tot;i++) if(q[i].type!=2){ int tmp=lower_bound(a+1,a+1+qaq,q[i].k)-a; map_rnk[tmp]=q[i].k; q[i].k=tmp; } solve(1,tot,0,qaq+1); for(int i=1;i<=pos;i++){ if(ans[i]==0)puts("invalid request!"); else printf("%lld\n",map_rnk[ans[i]]); } return 0; } |
说点什么