QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#95660 | #4387. Static Query on Tree | 3360550356 | AC ✓ | 373ms | 57380kb | C++14 | 5.3kb | 2023-04-11 10:33:10 | 2023-04-11 10:33:12 |
Judging History
answer
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define db double
#define ls u<<1
#define rs u<<1|1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const int N = 2e5+100;
const int M = 2e6 + 10;
const int mod = 1e9+7;
const int INF=1e9;
const double PI=acos(-1);
const double eps=1e-10;
//线段树
struct node1{
int l,r;
int v1,v2;
int clear,lazy;
}tr[N<<2];
//链式前向星
struct node2{
int next,to;
}e[N<<2];
int head[N];
int idx;
void add(int u,int v){
idx++;
e[idx].to=v;
e[idx].next=head[u];
head[u]=idx;
}
//树链剖分第1次dfs
int s[N],fa[N],dep[N],son[N],v[N];
//子树节点数量 父节点 深度 重儿子
void dfs1(int x,int father)
{
s[x]=1;
// v[x]=1;
int maxsize=-1;
for(int i=head[x];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(to==father) continue;
fa[to]=x;
dep[to]=dep[x]+1;
dfs1(to,x);
s[x]+=s[to];
if(maxsize<s[to])
{
maxsize=s[to];
son[x]=to;
}
}
}
//树链剖分第2次dfs
int tim;
int dfn[N],top[N],w[N];
//时间戳 重链的根 权值根据时间戳排序
void dfs2(int u,int t) //第二遍搜索
{
dfn[u]=++tim;
top[u]=t;
// w[tim]=a[u]; //本题没有点权
if(!son[u])
{
return ;
}
dfs2(son[u],t);
for(int i=head[u];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(to==fa[u]||to==son[u]) continue;
dfs2(to,to);
}
}
//线段树
void build(int u,int l,int r){
tr[u]={l,r,0,0,0,0};
if(l==r)return;
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
//v1当区间"与"等于7时说明子树区间全部满足,直接加上区间长度结束递归
//v2当区间"或"小于7时说明子树区间已经不可能对答案有贡献,不继续向下递归
void push_up(int u){
tr[u].v1=tr[ls].v1&tr[rs].v1;
tr[u].v2=tr[ls].v2|tr[rs].v2;
}
void push_down(int u){
//clear()标记用于每次询问后把整颗线段树维护信息清空
if(tr[u].clear){
//clear向下传递以实现整棵树的清空
tr[ls].clear=tr[rs].clear=tr[u].clear;
tr[ls].v1=tr[rs].v1=0;
tr[ls].v2=tr[rs].v2=0;
tr[ls].lazy=tr[rs].lazy=0;
tr[u].clear=0;
}
if(tr[u].lazy){
tr[ls].v1|=tr[u].lazy;
tr[rs].v1|=tr[u].lazy;
tr[ls].v2|=tr[u].lazy;
tr[rs].v2|=tr[u].lazy;
tr[ls].lazy|=tr[u].lazy;
tr[rs].lazy|=tr[u].lazy;
tr[u].lazy=0;
}
}
//修改区间l,r,树形结构已经被我们树剖变成了线性的
void update(int u,int l,int r,int ty){
if(l<=tr[u].l&&r>=tr[u].r){
tr[u].v1|=ty; //只要是加上标记,都是用|或
tr[u].v2|=ty;
tr[u].lazy|=ty;
return;
}
push_down(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)update(ls,l,r,ty);
if(r>mid)update(rs,l,r,ty);
push_up(u);
}
int query(int u,int l,int r){
if(l<=tr[u].l&&r>=tr[u].r){
if(tr[u].v1>=7){
return tr[u].r-tr[u].l+1;
}
if(tr[u].l==tr[u].r){
return 0;
}
}
push_down(u);
int mid=tr[u].l+tr[u].r>>1;
int res=0;
//v2>=7代表子树中有可能还有满足条件的,否则不进入子树递归
//到这可以发现,引入&操作是为了记录有多少点满足含三种标记
//引入|操作是为了剪枝
if(l<=mid&&tr[ls].v2>=7){
res+=query(ls,l,r);
}
if(r>mid&&tr[rs].v2>=7){
res+=query(rs,l,r);
}
return res;
}
void update_path(int u,int v,int ty){
//树上lca思想
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
update(1,dfn[top[u]],dfn[u],ty);
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
update(1,dfn[v],dfn[u],ty);
}
void update_tree(int u,int ty){
update(1,dfn[u],dfn[u]+s[u]-1,ty);
}
void solve(){
int n,m;
cin>>n>>m;
//初始化
memset(head,-1,sizeof(head));
idx=0;
//这种树输入方式就保证了一定是个自顶向下的有向形式
for(int i=1;i<n;i++){
int x;
cin>>x;
add(x,i+1);
add(i+1,x);
}
dfs1(1,-1);
dfs2(1,1);
build(1,1,n);
while(m--){
int a,b,c;
cin>>a>>b>>c;
int x;
for(int i=1;i<=a;i++){
cin>>x;
update_path(1,x,1); //将A到根的路径标记1
}
for(int i=1;i<=b;i++){
cin>>x;
update_path(1,x,2); //将B到根的路径标记2
}
for(int i=1;i<=c;i++){
int x;
cin>>x;
update_tree(x,4); //将C的子树标记成4
}
//查询含三种标记的节点数量
cout<<query(1,1,n)<<endl;
//清空线段树的标记
tr[1].clear=1;
tr[1].v1=0;
tr[1].v2=0;
tr[1].lazy=0;
}
}
signed main() {
// std::ios::sync_with_stdio(false);
// std::cin.tie(0);
int T=1;
cin>>T;
while(T--) {
solve();
}
}
/**
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 373ms
memory: 57380kb
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