bitset+DFS序+线段树 Codeforces633G Yash And Trees

传送门：​​点击打开链接​​

题意：给你一棵树，根节点为1

有2种操作，第一种是给u节点所在的子树的所有节点的权值+x

第二种是询问，假设v是子树u中的节点，有多少种质数满足av = p + m·k

其中p<m

思路：首先用DFS序，把树弄成线段树来表示，这种做法十分常见就不多讲了

因为m<=1000,我们用bitset保存av%m的值

每次对子树增加权值的时候，只需要修改懒惰标记，来记录增加的大小

然后直接把bitset利用位运算来完成循环移动就行了。

这道题只要能熟练运用bitset，对DFS序的线段树有一定的了解，应该是没很大问题的。

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;

const int MX = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int M = 1005;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

int n, m, Q;
int DL[MX], DR[MX], DFN;
int A[MX], B[MX], sum[MX << 2];
bitset<M>stu[MX << 2], temp, pr;
int Head[MX], erear;
struct Edge {
    int v, nxt;
} E[MX * 2];

void edge_init() {
    erear = 0;
    memset(Head, -1, sizeof(Head));
}
void edge_add(int u, int v) {
    E[erear].v = v;
    E[erear].nxt = Head[u];
    Head[u] = erear++;
}
bool prime_is(int x) {
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) return false;
    }
    return true;
}
void prime_init() {
    pr = 0;
    for(int i = 2; i < m; i++) {
        if(prime_is(i)) pr.set(i);
    }
}
void DFS(int u, int f) {
    DL[u] = ++DFN;
    B[DFN] = A[u];
    for(int i = Head[u]; ~i; i = E[i].nxt) {
        int v = E[i].v;
        if(v == f) continue;
        DFS(v, u);
    }
    DR[u] = DFN;
}
void push_up(int rt) {
    stu[rt] = stu[rt << 1] | stu[rt << 1 | 1];
}
void func_right(int rt, int x) {
    stu[rt] = (stu[rt] << x) | (stu[rt] >> (m - x));
}
void push_down(int rt) {
    if(sum[rt]) {
        sum[rt << 1] += sum[rt]; sum[rt << 1] %= m;
        sum[rt << 1 | 1] += sum[rt]; sum[rt << 1 | 1] %= m;
        func_right(rt << 1, sum[rt]);
        func_right(rt << 1 | 1, sum[rt]);
        sum[rt] = 0;
    }
}
void build(int l, int r, int rt) {
    sum[rt] = 0;
    if(l == r) {
        stu[rt].reset();
        stu[rt].set(B[l] % m);
        return;
    }
    int m = (l + r) >> 1;
    build(lson); build(rson);
    push_up(rt);
}
void add(int L, int R, int x, int l, int r, int rt) {
    if(L <= l && r <= R) {
        sum[rt] = (sum[rt] + x) % m;
        func_right(rt, x);
        return;
    }
    int m = (l + r) >> 1;
    push_down(rt);
    if(L <= m) add(L, R, x, lson);
    if(R > m) add(L, R, x, rson);
    push_up(rt);
}
bitset<M> query(int L, int R, int l, int r, int rt) {
    if(L <= l && r <= R) {
        return stu[rt];
    }
    int m = (l + r) >> 1;
    push_down(rt);
    bitset<M> ret;
    if(L <= m) ret |= query(L, R, lson);
    if(R > m) ret |= query(L, R, rson);
    return ret;
}

int main() {
    //FIN;
    while(~scanf("%d%d", &n, &m)) {
        DFN = 0;
        edge_init(); prime_init();
        for(int i = 1; i <= n; i++) {
            scanf("%d", &A[i]);
        }
        for(int i = 1; i <= n - 1; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            edge_add(u, v);
            edge_add(v, u);
        }
        DFS(1, -1);
        build(1, n, 1);

        scanf("%d", &Q);
        while(Q--) {
            int op, a, b;
            scanf("%d%d", &op, &a);
            if(op == 1) {
                scanf("%d", &b);
                add(DL[a], DR[a], b % m, 1, n, 1);
            } else {
                temp = query(DL[a], DR[a], 1, n, 1);
                printf("%d\n", (int)((temp & pr).count()));
            }
        }
    }
}