HAOI 2016 地图（仙人掌+DFS序+莫队+分块）

发表于 |
字数统计: 1,672字 | 阅读时长 ≈ 8min

[HAOI2016]地图

问题描述

一天rin来到了一个遥远的都市。这个都市有n个建筑，编号从1到n，其中市中心编号为1，这个都市有m条双向通行的街道，每条街道连接着两个建筑，其中某些街道首尾相连连接成了一个环。rin通过长时间的走访，已经清楚了这个都市的两个特点：

1.从市中心出发可以到达所有的建筑物。

2.任意一条街道最多存在与一个简单环中。

令rin心花怒放的是，每个建筑物都会有拉面售卖。拉面有很多不同的种类，但对于rin而言只有油腻程度的不同，因此我们把油腻程度相同的拉面看做同一种拉面。由于不同建筑物的拉面的油腻程度可能不同，我们用一个正整数来表示拉面的油腻程度。要知道，拉面可是rin的最爱，但是现在到了下班高峰期，都市的交通变得非常的堵塞。 rin只能通过没有被堵死的街道通行，去品尝所在建筑物的拉面。

现在rin想知道，如果她正在编号为x的建筑物，那么在从市中心到x的所有简单路径经过的街道都被堵死的情况下，rin可以品尝到的拉面中（注意没有出现的拉面是不能算在里面的）：

1.油腻程度≤ y且品尝次数为奇数次的拉面有多少种？

2.油腻程度≤ y且品尝次数为偶数次的拉面有多少种？

输入格式

第一行两个正整数n,m，含义如题所示第二行一共N个正整数，第i个数Ai表示第i个建筑物出售的拉面的油腻程度。

接下来M行，每行两个正整数x,y，表示在建筑物x,y之间有一条双向通行的街道。数据保证1<=x<y<=N

接下来一行一个正整数Q，表示询问个数。

接下来Q行每行三个非负整数ty,x,y,x表示询问的建筑物编号，y表示油腻程度的限制，ty=0时表示询问偶数，ty=1表示询问奇数。

N<=100000,M<=150000,Q<=100000,Ai<=10^6

输出格式

一共Q行，对于每个询问输出一个答案。

这题给了个仙人掌，但观察后发现，由于是有根的，因此可以直接利用圆方树的姿势处理，但不需要添加方点，直接跑Tarjan后转化成一个树上对子树的询问。

直接维护比较麻烦，我们考虑利用DFS序转化成序列上的问题，然后发现每次询问相当于问一个区间，因此考虑用莫队维护cnt值，同时用一个数据结构来维护每个权值出现了奇数次和偶数次的前缀和，由于莫队的原因，可以用修改$O(1)$，询问$O(\sqrt{n})$的分块前缀和来解决。

总时间复杂度仍然是$O(n\sqrt{n})$

代码：

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 1000005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
int n,m,q,A[N],MAX,Hash[N],Ans[N],H;
int TOT,LA[N],NE[N],ST[N],EN[N];
int tot,la[N],ne[N],en[N];
int dfn[N],low[N],VT,fa[N],id[N];
int In[N],Out[N],C[N],Cnt[N],VTT;
struct node{int ty,l,r,k,id;}K[N];
bool cmp(node a,node b)
{
	if(id[a.l]==id[b.l])return a.r<b.r;
	return id[a.l]<id[b.l];
}
namespace BLK
{
	int lp[N],rp[N],id[N],sum[N][2],cnt[N][2],S;
	void Build()
	{
		int i,j;S=sqrt(H);
		for(i=1;i<=H;i++)
		{
			id[i]=i/S+1;
			if(!lp[id[i]])lp[id[i]]=i;
			rp[id[i]]=i;
		}
	}
	void Ins(int x,int d,int ty)
	{
		cnt[x][ty]+=d;
		sum[id[x]][ty]+=d;
	}
	int GS(int x,int ty)
	{
		int i,ans=0;
		for(i=1;i<id[x];i++)ans+=sum[i][ty];
		for(i=lp[id[x]];i<=x;i++)ans+=cnt[i][ty];
		return ans;
	}
}
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void add(int x,int y)
{
	tot++;
	en[tot]=y;
	ne[tot]=la[x];
	la[x]=tot;
}
void Getcir(int x,int y)
{
	do{
		add(x,y);
		add(y,x);
		y=fa[y];
	}while(y!=x);
}
void Tarjan(int x)
{
	int i,y;
	dfn[x]=low[x]=++VT;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];if(y==fa[x])continue;
		if(!dfn[y])
		{
			fa[y]=x;Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else low[x]=min(low[x],dfn[y]);
		if(low[y]>dfn[x])add(x,y),add(y,x);
	}
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];if(dfn[y]<dfn[x])continue;
		if(fa[y]!=x)Getcir(x,y);
	}
}
void DFS(int x,int f)
{
	int i,y;
	In[x]=++VTT;
	C[VTT]=A[x];
	for(i=la[x];i;i=ne[i])
	{
		y=en[i];if(In[y])continue;
		DFS(y,x);
	}
	Out[x]=VTT;
}
void UD(int k,int ty)
{
	k=C[k];
	if(Cnt[k])BLK::Ins(k,-1,Cnt[k]&1);
	Cnt[k]+=ty;
	if(Cnt[k])BLK::Ins(k,1,Cnt[k]&1);
}
int main_main()
{
	int i,j,k,x,y,z,ty,S,L,R;
	_R(n);_R(m);S=sqrt(n);
	for(i=1;i<=n;i++)_R(A[i]),id[i]=i/S;
	for(i=1;i<=m;i++)
	{
		_R(x);_R(y);
		ADD(x,y);ADD(y,x);
	}
	Tarjan(1);DFS(1,0);
	for(i=1;i<=n;i++)Hash[i]=C[i];
	sort(Hash+1,Hash+n+1);
	H=unique(Hash+1,Hash+n+1)-Hash-1;
	for(i=1;i<=n;i++)C[i]=lower_bound(Hash+1,Hash+H+1,C[i])-Hash;
	_R(q);
	for(i=1;i<=q;i++)
	{
		_R(ty);_R(x);_R(y);
		z=lower_bound(Hash+1,Hash+H+1,y)-Hash;
		if(Hash[z]!=y)z--;
		K[i]=(node){ty,In[x],Out[x],z,i};
	}
	sort(K+1,K+q+1,cmp);
	L=1;R=0;BLK::Build();
	for(i=1;i<=q;i++)
	{
		while(R<K[i].r)UD(++R,1);
		while(R>K[i].r)UD(R--,-1);
		while(L<K[i].l)UD(L++,-1);
		while(L>K[i].l)UD(--L,1);
		Ans[K[i].id]=BLK::GS(K[i].k,K[i].ty);
	}
	for(i=1;i<=q;i++)printf("%d\n",Ans[i]);
}
const int main_stack=16;    
char my_stack[128<<20];    
int main() {    
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");    
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");    
  main_main();    
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");    
  return 0;    
}