UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#206221#2646. sumone_zero_four_zero1001678ms25292kbC++112.8kb2024-07-21 15:17:442024-07-21 16:38:21

answer

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define mid(p) (((tree[p].itel) + (tree[p].iter)) >> 1)
#define len(p) (((tree[p].iter) - (tree[p].itel)) + 1)
using namespace std;

struct node{
    int itel, iter;
    int sum, tag;
};

int n, q, cid = 0;
int op, x;
int fa[300005];
vector<int> a[300005];
int val[300005];
int dfn[300005], out[300005];
node tree[1000006];

void erg(int u){
    dfn[u] = ++ cid;
    for (auto && i : a[u]){
        erg(i);
    }
    out[u] = cid;
    // cout << u << " " << dfn[u] << " " << out[u] << "\n";
}

void pushup(int p){
    tree[p].sum = tree[ls(p)].sum + tree[rs(p)].sum;
}

void pushdown(int p){
    if (!tree[p].tag) return;
    tree[ls(p)].sum = len(ls(p)) - tree[ls(p)].sum;
    tree[rs(p)].sum = len(rs(p)) - tree[rs(p)].sum;
    tree[ls(p)].tag ^= tree[p].tag;
    tree[rs(p)].tag ^= tree[p].tag;
    tree[p].tag = 0;
}

