社区讨论
关于一个2=0的问题
学术版参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo7k4mn1
- 此快照首次捕获于
- 2023/10/27 03:08 2 年前
- 此快照最后确认于
- 2023/10/27 03:08 2 年前
这是一个动态开点值域线段树(可能?
CPPint build()
{
v[id].emplace_back((SGT){0, 0, 0});
printf("<%d>\n",v[id].size()-1);
return (v[id].size() - 1);
}
CPPif (!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 条回复,欢迎继续交流。
正在加载回复...