当前位置: 首页 > news >正文

题解:P7126 [Ynoi2008] rdCcot

题意:很简单了,不再赘述。

做法:

考虑怎么数连通块,钦定一个代表元,因为这个东西是 \(C\) 邻域状物,跟深度有关,我们可以考虑一下 bfs 序,那么我们就以 bfs 序最小的元素为代表元。

然后我们就要考虑一个元素什么时候是代表元,接下来我们会证明,对于一个元素,如果点 \(u\) 不和 bfs 序小于他的点连边,那么他就是代表元。

首先我们需要先证明一个结论:考虑对于 \(bfn_{i}<bfn_j<bfn_k,(i,k),(j,k)\) 间有边,则 \((i,j)\) 间也有边。

考虑 \(d = lca(i,k)\),如果 \(j\)\(d\) 子树内,那么 \(dep_j\le dep_k\),所以 \(dis(i,k)\ge dis(i,j)\),那么有边;而若在子树外,因为 \(dep_i\le dep_k\),所以 \(dis(j,k)\ge dis(i,j)\),所以也有边。

接下来我们证明上面的东西,考虑如果现在有一条路径 \(u\rightarrow a_1\rightarrow a_2\rightarrow\cdots\rightarrow a_k\rightarrow v\)满足 \(bfn_u>bfn_v\),那么我们就可以按上面那个结论,把这个路径的 \(bfn\) 写出来,就等于每次我可以缩掉一个峰,一直缩就可以证明这个结论。

所以我们现在只需要求出来满足对于 \(i\),下标小于 \(i\) 且 bfs 序更小,与 \(i\) 有连边的下标最大的元素 \(l_i\),类似定义 \(r_i\),那么最后询问区间 \([L,R]\) 时,只需要算 \(l_i<L,r_i>R,L\le i\le R\) 的有多少个,这个可以扫描线,在 \(i\) 处对区间 \([l_i+1,i]\) 加一,在 \(r_i\) 处减一,询问单点查就可以。

那么怎么计算 \(l_i,r_i\) 呢?因为这个东西需要满足 \(dis(i,l_i)\le C\),所以我们考虑用淀粉质来做,然后按 bfn 序排序。我们维护一颗平衡树,这里我用的是 FHQ Treap,按照点的编号从小到大,然后在每一个节点上维护字数内距离当前分治中心最小距离是多少。在插入一个点的时候,先将编号小于和大于的两部分分裂,分别去找编号最大/最小的满足距离限制的点即可。

