SCOI2015 情报传递

wjh15101051's space

卧薪尝胆，厚积薄发。

SCOI2015 情报传递

Date: Sat Nov 03 10:00:21 CST 2018

In Category: NoCategory

Description：

有一个树形的情报网络，每有一个人开始搜集情报他的危险值就会逐日加一， $m$ 次操作，每次让某个人开始搜集情报或者询问从 $a$ 到 $b$ 的链上有多少情报员危险值大于 $C_i$ 。

$1\leqslant n\leqslant 2\times 10^5$

Solution：

设当前查询的时间是第 $k$ 天，那么就是查询有多少人开始的搜集情报的时间 $<k-C_i$ ，那就可以把所有询问离线下来，按时间排序，然后用树链剖分来维护链上和就行了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 200010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

int gen;

void add(int a,int b)

{

	if(a == 0 || b == 0){gen = a + b;return;}

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

struct node

{

	int lc,rc;

	int sum;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

int dep[MAXN],top[MAXN],siz[MAXN],son[MAXN],fa[MAXN],rnk[MAXN],th[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth + 1;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	rnk[k] = ++tot;th[tot] = k;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

void add(int rt,int p,int l,int r)

{

	++t[rt].sum;

	if(l == r)return;

	if(p <= mid)add(t[rt].lc,p,l,mid);

	else add(t[rt].rc,p,mid + 1,r);

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].sum;

	int res = 0;

	if(L <= mid)res += query(t[rt].lc,L,R,l,mid);

	if(R > mid)res += query(t[rt].rc,L,R,mid + 1,r);

	return res;

}

pair<int,int> calc(int a,int b)

{

	pair<int,int> res = make_pair(0,0);

	res.second = dep[a] + dep[b];

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		res.first += query(root,rnk[top[a]],rnk[a],1,n);

		a = fa[top[a]];

	}

	if(dep[a] > dep[b])swap(a,b);

	res.first += query(root,rnk[a],rnk[b],1,n);

	res.second -= 2 * dep[a];

	return res;

}

struct change

{

	int t,p;

}c[MAXN];

int changenum = 0;

struct ask

{

	int t,x,y,c;

	pair<int,int> ans;

}q[MAXN];

int asknum = 0;

bool cmp_ask(ask a,ask b){return a.t - a.c < b.t - b.c;}

bool cmp_t(ask a,ask b){return a.t < b.t;}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)add(rd(),i);

	dfs1(gen,0);dfs2(gen,gen);

	build(root,1,n);

	scanf("%d",&m);

	int opt,x,y,k;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&opt);

		if(opt == 2)

		{

			scanf("%d",&k);

			c[++changenum] = (change){i,k};

		}

		else

		{

			scanf("%d%d%d",&x,&y,&k);

			q[++asknum] = (ask){i,x,y,k};

		}

	}

	sort(q + 1,q + 1 + asknum,cmp_ask);

	int i,j;

	for(i = j = 1;i <= changenum && j <= asknum;)

	{

		if(c[i].t < q[j].t - q[j].c)

		{

			add(root,rnk[c[i].p],1,n);

			++i;

		}

		else

		{

			q[j].ans = calc(q[j].x,q[j].y);

			++j;

		}

	}

	for(;j <= asknum;++j)

	{

		q[j].ans = calc(q[j].x,q[j].y);

	}

	sort(q + 1,q + 1 + asknum,cmp_t);

	for(int i = 1;i <= asknum;++i)

	{

		printf("%d %d\n",q[i].ans.second + 1,q[i].ans.first);

	}

	return 0;

}

In tag: 树-树链剖分数据结构-主席树

wjh15101051