C 题地址: 大小接近的点对 http://acm.zzuli.edu.cn/problem.php?id=2520
分析题目:
方法一:
在 dfs 序上, 树状数组维护每个数出现的次数; 因为在 dfs 序上根比它的子孙先遍历到 (遍历到根时, 还没加入遍历孩子)
题目要统计 u 是 v 的祖先时, dfs 序就保证了,"在遍历到的结点 x 是根, 而接下来遍历的都是它的子孙",
递归思想, 叶节点先计算完, 再向父亲更新, 父亲再像父亲更新贡献, 完事.
总结: dfs 序用来处理 根和它子树问题
很清楚的思想: dfs 序上作两次查询, 1 次统计遍历子树前, 1 次统计遍历子树后的贡献, 两者相减就是子树的贡献了
方法二: 主席树在 dfs 序的 入时间戳 和 出时间戳上 统计区间和, 思路没问题吧.
这里先放上方法一的做法, 方法二写的代码 wa 了, 但它肯定有被 ac 的那一天!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn = 1e5+10;
- ll a[maxn];
- ll sum[maxn],c[maxn];
- const int INF = 0x3f3f3f3f;
- vector<int> vec;
- vector<ll> g[maxn];
- int n;
- ll k;
- // 树状数组
- int lowbit(int x){
- return x & -x;
- }
- void add(int x, int v){
- while (x <maxn){
- c[x] += v;
- x += lowbit(x);
- }
- }
- int query(int x){
- if (x>= maxn)
- return 0;
- int res = 0;
- while (x)
- res += c[x], x -= lowbit(x);
- return res;
- }
- int rangeQuery(int l, int r){
- return query(r) - query(l - 1);
- }
- //dfs 序上 查询和更新树状数组
- void dfs(int x){
- int l = lower_bound(vec.begin(),vec.end(),a[x] - k ) - vec.begin(); // 找到左边界下标 ()
- int r = lower_bound(vec.begin(),vec.end(),a[x] + k ) - vec.begin(); // 找到右边界下标 ()
- if(r>= vec.size() || vec[r]> a[x] + k) --r; // 右边界没找到 规定为 vec 容器的最后一个值
- ll cnt1 = rangeQuery(l,r); // 先求出 dfs 子树前的贡献
- add(lower_bound(vec.begin(),vec.end(),a[x]) - vec.begin(),1); // 出现次数 + 1
- for(int v : g[x]){
- dfs(v);
- sum[x] += sum[v]; // 加上孩子们的贡献
- }
- ll cnt2 = rangeQuery(l,r); // 再求出 dfs 子树后的贡献
- sum[x] += cnt2 - cnt1; // 两者相减的差 就是子树的贡献了
- }
- int main(){
- scanf("%d %lld",&n,&k);
- for(int i=1;i<=n;i++){
- scanf("%lld",&a[i]);
- vec.push_back(a[i]);
- }
- // 离散化
- vec.push_back(-INF);
- sort(vec.begin(),vec.end());
- vec.erase(unique(vec.begin(),vec.end()),vec.end());
- for(int i=1;i<=n-1;i++){
- ll fa;
- scanf("%lld",&fa);
- g[fa].push_back(i+1);
- }
- dfs(1);
- for(int i=1;i<=n;i++) printf("%lld\n",sum[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3394405.html