Codeforces 380B Sereja and Tree(暴力）

题目链接：Codeforces 380B Sereja and Tree

题目大意：给出n和m，带表一个n层的树和m次操作，树的构建方式为题目中图所示，每个节点由（a，b）组成，a表示的是层数，b表示的是该节点为当前层中的第b个节点。另外，当b = 2^k时，该节点有两个孩子节点，否则只有一个孩子节点。操作分为两种，1：给出t，l，r, x，表示在第t层l~r节点上添加一个数x;2:给出a，b，要求计算节点（a，b）以及它所有的孩子节点中共有多少中数字（重复不算）。

解题思路：暴力。对于添加操作，可以在每一层用一个vector记录下所有的添加操作，只需记录l，r和x。每当出现需要查询时，只需由根节点向下，遍历每层的1操作，判断是否对其造成影响（注意去重）。 然后比如在i层的区间是[x,y]，到i+1层时可以计算的出[xx,yy]，没有必要一个一个去判断，那样肯定超时。xx = x + log2（x），yy = y + log2（y） + (是否为2^k?1:0)。但是如果一次一次去计算的话时间开销很大，TLE了，必须在提前记录下所有下标的关系。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <set>

using namespace std;
const int N = 7005;
const int M = 200000;

struct state {
	int l, r, val;
	state() {}
	state(int l, int r, int val) {
		this->l = l; this->r = r; this->val = val;
	}
};

int n, m, dl[M], dr[M];
vector<state> v[N];

int solve (int d, int x, int y) {
	set<int> ans;

	for (int i = d; i <= n; i++) {
		for (int j = 0; j < v[i].size(); j++) {
			state& c = v[i][j];
			if (c.l <= y && c.r >= x) ans.insert(c.val);
		}

		x = (dl[x] == -1 ? dr[x] : dl[x]);
		y = dr[y];
	}
	return ans.size();	
}

void init () {
	int cnt = 1, p = 3;
	memset(dl, -1, sizeof(dl));
	memset(dr, -1, sizeof(dr));
	dl[1] = 1; dr[1] = 2;
	for (int i = 2; i < M; i++) {
		if ((1<<cnt) == i) {
			cnt++;
			dl[i] = p++;
		}
		dr[i] = p++;
	}
}

int main () {
	init ();
	int order, d, x, y, val;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d", &order);
		if (order == 1) {
			scanf("%d%d%d%d", &d, &x, &y, &val);
			v[d].push_back(state(x, y, val));
		} else {
			scanf("%d%d", &d, &x);
			printf("%d\n", solve(d, x, x));
		}
	}
	return 0;
}

Codeforces 380B Sereja and Tree(暴力）

原文：http://blog.csdn.net/keshuai19940722/article/details/19019693