专栏首页数据结构与算法BZOJ3351: [ioi2009]Regions(根号分治)

BZOJ3351: [ioi2009]Regions(根号分治)

题意

题目链接

Sol

很神仙的题

我们考虑询问(a, b)(a是b的祖先),直接对b根号分治

如果b的出现次数\(< \sqrt{n}\),我们可以直接对每个b记录下与它有关的询问,这样每个询问至多扫\(\sqrt{n}\)个点即可知道答案,那么dfs的时候暴力统计答案即可,复杂度\(q\sqrt{n}\)

如果b的出现次数\(> \sqrt{n}\),显然这样的b最多只有\(\sqrt{n}\)个,也就是说在询问中最多会有\(\sqrt{n}\)个这样的b,那么我们可以对每个a,暴力统计,复杂度\(n\sqrt{n}\)

然后用天天爱跑步那题的差分技巧搞一下就行了

代码十分好写~

#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long 
#define LL long long 
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, R, Q, base;
vector<int> v[MAXN];
vector<Pair> a1[MAXN], a2[MAXN];
int r[MAXN], fa[MAXN], ti[MAXN], ha[MAXN], ans[MAXN];
void dfs1(int x) {
    for(auto &a : a1[r[x]]) ans[a.se] += ha[a.fi]; ha[r[x]]++;
    for(auto &to : v[x]) dfs1(to); ha[r[x]]--;
}
void dfs2(int x) {
    for(auto &b: a2[r[x]]) ans[b.se] -= ha[b.fi];
    for(auto &to: v[x]) dfs2(to);
    for(auto &b: a2[r[x]]) ans[b.se] += ha[b.fi];
    ha[r[x]]++;
}
signed main() {
//  Fin(9); Fout(b);
    N = read(); R = read(); Q = read(); base = sqrt(N);
    r[1] = read(); ti[r[1]]++;
    for(int i = 2; i <= N; i++) {
        int f = read(); r[i] = read();
        v[f].push_back(i);
        ti[r[i]]++;
    }
    for(int i = 1; i <= Q; i++) {
        int a = read(), b = read();
        if(ti[b] < base) {
            a1[b].push_back({a, i});
        } else {
            a2[a].push_back({b, i});
        }
    }
    dfs1(1);
    memset(ha, 0, sizeof(ha));
    dfs2(1);
    for(int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 集合的前N个元素

    集合的前N个元素:编一个程序,按递增次序生成集合M的最小的N个数,M的定义如下:     (1)数1属于M;     (2)如果X属于M,则Y=2*x+1和Z=...

    attack
  • 洛谷P1600 天天爱跑步(差分 LCA 桶)

    \(T_i = 1\):同样还是差分的思想,由于每个点 能对其产生的点的深度是相同的(假设为\(x\)),那么访问该点时记录下\(dep[x]\)的数量,将结束...

    attack
  • cf1028C. Rectangles(前缀和)

    呵呵哒,昨天cf半夜场,一道全场切的题,我没做出来。。不想找什么理由,不会做就是不会做。。

    attack
  • 集合的前N个元素

    集合的前N个元素:编一个程序,按递增次序生成集合M的最小的N个数,M的定义如下:     (1)数1属于M;     (2)如果X属于M,则Y=2*x+1和Z=...

    attack
  • 另一种阶乘问题

    大家都知道阶乘这个概念,举个简单的例子:5!=1*2*3*4*5.现在我们引入一种新的阶乘概念,将原来的每个数相乘变为i不大于n的所有奇数相乘例如:5!!=1*...

    书童小二
  • Android浏览器跨域数据窃取和Intent Scheme攻击

    我们接下来要介绍的这个漏洞,其影响了Android版本4.4以下的自带浏览器和一些其他特定的Android浏览器,它允许黑客读取sqlite格式的cookie数...

    FB客服
  • 13:图像模糊处理

    13:图像模糊处理 总时间限制: 1000ms 内存限制: 65536kB描述 给定n行m列的图像各像素点的灰度值,要求用如下方法对其进行模糊化处理: 1....

    attack
  • Java int 最大值 最小值

    从JDK1.0开始,Integer中就定义了MIN_VALUE和MAX-VALUE两个常量:

    week
  • POJ 3041 Asteroids(匈牙利算法)

           题意就是有一个地图,然后给你几个点的坐标标记为'x',然后你有一个武器,每次可以消灭一行或一列的'x',问最少需要几次能把所有的'x'消灭完。然后...

    Ch_Zaqdt
  • 查找算法总结及其算法实现(Python/Java)

    需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。

    后端技术漫谈

扫码关注云+社区

领取腾讯云代金券