社区讨论

关于一个2=0的问题

学术版参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo7k4mn1
此快照首次捕获于
2023/10/27 03:08
2 年前
此快照最后确认于
2023/10/27 03:08
2 年前
查看原帖
这是一个动态开点值域线段树(可能?
CPP
int build()
{
	v[id].emplace_back((SGT){0, 0, 0});
	printf("<%d>\n",v[id].size()-1);
	return (v[id].size() - 1);
}
CPP
if (!v[id][p].lc) v[id][p].lc = build(); 	
insert(v[id][p].lc, l, mid, pos, val);
这一块的代码
build()返回的值是2
但是在insert前输出lc
lc的值为0
下面是完整代码
CPP
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define lfor(i, x, y) for (int i = (x); i <= (y); ++ i)
#define llfor(i, x, y) for (int i = (x); i < (y); ++ i)
#define rfor(i, x, y) for (int i = (x); i >= (y); -- i)
#define rlfor(i, x, y) for (int i = (x); i > (y); -- i)
#define For(p) for (int i = head[p]; i; i = nxt[i])
using namespace std;

const int N = 2e5 + 10;
const int INF = 1e9 + 10;
struct SGT
{
	int lc, rc;
	int dat;
};
vector<SGT> v[N];
vector<int> x[N];
int id;
map<int, int> val;

int build()
{
	v[id].emplace_back((SGT){0, 0, 0});
	printf("<%d>\n",v[id].size()-1);
	return (v[id].size() - 1);
}

void insert(int p, int l, int r, int pos, int val)
{
	printf("<%d> %d %d %d %d\n", p, l, r, pos, val);
	if (l == r) {v[id][p].dat += val; return;}
	int mid = (l + r) >> 1;
	if (pos <= mid) 
	{
		if (!v[id][p].lc) putchar('@'),v[id][p].lc = build(); 	
		printf("! %d %d\n", v[id][p].lc, v[id].size());
		insert(v[id][p].lc, l, mid, pos, val);
	}
	else 
	{
		puts("2");
		if (!v[id][p].rc) v[id][p].rc = build();
		insert(v[id][p].rc, mid + 1, r, pos, val);
	}
}

int ask(int p, int l, int r, int L, int R)
{
	if (L <= l && r <= R) return v[id][p].dat;
	int mid = (l + r) >> 1, ans = 0;
	if (L <= mid && v[id][p].lc) ans += ask(v[id][p].lc, l, mid, L, R);
	if (R > mid && v[id][p].rc) ans += ask(v[id][p].rc, mid + 1, r, L, R);	
	return  ans;
}

int main()
{
	int m, q; scanf("%d", &m);
	lfor (i, 1, m)
	{
		id = i; v[id].emplace_back((SGT){0, 0, 0});
		int n, root = build(); scanf("%d", &n); 
		lfor (j, 1, n) 
		{ 
			int a; scanf("%d", &a);
			x[id].emplace_back(a);
			insert(1, 1, INF, a, 1);
		}
	}
	scanf("%d", &q);
	lfor (i, 1, q)
	{
		int a, b, ans = 0; scanf("%d %d", &a, &b); id = a;
		llfor (j, 0, x[b].size()) ans += ask(1, 1, INF, 1, x[b][j]);
		printf("%d\n", ans);
	}
 	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...