【树链剖分】【函数式权值分块】bzoj1146 [CTSC2008]网络管理Network
2024-09-02 05:18:29
裸题，直接上。复杂度O(n*sqrt(n)*log(n))。
//Num[i]表示树中的点i在函数式权值分块中对应的点
//Map[i]表示函数式权值分块中的点i在树中对应的点
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 80001
#define INF 2147483647
#define NN 87001
#define BN 296
int x,y;
int fa[N],dep[N],siz[N],son[N],Num[N],tot,top[N],n,m,Ks[N],xs[N],ys[N],w[N];
int en,first[N],next[N<<1],v[N<<1];
int en2,en3,ma[NN],a[NN];
int l[BN],sum=1,r[BN],num[N];
int r2[NN],num2[NN],sum2=1;
struct Point{int p,v;}t[NN];
bool operator < (const Point &a,const Point &b){return a.v<b.v;}
struct Val_Block
{
int b[NN],sumv[BN];
void insert(const int &x){++b[x]; ++sumv[num2[x]];}
void erase(const int &x){--b[x]; --sumv[num2[x]];}
}T[285],S;
void AddEdge(const int &U,const int &V)
{
v[++en]=V;
next[en]=first[U];
first[U]=en;
}
void dfs(int U,int Fa,int d)
{
fa[U]=Fa;
dep[U]=d;
siz[U]=1;
for(int i=first[U];i;i=next[i])
if(v[i]!=fa[U])
{
dfs(v[i],U,d+1);
siz[U]+=siz[v[i]];
if(siz[v[i]]>siz[son[U]])
son[U]=v[i];
}
}
void dfs2(int U)
{
if(son[U])
{
top[son[U]]=top[U];
Num[son[U]]=++tot;
dfs2(son[U]);
}
for(int i=first[U];i;i=next[i])
if(v[i]!=fa[U]&&v[i]!=son[U])
{
top[v[i]]=v[i];
Num[v[i]]=++tot;
dfs2(v[i]);
}
}
void makeblock()
{
int sz=sqrt(n);
if(!sz) sz=1;
for(;sum*sz<n;++sum)
{
l[sum]=r[sum-1]+1;
r[sum]=sum*sz;
for(int i=l[sum];i<=r[sum];++i)
num[i]=sum;
}
l[sum]=r[sum-1]+1;
r[sum]=n;
for(int i=l[sum];i<=r[sum];++i)
num[i]=sum;
}
void val_mb()
{
int sz=sqrt(en3);
if(!sz) sz=1;
for(;sum2*sz<en3;++sum2)
{
r2[sum2]=sum2*sz;
for(int i=r2[sum2-1]+1;i<=r2[sum2];++i)
num2[i]=sum2;
}
r2[sum2]=en3;
for(int i=r2[sum2-1]+1;i<=r2[sum2];++i)
num2[i]=sum2;
}
void Init_Ts()
{
for(int i=1;i<=sum;++i)
{
T[i]=T[i-1];
for(int j=l[i];j<=r[i];++j)
T[i].insert(a[j]);
}
}
int Query(const int &x,const int &y,const int &K)
{
//构建零散部分的权值分块
int U=x,V=y,cnt=0,res=INF;
int f1=top[U],f2=top[V];
while(f1!=f2)
{
if(dep[f1]<dep[f2])
{
swap(U,V);
swap(f1,f2);
}
if(num[Num[f1]]+1>=num[Num[U]])
for(int i=Num[f1];i<=Num[U];++i)
S.insert(a[i]);
else
{
for(int i=Num[f1];i<=r[num[Num[f1]]];++i)
S.insert(a[i]);
for(int i=l[num[Num[U]]];i<=Num[U];++i)
S.insert(a[i]);
}
U=fa[f1];
f1=top[U];
}
if(dep[U]>dep[V])
swap(U,V);
if(num[Num[U]]+1>=num[Num[V]])
for(int i=Num[U];i<=Num[V];++i)
S.insert(a[i]);
else
{
for(int i=Num[U];i<=r[num[Num[U]]];++i)
S.insert(a[i]);
for(int i=l[num[Num[V]]];i<=Num[V];++i)
S.insert(a[i]);
}
//计算答案
for(int i=sum2;i>=1;--i)
{
int tcnt=0;
U=x; V=y;
f1=top[U]; f2=top[V];
while(f1!=f2)
{
if(dep[f1]<dep[f2])
{
swap(U,V);
swap(f1,f2);
}
if(num[Num[f1]]+1<num[Num[U]])
tcnt+=T[num[Num[U]]-1].sumv[i]-T[num[Num[f1]]].sumv[i];
U=fa[f1];
f1=top[U];
}
if(dep[U]>dep[V])
swap(U,V);
if(num[Num[U]]+1<num[Num[V]])
tcnt+=T[num[Num[V]]-1].sumv[i]-T[num[Num[U]]].sumv[i];
tcnt+=S.sumv[i];
cnt+=tcnt;
if(cnt>=K)
{
cnt-=tcnt;
for(int j=r2[i];;--j)
{
U=x; V=y;
f1=top[U]; f2=top[V];
while(f1!=f2)
{
if(dep[f1]<dep[f2])
{
swap(U,V);
swap(f1,f2);
}
if(num[Num[f1]]+1<num[Num[U]])
cnt+=T[num[Num[U]]-1].b[j]-T[num[Num[f1]]].b[j];
U=fa[f1];
f1=top[U];
}
if(dep[U]>dep[V])
swap(U,V);
if(num[Num[U]]+1<num[Num[V]])
cnt+=T[num[Num[V]]-1].b[j]-T[num[Num[U]]].b[j];
cnt+=S.b[j];
if(cnt>=K)
{
res=j;
goto OUT;
}
}
}
}
OUT:
//清空零散部分的权值分块
U=x,V=y;
f1=top[U],f2=top[V];
while(f1!=f2)
{
if(dep[f1]<dep[f2])
{
swap(U,V);
swap(f1,f2);
}
if(num[Num[f1]]+1>=num[Num[U]])
for(int i=Num[f1];i<=Num[U];++i)
S.erase(a[i]);
else
{
for(int i=Num[f1];i<=r[num[Num[f1]]];++i)
S.erase(a[i]);
for(int i=l[num[Num[U]]];i<=Num[U];++i)
S.erase(a[i]);
}
U=fa[f1];
f1=top[U];
}
if(dep[U]>dep[V])
swap(U,V);
if(num[Num[U]]+1>=num[Num[V]])
for(int i=Num[U];i<=Num[V];++i)
S.erase(a[i]);
else
{
for(int i=Num[U];i<=r[num[Num[U]]];++i)
S.erase(a[i]);
for(int i=l[num[Num[V]]];i<=Num[V];++i)
S.erase(a[i]);
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
makeblock();
for(int i=1;i<=n;++i)
scanf("%d",&w[i]);
for(int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
AddEdge(x,y);
AddEdge(y,x);
}
top[1]=1;
Num[1]=++tot;
dfs(1,0,1);
dfs2(1);
for(int i=1;i<=n;++i)
{
t[Num[i]].v=w[i];
t[Num[i]].p=Num[i];
}
en2=n;
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&Ks[i],&xs[i],&ys[i]);
if(!Ks[i])
{
t[++en2].v=ys[i];
t[en2].p=en2;
}
}
sort(t+1,t+en2+1);
ma[a[t[1].p]=++en3]=t[1].v;
for(int i=2;i<=en2;++i)
{
if(t[i].v!=t[i-1].v) ++en3;
ma[a[t[i].p]=en3]=t[i].v;
}
val_mb();
Init_Ts();
en2=n;
for(int i=1;i<=m;++i)
{
if(Ks[i])
{
int ans=Query(xs[i],ys[i],Ks[i]);
if(ans==INF) puts("invalid request!");
else printf("%d\n",ma[ans]);
}
else
{
++en2;
for(int j=num[Num[xs[i]]];j<=sum;++j)
{
T[j].erase(a[Num[xs[i]]]);
T[j].insert(a[en2]);
}
a[Num[xs[i]]]=a[en2];
}
}
return 0;
}
最新文章
- Lamp（Ubuntu 12.04 LTS） 之 htaccess的使用
- &,引用复制@,忽略错误提示
- svn学习笔记（2）操作----还原，重命名，冲突处理，权限配置等
- Linux下RPM、tar.gz、DEB格式软件包的区别
- Display Images in widget
- free 和 fclose
- VS2010/MFC：模态对话框及其弹出过程
- Alamofire源码解读系列(六)之Task代理(TaskDelegate)
- Action和Fuc的区别
- ctags-vim代码间快速跳转
- GWAS：拒绝假阳性之case和control数量比例严重失衡的解决方案（SAIGE模型的应用）
- Nginx 完全配置
- Selenium自动化Chrome浏览器 在windows下窗口最大化
- Consumer group理解深入
- 「HNOI2016」网络 解题报告
- Thread线程中断相关方法
- PAT A1013 Battle Over Cities （25 分）——图遍历，联通块个数
- webpack-clean-webpack-plugin
- T4模板根据数据库表和列的Description生成代码的summary的终极解决方案
- 【钉钉PC】PC端钉钉清除缓存