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("%dn", solve(d, x, x));
}
}
return 0;
}

最后

以上就是风中路灯为你收集整理的Codeforces 380B Sereja and Tree(暴力）的全部内容，希望文章能够帮你解决Codeforces 380B Sereja and Tree(暴力）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。