P4175 [CTSC2008]网络管理
题目
树上单点修改，查询路径第 k 大。
解答
这道题做法很多，有 树剖+线段树+平衡树+二分 的，也有 树剖+可持久化线段树+树状数组 的，也有 可持久化线段树+差分+树状数组 的，还有就是 整体二分+树剖 的。
复杂度都是几个 (log) 的做法。
这里先暂时只说一个树分块带修莫队的 (O(n^{frac{5}{3}})) 做法。
首先树分块然后莫队，这里我们可以利用到一个莫队的很大优势：维护的信息是全局的。
也就是说，我们现在相当于维护的就是全局的第 (k) 大值。
但是这个时候因为复杂度已经很高了，我们需要一种支持 (O(1)) 插入，(O(sqrt{n})) 内询问第 (k) 大的数据结构。
线段树肯定不行了，这里是值域分块。
每次我们从后往前跳，找到对应块，然后一个点一个点暴力跳，时间复杂度是根号级别的。
代码：
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
#define ll long long
const int N=2*(8e4)+5,INF=1e9+7,B=505;
struct Query{
int u,v,k,t,id;
Query(int u=0,int v=0,int k=0,int t=0,int id=0):u(u),v(v),k(k),t(t),id(id){}
}Q[N];
struct Change{
int u,las,nex;
Change(int u=0,int las=0,int nex=0):u(u),las(las),nex(nex){}
}C[N];
int val[N],w[N],fa[N],dep[N],son[N],sta[N];
int siz[N],top[N],bl[N],a[N],sum[N];
int Sum[B],num[B][B],blo[N];
int b[N],Cnt,SUM,Vblock,VB;
bool vis[N];
int n,m,q,Top,idx,cnt1,cnt2,block;
ll res,Ans[N];
vector<int> vec[N];
void dfs1(int u,int f){
int now=Top;
sta[++Top]=u,fa[u]=f,dep[u]=dep[f]+1,siz[u]=1;//压入栈和更新信息
for(auto v:vec[u]){
if(v==f) continue;
dfs1(v,u);
if(Top-now>block){//如果里面的点多于 B 个
idx++;//块编号
while(Top!=now) bl[sta[Top--]]=idx;//更新节点所属块
}
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
return ;
}
void dfs2(int u,int f){//树剖预处理
top[u]=f;
if(!son[u]) return ;
dfs2(son[u],f);
for(auto v:vec[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
return ;
}
inline int QueryLca(int u,int v){//查询lca
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u=fa[top[u]];
}
if(dep[u]<dep[v]) return u;
return v;
}
inline bool cmp(Query a,Query b){//莫队排序
if(bl[a.u]==bl[b.u]){
if(bl[a.v]==bl[b.v]) return a.t<b.t;
return bl[a.v]<bl[b.v];
}
return bl[a.u]<bl[b.u];
}
inline void Add(int u){//更新添加a[u]的影响
num[blo[u]][u-(blo[u]-1)*Vblock]++;
Sum[blo[u]]++;
SUM++;
return ;
}
inline void Del(int u){//更新删掉a[u]的影响
num[blo[u]][u-(blo[u]-1)*Vblock]--;
Sum[blo[u]]--;
SUM--;
return ;
}
inline void Update(int u){//把u这个点取反的影响（用变不用，不用变用）
if(vis[u]) Del(a[u]),vis[u]=false;
else Add(a[u]),vis[u]=true;
return ;
}
inline void Modify(int u,int t){//把u这个点的颜色换成t的影响
if(vis[u]) Del(a[u]),Add(t);
a[u]=t;
return ;
}
inline void Move(int u,int v){//把u->v这条路径的更新了
if(dep[u]<dep[v]) swap(u,v);
while(dep[u]>dep[v]) Update(u),u=fa[u];
while(u!=v) Update(u),Update(v),u=fa[u],v=fa[v];
return ;
}
int main(){
read(n),read(q);
block=pow(n,2.0/3);
for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i];
Cnt=n;
for(int i=1;i<n;i++){//建图
int u,v;read(u),read(v);
vec[u].push_back(v),vec[v].push_back(u);
}
for(int i=1;i<=q;i++){
int op,u,v;
read(op),read(u),read(v);
if(op==0) C[++cnt1]=Change(u,sta[u],v),b[++Cnt]=v;//操作，sta是当前的颜色
else ++cnt2,Q[cnt2]=Query(u,v,op,cnt1,cnt2);//l,r,t,id
}
sort(b+1,b+Cnt+1);
int Id=unique(b+1,b+Cnt+1)-b-1;
Vblock=sqrt(Id);
for(int i=1;i<=Id;i++) blo[i]=(i-1)/Vblock+1;
VB=(Id-1)/Vblock+1;
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+Id+1,a[i])-b,sta[i]=a[i];//a是最初的颜色
for(int i=1;i<=cnt1;i++) C[i].nex=lower_bound(b+1,b+Id+1,C[i].nex)-b,C[i].las=sta[C[i].u],sta[C[i].u]=C[i].nex;
memset(sta,0,sizeof(sta));
dfs1(1,0),dfs2(1,1);//分块和LCA预处理
while(Top>0) bl[sta[Top--]]=idx;//分完块
sort(Q+1,Q+cnt2+1,cmp);//莫队排序
int u,v,t;
u=v=1,t=0;
Update(1);//初始化第一个点
for(int i=1;i<=cnt2;i++){//处理询问
while(t<Q[i].t) Modify(C[t+1].u,C[t+1].nex),t++;//修正时间
while(t>Q[i].t) Modify(C[t].u,C[t].las),--t;
Update(QueryLca(u,v));//两个LCA在这里要单独讨论
if(u!=Q[i].u) Move(u,Q[i].u),u=Q[i].u;//u更新到u`
if(v!=Q[i].v) Move(v,Q[i].v),v=Q[i].v;//v更新到v`
Update(QueryLca(u,v));//讨论
int now=VB,rk=Q[i].k,pos=Vblock;
if(rk>SUM) continue;
while(rk>Sum[now]&&now>=0) rk-=Sum[now],now--;
while(rk>num[now][pos]&&pos>=1) rk-=num[now][pos],pos--;
Ans[Q[i].id]=b[(now-1)*Vblock+pos];
}
for(int i=1;i<=cnt2;i++){
if(Ans[i]) write(Ans[i]),putchar('
');
else puts("invalid request!");
}
return 0;
}
坑
这道题询问区间第 k 大，然后求成了区间第 k 小，还过了样例...懵逼了好久。。