欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

HDU 3966 + 树链剖分复习 + 视频讲解

程序员文章站 2022-06-23 09:43:11
树链剖分学习 参考代码:#include #include #include #include #include #include #include #include

树链剖分学习

参考代码:

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
const int N = 1005;
const int maxn = 1e6 + 5;
struct node
{
	int v, nex;
} edge[maxn << 1];
int head[maxn], w[maxn], son[maxn], deep[maxn];
int pre[maxn], sizx[maxn], dfn[maxn], top[maxn], a[maxn];
int cnt, cnx;
void add(int u, int v)
{
	edge[cnt].v = v, edge[cnt].nex = head[u];
	head[u] = cnt++;
}
void dfs1(int u, int fa)
{
	pre[u] = fa;
	deep[u] = deep[fa] + 1;
	sizx[u] = 1;
	int maxson = -1;
	for (int i = head[u]; ~i; i = edge[i].nex)
	{
		int v = edge[i].v;
		if (v != fa)
		{
			dfs1(v, u);
			sizx[u] += sizx[v];
			if (maxson < sizx[v])
			{
				son[u] = v;
				maxson = sizx[v];
			}
		}
	}
}
void dfs2(int u, int t)
{
	top[u] = t;
	dfn[u] = ++cnx;
	a[cnx] = w[u];
	if (!son[u])
		return;
	dfs2(son[u], t);
	for (int i = head[u]; ~i; i = edge[i].nex)
	{
		int v = edge[i].v;
		if (v != pre[u] && v != son[u])
		{
			dfs2(v, v);
		}
	}
}
struct vain
{
	int l, r, p, lazy;
} tr[maxn << 2];
void pushdown(int k)
{
	if (tr[k].lazy)
	{
		tr[k << 1].p += tr[k].lazy;
		tr[k << 1 | 1].p += tr[k].lazy;
		tr[k << 1].lazy += tr[k].lazy;
		tr[k << 1 | 1].lazy += tr[k].lazy;
		tr[k].lazy = 0;
	}
}
void build(int k, int l, int r)
{
	tr[k].l = l, tr[k].r = r, tr[k].lazy = 0;
	if (l == r)
	{
		tr[k].p = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
}
void modify(int k, int ql, int qr, int w)
{
	if (tr[k].l >= ql && tr[k].r <= qr)
	{
		tr[k].p += w;
		tr[k].lazy += w;
		return;
	}
	pushdown(k);
	int mid = tr[k].l + tr[k].r >> 1;
	if (ql <= mid)
	{
		modify(k << 1, ql, qr, w);
	}
	if (qr > mid)
	{
		modify(k << 1 | 1, ql, qr, w);
	}
}
int query(int k, int pos)
{
	if (tr[k].l == tr[k].r)
	{
		return tr[k].p;
	}
	pushdown(k);
	int mid = tr[k].l + tr[k].r >> 1;
	if (mid >= pos)
		return query(k << 1, pos);
	else
		return query(k << 1 | 1, pos);
}
void swap(int &x, int &y)
{
	int tep = x;
	x = y, y = tep;
}
void mtre(int x, int y, int z)
{
	while (top[x] != top[y])
	{
		if (deep[top[x]] < deep[top[y]])
			swap(x, y);
		modify(1, dfn[top[x]], dfn[x], z);
		x = pre[top[x]];
	}
	if (deep[x] > deep[y])
		swap(x, y);
	modify(1, dfn[x], dfn[y], z);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, q;
	while (cin >> n >> m >> q)
	{
		memset(son, 0, sizeof son);
		memset(head, -1, sizeof head);
		cnx = cnt = 0;
		int u, v;
		for (int i = 1; i <= n; i++)
			cin >> w[i];
		for (int i = 0; i < m; i++)
		{
			cin >> u >> v;
			add(u, v), add(v, u);
		}
		dfs1(1, 0);
		dfs2(1, 1);
		build(1, 1, n);
		while (q--)
		{
			char c;
			cin >> c;
			if (c == 'I')
			{
				int u, v, w;
				cin >> u >> v >> w;
				mtre(u, v, w);
			}
			if (c == 'D')
			{
				int u, v, w;
				cin >> u >> v >> w;
				mtre(u, v, -w);
			}
			if (c == 'Q')
			{
				int p;
				cin >> p;
				cout << query(1, dfn[p]) << endl;
			}
		}
	}
}

本文地址:https://blog.csdn.net/yangzijiangac/article/details/107358398

相关标签: 数据结构