CF570D Tree Requests

离线 + 树状数组

如果子树中的一个深度的所有点中有两个以上的字母出现了奇数次，那么这个询问的答案就是$No$，其他的情况吧都是$Yes$。

由于只有$26$个字母，我们可以考虑暴力检验，把树映射到$dfs$序上然后看一看子树区间中每一个字母出现了多少次。

我先写了一个动态开点的线段树，然后$O(26 * (n + q)logn)$完美爆炸了。

然后我们发现一个深度的所有点是可以相互利用的，这样子只要堆所有的询问离线一下按照深度排个序就好了，开$26$个树状数组单点修改+ 区间求和就做完了。

感觉速度飞快。

时间复杂度$O(nlogn + 26 * qlogn)$。

Code：

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

const int N = 5e5 + ;

const int M = ;

int n, qn, tot = , head[N];

int dfsc = , dep[N], id[N], siz[N];

char let[N];

vector <int> vec[N];

struct Edge {

    int to, nxt;

} e[N << ];

inline void add(int from, int to) {

    e[++tot].to = to;

    e[tot].nxt = head[from];

    head[from] = tot;

}

struct Querys {

    int x, h, res, id;

    friend bool operator < (const Querys &u, const Querys &v) {

        return u.h < v.h;

    }

} q[N];

inline void read(int &X) {

    X = ; char ch = ; int op = ;

    for(; ch > ''|| ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

bool cmp(int x, int y) {

    return dep[x] < dep[y];

}

inline void chkMax(int &x, int y) {

    if(y > x) x = y;

}

void dfs(int x, int fat, int depth) {

    dep[x] = depth, id[x] = ++dfsc, siz[x] = ;

    for(int i = head[x]; i; i = e[i].nxt) {

        int y = e[i].to;

        if(y == fat) continue;

        dfs(y, x, depth + );

        siz[x] += siz[y];

    }

}

namespace Bit {

    int s[M][N];

    #define lowbit(p) (p & (-p))

    inline void modify(int t, int p, int v) {

        for(; p <= n; p += lowbit(p))

            s[t][p] += v;

    }

    inline int query(int t, int p) {

        int res = ;

        for(; p > ; p -= lowbit(p))

            res += s[t][p];

        return res;

    }

} using namespace Bit;

int main() {

//    freopen("Sample.txt", "r", stdin);

//    freopen("my.out", "w", stdout);

    read(n), read(qn);

    for(int fat, i = ; i <= n; i++) {

        read(fat);

        add(fat, i), add(i, fat);

    }

    dfs(, , );

    int maxd = ;

    for(int i = ; i <= n; i++) {

        chkMax(maxd, dep[i]);

        vec[dep[i]].push_back(i);

    }

    scanf("%s", let + );

    for(int i = ; i <= qn; i++) {

        q[i].res = , q[i].id = i;

        read(q[i].x), read(q[i].h);

    }

    sort(q + , q +  + qn);

    for(int i = ; i <= qn; i++) {

        int lst = i;

        for(; q[i].h == q[lst].h; i++);

        i--;

        if(q[i].h > maxd) continue;

        int vecSiz = vec[q[i].h].size();

        for(int j = ; j < vecSiz; j++) {

            int pos = vec[q[i].h][j];

            modify(let[pos] - 'a', id[pos], );

        }

        for(int j = lst; j <= i; j++)

            for(int c = ; c < ; c++) {

                int tmp = query(c, id[q[j].x] + siz[q[j].x] - ) - query(c, id[q[j].x] - );

                if(tmp & ) ++q[q[j].id].res;

            }

        for(int j = ; j < vecSiz; j++) {

            int pos = vec[q[i].h][j];

            modify(let[pos] - 'a', id[pos], -);

        }

    }

/*    for(int i = 1; i <= qn; i++)

        printf("%d ", q[i].res);

    printf("\n");   */

    for(int i = ; i <= qn; i++)

        if(q[i].res <= ) puts("Yes");

        else puts("No");

    return ;

}

巴特西

CF570D Tree Requests

最新文章

热门文章