这个题有点卡常,一点卡常小技巧是,分治时如果扫到一个点距离分治中心大于 \(C\),那么就没有必要让剩下子树去计算 \(l_i,r_i\),显然是没有贡献的。

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e5 + 5;
int n, m, c, bfn[maxn / 2], tot, f[maxn / 2];
vector<int> e[maxn];
void bfs(int s) {queue<int> q;q.push(s);while(!q.empty()) {int u = q.front(); bfn[u] = ++tot; q.pop();for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == f[u])continue;f[v] = u, q.push(v);}}
}
int dis[maxn / 2], l[maxn / 2], r[maxn / 2];
mt19937 rnd(time(0));
struct node {int l, r, del, pos, res, v;node() {l = r = 0, del = rnd();res = 0, v = 0;}
} ;
struct Treap {node tr[maxn / 2];int tot, rt;	inline int newnode(int u) {tr[++tot] = node();tr[tot].pos = u, tr[tot].res = tr[tot].v = dis[u];return tot;}inline void pushup(int u) {tr[u].res = min(min(tr[tr[u].l].res, tr[tr[u].r].res), tr[u].v);}void split(int p, int &l, int &r, int k) {if(!p) {l = r = 0;return ;}if(tr[p].pos <= k) l = p, split(tr[p].r, tr[l].r, r, k);elser = p, split(tr[p].l, l, tr[r].l, k);pushup(p);}int mrg(int l, int r) {if(!l || !r)return l + r;int p;if(tr[l].del > tr[r].del) p = l, tr[l].r = mrg(tr[l].r, r);elsep = r, tr[r].l = mrg(l, tr[r].l);pushup(p);return p;}int query_getposl(int u, int lim) {//	cout << u << endl;if(tr[u].res > lim || !u) {// 		cout << u << endl;return 0;}if(tr[tr[u].r].res <= lim)return query_getposl(tr[u].r, lim);if(tr[u].v <= lim)return tr[u].pos;return query_getposl(tr[u].l, lim);}int query_getposr(int u, int lim) {if(tr[u].res > lim || !u)return n + 1;if(tr[tr[u].l].res <= lim)return query_getposr(tr[u].l, lim);if(tr[u].v <= lim)return tr[u].pos;return query_getposr(tr[u].r, lim);} inline void insert(int u) {int p = newnode(u), p1, p2;split(rt, p1, p2, u);int v1 = query_getposl(p1, c - dis[u]), v2 = query_getposr(p2, c - dis[u]);l[u] = max(l[u], v1);r[u] = min(r[u], v2);rt = mrg(mrg(p1, p), p2);}inline void clear() {rt = tot = 0;tr[0].res = 2e9;}
} tree;
int sz[maxn / 2], rt, all, mx;
bool vis[maxn / 2];
void getsz(int u, int fa) {sz[u] = 1; all++;
//	cout << u << endl;for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == fa || vis[v])continue;getsz(v, u);sz[u] += sz[v];}
}
void getrt(int u, int fa) {int res = all - sz[u];for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == fa || vis[v])continue;getrt(v, u);res = max(res, sz[v]);}if(res < mx)mx = res, rt = u;
}
int getroot(int u) {rt = all = 0, mx = 2e9;getsz(u, 0), getrt(u, 0);return rt;
}
bool cmp(int x, int y) {return bfn[x] < bfn[y];
}
vector<int> pos;
void add(int u, int fa) {if(dis[u] > c)return ;pos.push_back(u);for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == fa || vis[v])continue;dis[v] = dis[u] + 1;add(v, u);}
}
void solve(int u) {
//	cout << u << endl;vis[u] = 1; dis[u] = 0;pos.clear(), add(u, 0); tree.clear();sort(pos.begin(), pos.end(), cmp);for (int i = 0; i < pos.size(); i++)tree.insert(pos[i]);for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(vis[v])continue;solve(getroot(v));}
}
#define lowbit(x) (x & (-x))
struct Segtree {int tr[maxn / 2];inline void add(int x, int val) {while(x <= n)tr[x] += val, x += lowbit(x);}inline int query(int x) {int ans = 0;while(x)ans += tr[x], x -= lowbit(x);return ans;}inline int queryseg(int l, int r) {return query(r) - query(l - 1);}inline void addseg(int l, int r, int v) {add(l, v), add(r + 1, -v);}
} tree1;
int lq[maxn], rq[maxn], ans[maxn];
vector<int> post[maxn / 2], qry[maxn / 2];
inline int read() {int sum = 0; char c = getchar();while(!isdigit(c))c = getchar();while(isdigit(c))sum = sum * 10 + c - '0', c = getchar();return sum;
}
void write(int x) {if(x <= 9) {putchar(x + '0');return ;}write(x / 10);putchar(x % 10 + '0');
}
signed main() {n = read(), m = read(), c = read();for (int x, i = 2; i <= n; i++)x = read(), e[x].push_back(i), e[i].push_back(x);bfs(1);for (int i = 1; i <= n; i++)l[i] = 0, r[i] = n + 1;solve(getroot(1));for (int i = 1; i <= m; i++)lq[i] = read(), rq[i] = read(), qry[rq[i]].push_back(i);for (int i = 1; i <= n; i++)post[i].push_back(i), post[r[i]].push_back(-i);for (int i = 1; i <= n; i++) {for (int j = 0; j < post[i].size(); j++) {int id = post[i][j];if(id > 0)tree1.addseg(l[id] + 1, id, 1);elsetree1.addseg(l[-id] + 1, -id, -1);}for (int j = 0; j < qry[i].size(); j++)ans[qry[i][j]] = tree1.queryseg(1, lq[qry[i][j]]);}for (int i = 1; i <= m; i++)write(ans[i]), putchar('\n');return 0;
}
/*
9 6 5 
1 2 3 4 5 6 7 8
1 2
1 3
2 4 
3 9 
6 8
1 6
*/
http://www.hskmm.com/?act=detail&tid=21028

相关文章:

  • 个人微信机器人开发api接口
  • MyBatis技术详解:从入门到高效开发 - 详解
  • 解码数据结构队列
  • 解决升级 Windows 11 24H2 后 NAS 共享无法显示的问题
  • 【还未找到原题】宝石(GEM) - Harvey
  • 第八篇
  • C# AStar 算法 - 实际应用
  • nocobase 源码安装
  • 航司网站url后缀参数FECU分析
  • 子网掩码完全指南:从入门到精通
  • 微信群机器人API
  • 9月29号
  • 【CF19E】Fairy - Harvey
  • Python从入门到实战 (14):工具落地:用 PyInstaller 打包 Python 脚本为可执行文件 - 实践
  • Harmony实现流转开发之音乐播放器跨设备流转 - 实践
  • 软件工程中线性回归应用
  • 解决秒杀高并发的一些方案
  • 构建移动网关:Air780EPM用4G为WiFi和LAN设备供网
  • 9.29模拟赛总结
  • 多corner综合
  • 优化 if/else 的四种设计模式
  • Day11-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\oop\demo06
  • 牛客周赛 Round 111
  • OpenLayers地图交互 -- 章节十一:拖拽材料交互详解
  • 2025年人工智能与智能装备国际学术会议(AIIE 2025)
  • 通过IDOR实现权限提升导致未授权用户注入
  • APUE学习笔记之基础知识(一) - Invinc
  • Syslog日志集成搭建
  • 定义工业生产新范式!网易灵动发布全球首款全域智能无人装载机“灵载”
  • 国有银行人力资源数字化转型的合规突围与效能跃迁