洛谷 P4216 [SCOI2015]情报传递（树剖，树状数组）

传送门

解题思路

若强制在线，可以考虑用树剖+主席树，相当于每次询问两个点之间的路径上在 \(i-C_i\) 时刻之前开始搜集情报的人数。

但是这题可以离线，于是可以把询问按照 \(i-C_i\) 离线一下，就可以用线段树/树状数组来维护了。

注意一定要区分原编号和dfn编号。

时间复杂度：\(O(nlog^2n)\)

当然可以优化到一个log：不用树剖。

直接维护dfs序上差分，每次更新一个点相当于更新以它为根的整个子树，每次查询转化为两次单点查询和查询LCA、fa[LCA]的信息。

AC代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
templateinline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
templateinline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
const int maxn=4e5+5;
int n,m,t[maxn],cnt,p[maxn],siz[maxn],dep[maxn],tp[maxn],cntt,num;
int son[maxn],dfn[maxn],times,d[maxn],fa[maxn],rt;
struct node{
	int v,next;
}e[maxn];
struct Node{
	int ans1,ans2,c,x,y,id;
}q[maxn];
bool cmp1(Node a,Node b){
	return a.csiz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int top){
	dfn[u]=++times;
	tp[u]=top;
	if(son[u]) dfs2(son[u],top);
	for(int i=p[u];i!=-1;i=e[i].next){
		int v=e[i].v;
		if(v==son[u]) continue;
		dfs2(v,v);
	}
}
inline int lowbit(int x){
	return x&-x;
}
void update(int x){
	for(int i=x;i<=n;i+=lowbit(i)) d[i]++;
}
int query(int x){
	int res=0;
	for(int i=x;i>=1;i-=lowbit(i)) res+=d[i];
	return res;
}
void get_ans(Node &a){
	int x=a.x,y=a.y;
	while(tp[x]!=tp[y]){
		if(dep[tp[x]]>dep[tp[y]]) swap(x,y);
		a.ans2+=query(dfn[y])-query(dfn[tp[y]]-1);
		y=fa[tp[y]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	a.ans1=dep[a.x]+dep[a.y]-2*dep[x]+1;
	a.ans2+=query(dfn[y])-query(dfn[x]-1);
}
int main(){
	memset(p,-1,sizeof(p));
	read(n);
	for(int i=1;i<=n;i++){
		int x;
		read(x);
		if(x==0) rt=i;
		else insert(x,i),fa[i]=x;
	}
	dfs1(rt);
	dfs2(rt,rt);
	read(m);
	for(int i=1;i<=m;i++){
		int ty;
		read(ty);
		if(ty==1){
			int x,y,c;
			read(x);read(y);read(c);
			q[++num].x=x;
			q[num].y=y;
			q[num].c=i-c;
			q[num].id=i;
		}else{
			int x;
			read(x);
			t[i]=x;
		}
	}
	sort(q+1,q+num+1,cmp1);
	int now=1;
	for(int i=1;i<=m;i++){
		while(now<=num&&q[now].c<=i) get_ans(q[now]),now++;
		if(t[i]) update(dfn[t[i]]);		
	}
	while(now<=num) get_ans(q[now]),now++;
	sort(q+1,q+num+1,cmp2);
	for(int i=1;i<=num;i++) print(q[i].ans1),putchar(' '),print(q[i].ans2),puts("");
	return 0;
}
题解省选洛谷题解树链剖分树状数组数据结构

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

数据结构--栈（C语言实现）

Ubuntu 断网问题解决

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

数据结构----单链表升级版

数据结构/PTA-畅通工程之最低成本建设问题-畅通工程之局部最小花费问题/图/最小生成树

数据结构+java中常用的集合类

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

数据结构 之二叉树

数据结构与算法之PHP查找算法（哈希查找）

标签