void build(int p, int l, int r){
    tree[p] = {l, r, 0, 0};
    if (l == r){
        tree[p].sum = val[l];
        // cout << l << " ;;; " << val[l] << "\n";
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    pushup(p);
}

void update(int p, int l, int r){
    // cout << p << " " << l << " " << r << "[]\n";
    if (l <= tree[p].itel && r >= tree[p].iter){
        // cout << p << " " << l << " " << r << "[]\n";
        int len = tree[p].iter - tree[p].itel + 1;
        tree[p].sum = len - tree[p].sum;
        tree[p].tag ^= 1;
        return;
    }
    pushdown(p);
    if (l <= mid(p)) update(ls(p), l, r);
    if (r >= mid(p) + 1) update(rs(p), l, r);
    pushup(p);
}

int query(int p, int l, int r){
    // cout << p << " " << l << " " << r << "[]\n";
    int res = 0;
    if (l <= tree[p].itel && r >= tree[p].iter){
        return tree[p].sum;
    }
    pushdown(p);
    if (l <= mid(p)) res += query(ls(p), l, r);
    if (r >= mid(p) + 1) res += query(rs(p), l, r);
    return res;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("../data.in","r",stdin);
    freopen("../data.out","w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    scanf("%d", &n);
    for (int i = 2; i <= n; i ++){
        scanf("%d", &fa[i]);
        a[fa[i]].push_back(i);
    }
    erg(1);
    for (int i = 1; i <= n; i ++){
        scanf("%d", &val[dfn[i]]);
    }
    scanf("%d", &q);
    build(1, 1, n);
    while (q --){
        scanf("%d %d", &op, &x);
        if (op == 1){
            printf("%d\n", query(1, dfn[x], out[x]));
        }else{
            update(1, dfn[x], out[x]);
        }
        // for (int i = 1; i <= n; i ++){
        //     cout << query(1, dfn[i], out[i]) << " ";
        // }
        // cout << "\n";
    }

    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 162ms
memory: 25088kb

input:

187361
1 1 2 1 3 4 1 3 7 9 2 5 13 8 11 6 13 4 2 12 17 15 21 13 5 9 20 12 4 20 20 22 33 14 33 32 24 9...

output:

3
2
3
0
8
1
0
0
0
0
3
0
0
15
2
1
0
0
5
0
0
0
2
7
0
1
1
1
1
6
3
0
1
1
2
1
6
0
1
10
16
1
1
0
4
1
14
0
...

result:

ok 92174 lines

Test #2:

score: 10
Accepted
time: 160ms
memory: 24952kb

input:

180975
1 2 3 1 4 1 1 7 6 2 9 9 3 3 11 8 2 6 10 3 4 15 13 24 3 11 9 28 1 28 21 28 33 29 17 15 22 8 39...

output:

0
0
1
0
0
0
0
1
5
3
0
2
1
1
1
1
0
2
1
1
1
6
31
3
1
1
3
1
0
0
0
1
1
1
1
0
0
1
27
0
1
1
1
1
0
3
68
0
1...

result:

ok 96855 lines

Test #3:

score: 10
Accepted
time: 182ms
memory: 25292kb

input:

197782
1 2 3 1 3 2 2 5 5 7 7 4 11 7 3 9 9 16 13 5 18 15 9 21 2 9 7 8 14 17 22 15 16 32 31 33 21 37 3...

output:

1
2
12
0
2
1
1
0
2
1
7
3
2
1
3
0
0
2
0
10
0
4
1
0
1
0
1
3
1
5
1
2
2
0
4
0
0
0
1
1
0
1
0
3
2
1
0
15
1...

result:

ok 94716 lines

Test #4:

score: 10
Accepted
time: 167ms
memory: 25236kb

input:

194589
1 1 1 2 2 3 2 3 5 5 5 6 6 12 3 10 16 8 18 14 12 15 10 11 1 10 15 3 27 6 22 2 32 1 23 15 20 7 ...

output:

1
1
2
2
1
0
3
4
2
4
2
5
0
1
0
0
1
1
0
0
0
2
0
1
0
2
1
1
3
1
1
1
34
0
1
2
1
1
2
2
0
5
1
0
1
0
3
2
1
0...

result:

ok 92131 lines

Test #5:

score: 10
Accepted
time: 176ms
memory: 25108kb

input:

188203
1 2 2 2 5 6 3 6 4 8 2 10 9 7 10 12 5 10 7 18 19 15 2 22 2 9 21 19 24 21 24 8 32 16 29 34 18 6...

output:

0
3
3
1
2
2
1
0
1
2
13
1
4
1
1
1
2
2
0
0
0
1
1
0
0
1
0
1
3
1
1
0
0
0
0
1
11
1
2
2
0
3
3
0
1
0
27
1
1...

result:

ok 97304 lines

Test #6:

score: 10
Accepted
time: 168ms
memory: 25044kb

input:

185010
1 2 2 2 4 1 3 4 4 3 11 12 4 11 10 13 4 1 12 7 13 15 21 19 1 10 2 14 8 10 25 27 15 19 21 16 17...

output:

1
2
0
2
2
1
0
1
3
2
0
12
1
0
0
3
3
0
0
4
0
0
0
0
1
1
0
1
2
0
0
4
1
2
1
1
0
4
1
4
13
1
0
1
1
1
1
1
2
...

result:

ok 93162 lines

Test #7:

score: 10
Accepted
time: 153ms
memory: 24972kb

input:

181817
1 1 3 3 3 3 3 2 3 1 9 2 12 2 10 14 11 11 15 9 6 15 17 9 25 11 27 22 28 29 25 14 31 31 35 34 1...

output:

22
1
3
1
1
1
5
1
3
0
3
1
0
1
1
1
0
6
3
0
1
1
0
1
0
2
2
4
2
1
0
0
0
1
0
3
1
0
0
1
0
1
1
2
1
0
0
12
2
...

result:

ok 90816 lines

Test #8:

score: 10
Accepted
time: 174ms
memory: 25252kb

input:

195431
1 1 1 3 1 5 4 6 3 4 5 6 2 11 2 16 17 13 6 20 14 15 14 20 23 10 6 25 25 14 27 20 31 3 19 17 14...

output:

1
1
1
0
0
0
1
5
2
2
3
1
0
0
11
0
1
0
1
0
0
1
8
2
1
0
1
2
1
3
0
0
2
1
0
1
0
1
0
1
21
3
2
4
6
2
1
0
1
...

result:

ok 96235 lines

Test #9:

score: 10
Accepted
time: 173ms
memory: 25184kb

input:

192238
1 2 1 3 5 1 4 4 2 9 3 8 10 1 2 1 7 5 9 2 8 16 10 17 22 11 14 5 9 3 28 7 14 15 33 35 13 16 1 3...

output:

4
1
3
1
1
1
1
0
1
53
11
3
0
1
0
1
0
3
0
0
0
0
0
3
0
3
0
3
1
1
1
1
1
1
1
1
3
0
0
0
0
0
0
1
1
1
73
1
1...

result:

ok 93875 lines

Test #10:

score: 10
Accepted
time: 163ms
memory: 25120kb

input:

189045
1 2 1 3 4 2 4 2 2 7 2 10 5 6 9 2 6 15 14 4 1 16 6 7 21 9 12 13 22 22 28 26 30 18 25 17 12 24 ...

output:

0
0
3
4
5
0
1
2
0
1
0
1
0
0
1
2
7
0
1
0
0
1
1
5
0
7
41
1
1
11
2
1
1
4
1
0
0
2
0
1
0
1
2
0
0
1
0
0
1
...

result:

ok 91766 lines