QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95660#4387. Static Query on Tree3360550356AC ✓373ms57380kbC++145.3kb2023-04-11 10:33:102023-04-11 10:33:12

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-11 10:33:12]
  • 评测
  • 测评结果:AC
  • 用时:373ms
  • 内存:57380kb
  • [2023-04-11 10:33:10]
  • 提交

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