@[Imakf](/space/show?uid=47863) 资瓷
by МiсDZ @ 2018-08-19 18:32:46
滋滋
by sjttsts @ 2018-08-19 18:38:49
前排滋磁
by _FILARET_ @ 2018-08-19 18:50:33
@[kkksc03](/space/show?uid=1)
by andyli @ 2018-08-19 18:53:31
# [R9914665 评测详情](https://www.luogu.org/record/show?rid=9914665)
## 是这个，对吧？
# 提交了22次。。。
# 全错。。。
# ~~[看列表你就知道了。。。](https://www.luogu.org/recordnew/lists?uid=104048&pid=P3920&status=&sort=0)~~
## 随便点开一个就是。。。
# TLE！！！
by Happynewyear @ 2018-08-19 18:55:46
@[Imakf](/space/show?uid=47863) 这是这个人的代码
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
inline int read() //读入优化
{
char ch; int res=0;
while (ch = getchar(), ch < '0' || ch > '9');
res = ch - 48;
while (ch = getchar(), ch >= '0' && ch <= '9')
res = res * 10 + ch - 48;
return res;
}
const double alpha = 0.777666;
const int e = 1e5+5, mod = 1e9, inf = 0x3f3f3f3f, o = 4000006;
int test, n, r[e], fa[e], sze[e], son[e], num, next[e << 1];
int dist[e], head[e], go[e << 1], cost[e << 1];
long long ans = 0;
bool vis[e];
vector<int>anc[e], id[e], sons[e];
inline void add(int x, int y, int v) //建边
{
next[++num] = head[x];
head[x] = num;
go[num] = y;
cost[num] = v;
next[++num] = head[y];
head[y] = num;
go[num] = x;
cost[num] = v;
}
int unused[o], top, pool, rt_self[e], rt_fa[e];
//当 grav 为分治中心时
//rt_self[grav]表示存储 dist(i, grav) - ri 的 treap 的根结点
//设 grav 在点分树上的父亲为 f
//rt_fa[grav] 表示存储 dist(i, f) - ri 的根结点(非法情况)
struct node
{
int lc, rc, val, s, pos;
}a[o];
inline void reset(int &x, int v)
{
a[x].lc = a[x].rc = 0;
a[x].val = v;
a[x].s = 1;
a[x].pos = rand();
}
inline void update(int &x)
{
a[x].s = a[a[x].lc].s + a[a[x].rc].s + 1;
}
inline int new_node()
{
int res;
if (top > 0)
{
res = unused[top]; //将用过的并且删过的点的编号放入 unused
top--; //新建节点的时候可以再使用这些编号，可以省空间
}
else res = ++pool;
return res;
}
inline void del_node(int &u)
{
if (!u) return;
unused[++top] = u;
a[u].val = a[u].s = a[u].pos = 0;
if (a[u].lc) del_node(a[u].lc);
if (a[u].rc) del_node(a[u].rc);
u = 0;
}
inline void zig(int &u)
{
int v = a[u].lc;
a[u].lc = a[v].rc;
a[v].rc = u;
a[v].s = a[u].s;
update(u);
u = v;
}
inline void zag(int &u)
{
int v = a[u].rc;
a[u].rc = a[v].lc;
a[v].lc = u;
a[v].s = a[u].s;
update(u);
u = v;
}
inline void insert(int &u, int v)
{
if (!u)
{
u = new_node();
reset(u, v);
return;
}
a[u].s++;
if (v <= a[u].val)
{
insert(a[u].lc, v);
if (a[a[u].lc].pos < a[u].pos) zig(u);
}
else
{
insert(a[u].rc, v);
if (a[a[u].rc].pos < a[u].pos) zag(u);
}
}
inline int qrank(int u, int v)
{
if (!u) return 0;
if (v < a[u].val) return qrank(a[u].lc, v);
else return a[a[u].lc].s + 1 + qrank(a[u].rc, v);
}
inline int calc_grav(int &st) //求树的重心
{
static int qn, que[e];
que[qn = 1] = st;
fa[st] = 0;
for (int i = 1; i <= qn; i++)
{
int u = que[i];
sze[u] = 1;
son[u] = 0;
for (int j = head[u]; j; j = next[j])
{
int v = go[j];
if(!vis[v] || v == fa[u])continue;
fa[v] = u;
que[++qn] = v;
}
}
for (int i = qn; i >= 2; i--)
{
int u = que[i], v = fa[u];
sze[v] += sze[u];
if (sze[u] > son[v])
son[v] = sze[u];
}
int all = sze[st], grav = 0, min = inf;
for (int i = 1; i <= qn; i++)
{
int u = que[i];
if (all - sze[u] > son[u])
son[u] = all - sze[u];
if (son[u] < min)
{
min = son[u];
grav = u;
}
}
return grav;
}
inline int dac(int &st, int &par) //静态点分治，用于重建
{
static int qn, que[e];
int grav = calc_grav(st);
vis[grav] = false; // vis[] = false 表示当前这个点已经当过分治中心
que[qn = 1] = grav;
fa[grav] = 0;
dist[grav] = 0;
for (int i = 1; i <= qn; i++)
{
int u = que[i];
for (int j = head[u]; j; j = next[j])
{
int v = go[j];
if (!vis[v] || v == fa[u]) continue;
fa[v] = u;
dist[v] = dist[u] + cost[j];
que[++qn] = v;
}
}
for (int i = 1;i <= qn; i++)
{
int u = que[i];
id[u].push_back(grav);
//id[u][i] 表示 u 在点分树的所有祖先中(包括它自己)第 i 老的编号
anc[u].push_back(dist[u]); //anc[u][i] 就是 dist(u, id[u][i])
//id[u][i] 是 id[u][i+1] 点分树中的父亲，anc 同理
sons[grav].push_back(u); //sons[u] 存储在点分树中u的子树的所有节点
insert(rt_self[grav], dist[u] - r[u]); //所有情况
if (par != 0)
insert(rt_fa[grav], anc[u][anc[u].size() - 2] - r[u]); //非法情况
}
for (int i = head[grav]; i; i = next[i])
{
int v = go[i];
if (vis[v]) dac(v, grav);
}
}
inline void rebuild(int &u, int par) //重建点分树的某一子树
{
vector<int>tmpson = sons[u];
//要先把原来的 sons[u] 存了，因为下面 sons[v].clear
int notres = anc[par].size();
for (int i = 0; i < tmpson.size(); i++) //先把这棵子树部分的信息删了
{
int v = tmpson[i];
vis[v] = true;
sons[v].clear();
anc[v].resize(notres); //仅与子树的根结点的祖先们有关的信息还要留着
id[v].resize(notres);
del_node(rt_self[v]);
del_node(rt_fa[v]);
}
dac(u, par); //再将这棵子树中的所有点进行一次静态的点分治
}
inline void check(int &u)
{
for (int i = 0; i < anc[u].size(); i++)
{
insert(rt_self[id[u][i]], anc[u][i] - r[u]);
//所有祖先的 treap (包括它自己的)都要插入新结点
if (i != 0)
insert(rt_fa[id[u][i]], anc[u][i - 1] - r[u]);
}
for (int i = 0; i < anc[u].size() - 1; i++)
{
int sze_fa = a[rt_self[id[u][i]]].s;
int sze_son = a[rt_self[id[u][i + 1]]].s;
if (sze_fa <= 30)break;
if (sze_son > alpha * sze_fa) //过度不平衡，重建
{
rebuild(id[u][i], i == 0 ? 0 : id[u][i - 1]);
break;
}
}
}
inline int calc_ans(int &u, int &v, int &w)
{
int res = 0;
anc[u] = anc[v]; //当前结点的父亲的祖先也是它的祖先
id[u] = id[v]; //存储的信息先由它父亲得来
anc[u].push_back(-w); //和 += w 抵消
id[u].push_back(u);
for (int i = 0; i < anc[u].size(); i++)
{
anc[u][i] += w;
sons[id[u][i]].push_back(u);
res += qrank(rt_self[id[u][i]], r[u] - anc[u][i]);
//查询 r[u] - dist(u, id[u][i]) 的排名，即所有的情况
if (i != 0)
res -= qrank(rt_fa[id[u][i]], r[u] - anc[u][i - 1]);
//查询 r[u] - dist(u, id[u][i] 的父亲) 的排名，即非法情况
}
return res;
}
int main()
{
test = read();
n = read();
for (int i = 1; i <= n; i++)
{
int fa_i = read(), c = read();
r[i] = read();
fa_i ^= (ans % mod);
if(i == 1)
{
anc[i].push_back(0);
id[i].push_back(i);
sons[i].push_back(i);
insert(rt_self[i], -r[i]); //第一个结点 dist 为 0
puts("0");
continue;
}
add(fa_i, i, c);
ans += calc_ans(i, fa_i, c); //累加包含当前结点且满足条件的点对的个数
check(i); //往所有祖先结点和它的 treap 加入结点
//并检查是否存在过度不平衡现象
printf("%lld\n", ans);
}
return 0;
}
```
by Prurite @ 2018-08-19 18:55:55
# 然而并没有删。。。
```cpp
int notres = anc[par].size();
for (int i = 0; i < tmpson.size(); i++) //先把这棵子树部分的信息删了
{
int v = tmpson[i];
```
by Happynewyear @ 2018-08-19 18:56:57
# ~~连注释都没删。。。~~
by Happynewyear @ 2018-08-19 18:57:41
@[Imakf](/space/show?uid=47863) @[Happynewyear](/space/show?uid=87746)
# 这人代码和题解代码一模一样
```
正在比较文件 0.txt 和 1.TXT
FC: 找不到差异
```
怀疑他是想抄题解，然后发现题解有坑，然后就来卡评测机了
by Prurite @ 2018-08-19 19:00:12
## @[星烁晶熠辉](/space/show?uid=54160)
# 是的！
by Happynewyear @ 2018-08-19 19:02:51