您的位置: 首页  >  IT文章  >  [Luogu4175][CTSC2008]网络管理Network sol

[Luogu4175][CTSC2008]网络管理Network sol

分类: IT文章 • 2022-09-04 00:24:09

又是权限题qwq
一句话题意：带修改树上路径第k大

数据结构？还是再见吧。学一手合格的整体二分，只有思维强大，才能见题拆题。

如果你做过整体二分的动态区间第k大就会发现这是一样的题。
无非是区间变成了树上路径。
怎么办呢？树剖+dfn序不就好了吗。
复杂度算下来貌似是(O(nlog^3{n}))的。
(O(mbox{跑得过}))

code

注意是第k大啊！第k大啊！
写成第k小就爆零了。
神坑样例。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 8e4+5;
int gi()
{
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
struct edge{int to,next;}a[N<<1];
struct node{int opt,x,y,id,k;}q[N<<2],q1[N<<2],q2[N<<2];
int n,m,head[N],cnt,qcnt,T[N],fa[N],dep[N],sz[N],son[N],top[N],dfn[N],tmp[N],c[N],ans[N];
void dfs1(int u,int f)
{
	fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
	for (int e=head[u];e;e=a[e].next)
	{
		int v=a[e].to;if (v==f) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if (sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int up)
{
	top[u]=up;dfn[u]=++cnt;
	if (son[u]) dfs2(son[u],up);
	for (int e=head[u];e;e=a[e].next)
		if (a[e].to!=fa[u]&&a[e].to!=son[u])
			dfs2(a[e].to,a[e].to);
}
void modify(int k,int v){while (k<=n) c[k]+=v,k+=k&-k;}
int query(int k){int s=0;while (k) s+=c[k],k-=k&-k;return s;}
int lca(int x,int y)
{
	while (top[x]^top[y])
	{
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
int calc(int x,int y)
{
	int res=0;
	while (top[x]^top[y])
	{
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		res+=query(dfn[x])-query(dfn[top[x]]-1);
		x=fa[top[x]];
	}
	if (dep[x]<dep[y]) swap(x,y);
	res+=query(dfn[x])-query(dfn[y]-1);
	return res;
}
void solve(int L,int R,int l,int r)
{
	if (L>R) return;
	if (l==r)
	{
		for (int i=L;i<=R;i++)
			if (q[i].opt==0) ans[q[i].id]=l;
		return;
	}
	int mid=l+r>>1;
	for (int i=L;i<=R;i++)
		if (q[i].opt==0) tmp[q[i].id]=calc(q[i].x,q[i].y);
		else if (q[i].y<=mid) modify(q[i].x,q[i].opt);
	for (int i=L;i<=R;i++)
		if (q[i].opt!=0&&q[i].y<=mid) modify(q[i].x,-q[i].opt);
	int t1=0,t2=0;
	for (int i=L;i<=R;i++)
		if (q[i].opt==0)
			if (q[i].k<=tmp[q[i].id]) q1[++t1]=q[i];
			else q[i].k-=tmp[q[i].id],q2[++t2]=q[i];
		else
			if (q[i].y<=mid) q1[++t1]=q[i];
			else q2[++t2]=q[i];
	for (int i=L,j=1;j<=t1;i++,j++) q[i]=q1[j];
	for (int i=L+t1,j=1;j<=t2;i++,j++) q[i]=q2[j];
	solve(L,L+t1-1,l,mid);solve(L+t1,R,mid+1,r);
}
int main()
{
	n=gi();m=gi();
	for (int i=1;i<=n;i++) T[i]=gi();
	for (int i=1,u,v;i<n;i++)
	{
		u=gi(),v=gi();
		a[++cnt]=(edge){v,head[u]};head[u]=cnt;
		a[++cnt]=(edge){u,head[v]};head[v]=cnt;
	}
	dfs1(1,0);cnt=0;dfs2(1,1);cnt=0;
	for (int i=1;i<=n;i++)
		q[++cnt]=(node){1,dfn[i],T[i]};
	while (m--)
	{
		int k=gi(),x=gi(),y=gi();
		if (k)
		{
			int len=dep[x]+dep[y]-2*dep[lca(x,y)]+1;
			if (k>len) k=1e8;else k=len-k+1;
			q[++cnt]=(node){0,x,y,++qcnt,k};
		}
		else
		{
			q[++cnt]=(node){-1,dfn[x],T[x]};
			T[x]=y;
			q[++cnt]=(node){1,dfn[x],T[x]};
		}
	}
	solve(1,cnt,0,1e8);
	for (int i=1;i<=qcnt;i++)
		if (ans[i]==1e8) puts("invalid request!");
		else printf("%d
",ans[i]);
	return 0;
}

相关推荐