标签存档：数据结构

传送门
比赛的时候就很慢很慢地搞出前三题……然后rating加了5，囧
记一下自己犯圡的地方好了。
258A
不说了。
258B
一开始看错题了，但是数位dp的部分还是写得很快的。后来发现看错题以后，感觉后面那部分很难算，用dp写了很久(组合计数也太不熟练了)，总算pass了。
值得记录的一点是即使是分类相同的项里面取，也应该看成有顺序的，最后再乘6!这样的算法比较科学。
实际上最后那一部分10^7的dfs就可以了。对数据范围不够敏感……作为一个ACMer，能暴力就暴力是基本原则。

#include 
#include 
#include 
#include 
#include 
#include 
#include 

258C
直接枚举约数然后每个容斥统计。一开始觉得复杂度有点悬，好像是$$O(n\sqrt{n} \log n)$$的，但是突然就想起来[1,n]之间的约数个数应当是$$O(n\log n)$$级别的(参见筛法)，所以整个算法应该是$$O(n\sqrt{n} + n \log^2 n)$$的

#include 
#include 
#include 
#include 
#include 
#include 
#include 

258D
这种算数目的数学期望题……
其实就利用概率论与数理统计之前学到的那个将$$E(x)$$分解为若干个$$E(x_i)$$之和，然后分别算期望，叠加起来就好了。
这些随机变量$$x_i$$之间有关无关都是没有关系的。
至于为什么能这么搞，那是因为E(x)本来计算公式就是线性的……

#include 
#include 
#include 
#include 
#include 
#include 
#include 

258E
对这种不要求在线算法的情况，设计一个合理的计算顺序是至关重要，离线算法相对于在线算法的一个很大的优势就在于计算顺序可以按自己调。
这里也不例外。
首先将子树转化为dfs序中连续一段已经是很old的技巧了，然后按dfs序列从左往右扫，每个询问就只进栈两次再出栈两次。
这样只要用线段树统计出目前被覆盖的点的数目就可以了。这个统计的方法类似于用线段树求矩形并的面积。
具体方法就是记录当前区间的最小值以及这个最小值的数目就可以轻松统计出来了。

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 100005;
int n, m, ot;
int st[N], ed[N];
int order[N];
vector  E[N];

void dfs(int x, int fa) {
	order[++ot] = x;
	st[x] = ot;
	for (vector ::iterator it = E[x].begin(); it != E[x].end(); it++) {
		if (*it != fa) {
			dfs(*it, x);
		}
	}
	ed[x] = ot;
}

	struct Node {
		int l, r, minv, num, d;
		Node *lc, *rc;
		Node(){}
		Node(int l, int r):l(l), r(r) { num = r - l + 1; minv = d = 0; lc = rc = NULL; }
		bool fit(int _l, int _r) { return _l <= l && r <= _r; }
		void pushdown() {
			if (d) {
				minv += d;
				if (lc) {
					lc->d += d;
					rc->d += d;
				}
				d = 0;
			}
		}

		void update() {
			if (lc) {
				minv = min(lc->minv + lc->d, rc->minv + rc->d);
				num = 0;
				if (lc->minv + lc->d == minv) num += lc->num;
				if (rc->minv + rc->d == minv) num += rc->num;
			}
		}
	}tr[N << 2], *root = &tr[1];

	void build(int p, int l, int r) {
		tr[p] = Node(l, r);
		int mid = (l + r) / 2;
		if (l != r) {
			tr[p].lc = &tr[p * 2];
			tr[p].rc = &tr[p * 2 + 1];
			build(p * 2, l, mid);
			build(p * 2 + 1, mid + 1, r);
		}
	}

	void add(Node *p, int l, int r, int x) {
		p->pushdown();
		if (p->fit(l, r)) {
			p->d += x;
		} else {
			int mid = (p->l + p->r) / 2;
			if (l <= mid) add(p->lc, l, r, x);
			if (r >  mid) add(p->rc, l, r, x);
			p->update();
		}
	}

int a[N], b[N];
int ans[N];
vector  in[N], out[N];

int main() {
	scanf("%d%d", &n, &m);
	for (int x, y, i = 1; i < n; i++) {
		scanf("%d%d", &x, &y);
		E[x].push_back(y);
		E[y].push_back(x);
	}
	dfs(1, 0);
	build(1, 1, n);
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a[i], &b[i]);
		in[st[a[i]]].push_back(i);
		in[st[b[i]]].push_back(i);
		out[ed[a[i]]].push_back(i);
		out[ed[b[i]]].push_back(i);
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		vector ::iterator it;
		for (it = in[i].begin(); it != in[i].end(); it++) {
			add(root, st[a[*it]], ed[a[*it]], 1);
			add(root, st[b[*it]], ed[b[*it]], 1);
			cnt++;
		}
		ans[order[i]] = root->minv + root->d ? n - 1 : n - root->num - !!cnt ;
		for (it = out[i].begin(); it != out[i].end(); it++) {
			add(root, st[a[*it]], ed[a[*it]], -1);
			add(root, st[b[*it]], ed[b[*it]], -1);
			cnt--;
		}
	}
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}