QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#413568 | #4387. Static Query on Tree | mobbb | AC ✓ | 148ms | 41440kb | C++20 | 4.2kb | 2024-05-17 18:53:10 | 2024-05-17 18:53:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 7;
int n;
vector<int> e[N];
int in[N],ou[N],sz[N],hs[N],tot,fa[N],idx[N],top[N],dep[N];
// top 为重链头部节点
void dfs1(int u,int f){
sz[u] = 1;
hs[u] = -1;
fa[u] = f;
for (auto v : e[u]) if (v != f){
dep[v] = dep[u] + 1;
dfs1(v,u);
sz[u] += sz[v];
if (hs[u] == -1 || sz[v] > sz[hs[u]]){
hs[u] = v;
}
}
}
void dfs2(int u,int t){
top[u] = t;
in[u] = ++tot;
idx[tot] = u;
if (hs[u] != -1){
dfs2(hs[u],t);
}
for (auto v : e[u]) if(v != fa[u] && v != hs[u]){
dfs2(v,v);
}
ou[u] = tot;
}
struct tag{
int ta,tb,tc;
};
struct Node{
int a,b,ab,siz;
tag t;
}seg[N * 4];
void update(int id){
seg[id].a = seg[id * 2].a + seg[id * 2 + 1].a;
seg[id].b = seg[id * 2].b + seg[id * 2 + 1].b;
seg[id].ab = seg[id * 2].ab + seg[id * 2 + 1].ab;
}
void settag(int id,tag t){
if (t.tc){
seg[id].t.tc = 1;
seg[id].a = seg[id].b = seg[id].ab = seg[id].t.ta = seg[id].t.tb = 0;
}
if (t.ta){
seg[id].t.ta = 1;
seg[id].a = seg[id].siz;
seg[id].ab = seg[id].b;
}
if (t.tb){
seg[id].t.tb = 1;
seg[id].b = seg[id].siz;
seg[id].ab = seg[id].a;
}
}
void pushdown(int id){
if (seg[id].t.ta != 0 || seg[id].t.tb != 0 || seg[id].t.tc != 0 ){
settag(id * 2,seg[id].t);
settag(id * 2 + 1,seg[id].t);
seg[id].t = {0,0,0};
}
}
void build(int id,int l,int r){
seg[id].siz = r - l + 1;
seg[id].t = {0,0,0};
if (l == r){
seg[id].a = 0;
seg[id].b = 0;
seg[id].ab = 0;
return;
}
int mid = l + r >> 1;
build(id * 2,l,mid);
build(id * 2 + 1,mid + 1,r);
update(id);
}
void modify(int id,int l,int r,int ql,int qr,tag t){
if (l == ql && r == qr){
settag(id,t);
return;
}
pushdown(id);
int mid = l + r >> 1;
if (qr <= mid){
modify(id * 2,l,mid,ql,qr,t);
}else if (ql > mid){
modify(id * 2 + 1,mid + 1,r,ql,qr,t);
}else{
modify(id * 2,l,mid,ql,mid,t);
modify(id * 2 + 1,mid + 1,r,mid + 1,qr,t);
}
update(id);
}
int query(int id,int l,int r,int ql,int qr){
if (l == ql && r == qr){
return seg[id].ab;
}
pushdown(id);
int mid = l + r >> 1;
if (qr <= mid){
return query(id * 2,l,mid,ql,qr);
}else if (ql > mid){
return query(id * 2 + 1,mid + 1,r,ql,qr);
}else{
return (query(id * 2,l,mid,ql,mid) + query(id * 2 + 1,mid + 1,r,mid + 1,qr));
}
}
void modify(int u,tag w){
int v = 1;
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u,v);
modify(1,1,n,in[top[u]],in[u],w);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u,v);
modify(1,1,n,in[v],in[u],w);
}
void solve(){
int q;
cin >> n >> q;
tot = 0;
for (int i = 1;i <= n;i++){
e[i].clear();
}
for (int i = 2;i <= n;i++){
int f;cin >> f;
e[f].push_back(i);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
while (q--){
int a,b,c;
int ans = 0;
cin >> a >> b >> c;
for (int i = 1;i <= a;i++){
int u;
cin >> u;
modify(u,tag{1,0,0});
}
for (int i = 1;i <= b;i++){
int u;
cin >> u;
modify(u,tag{0,1,0});
}
for (int i = 1;i <= c;i++){
int u;
cin >> u;
ans += query(1,1,n,in[u],ou[u]);
modify(1,1,n,in[u],ou[u],tag{0,0,1});
}
cout << ans << "\n";
modify(1,1,n,in[1],ou[1],tag{0,0,1});
// for (int i = 1;i <= n;i++){
// cout << query(1,1,n,i,i) << " \n"[i == n];
// }
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 148ms
memory: 41440kb
input:
1 200000 18309 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
output:
102147 62590 87270 88880 7654 61542 62953 85022 55135 54125 70500 64356 25824 88300 42278 15336 18132 28734 90282 42889 28099 31311 96842 19959 34366 60205 78358 91142 56048 74688 86091 51979 94750 11989 89544 86860 56720 29534 52343 90031 79002 90293 94554 48340 65015 9181 15016 19884 49445 14181 6...
result:
ok 18309 numbers