欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-03-22 20:33:41
题意 "题目链接" Sol 很神仙的题 我们考虑询问(a, b)(a是b的祖先),直接对b根号分治 如果b的出现次数$ \sqrt{n}$,显然这样的b最多只有$\sqrt{n}$个,也就是说在询问中最多会有$\sqrt{n}$个这样的b,那么我们可以对每个a,暴力统计,复杂度$n\sqrt{n}$ ......

题意

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;
}