4564: [Haoi2016]地图

4564: [Haoi2016]地图

Time Limit: 20 Sec   Memory Limit: 128 MB Submit: 124   Solved: 44 [ Submit][ Status][ Discuss]

Description

一天rin来到了一个遥远的都市。这个都市有n个建筑，编号从1到n，其中市中心编号为1，这个都市有m条双向通 行的街道，每条街道连接着两个建筑，其中某些街道首尾相连连接成了一个环。rin通过长时间的走访，已经清楚 了这个都市的两个特点：1. 从市中心出发可以到达所有的建筑物。2. 任意一条街道最多存在与一个简单环中。令 rin心花怒放的是，每个建筑物都会有拉面售卖。拉面有很多不同的种类，但对于rin而言只有油腻程度的不同，因 此我们把油腻程度相同的拉面看做同一种拉面。由于不同建筑物的拉面的油腻程度可能不同，我们用一个正整数来 表示拉面的油腻程度。要知道，拉面可是rin的最爱，但是现在到了下班高峰期，都市的交通变得非常的堵塞。 ri n只能通过没有被堵死的街道通行，去品尝所在建筑物的拉面。现在rin想知道，如果她正在编号为x的建筑物，那 么在从市中心到x的所有简单路径经过的街道都被堵死的情况下，rin可以品尝到的拉面中（注意没有出现的拉面是 不能算在里面的）： 1. 油腻程度≤ y且品尝次数为奇数次的拉面有多少种？ 2. 油腻程度≤ y且品尝次数为偶数次的拉面有多少种？

Input

第一行两个正整数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提示：请注意数据范围中 的<=，特殊条件中提到的??均为询问中的y，对于所有的数据，有y<=10^6

Output

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

Sample Input

10 12 1 10 4 5 2 10 1 8 4 8 1 2 1 3 1 4 2 5 4 6 4 7 7 8 2 9 8 10 1 6 8 10 4 7 10 0 3 9 1 7 6 0 5 2 1 10 9 0 5 7 1 7 4 0 7 3 1 2 7 0 3 4 0 3 8

Sample Output

0 1 0 1 0 1 0 2 0 0

HINT

Source

[ Submit][ Status][ Discuss]



首先询问是在一棵仙人掌上进行

对原图进行一次dfs，得到一棵dfs树

对于每个环，称环上的点中在dfs树里深度最小的那个点为该环的环根

考虑原问题的询问，有一个约束，是从1号点到x的所有简单路径都不能通过

那么，对于所有经过点x的环来说，除非x是该点环根，否则该环其它点对答案都没有贡献

因为可以从环根走到该点下面再走上来，或者环根直接走到这个点，这样环上的点就都作废了==

针对这个性质可以将原仙人掌重建

对于每个环，将环上除环根每个点的父亲指定为环根而删去原来指向父亲的边

对新树进行一次dfs，得到dfs序，这样是一个序列

每个询问就可以变成区间询问了。。莫队解决

维护权值的方案，用bzoj3809的分块方法即可

当然，构建新树不需要真的构建出，两边dfs配合tarjan就行了

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #include<bitset> #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int maxn = 1E5 + 10; const int N = 1E6 + 10; int n,m,sq1,sq2,dfs_clock,tot,cur,low[maxn],DFN[maxn],Name[maxn] ,dfn[maxn],s[maxn],a[maxn],siz[maxn],sum[1010][2],cnt[N],ans[maxn]; vector <int> v[maxn]; int Getpos (int x,int sq) { return (x % sq == 0)?x / sq:x / sq + 1; } struct Query{ int l,r,t,y,num; Query(){} Query(int l,int r,int t,int y,int num): l(l),r(r),t(t),y(y),num(num){} bool operator < (const Query &B) const { if (Getpos(l,sq1) < Getpos(B.l,sq1)) return 1; if (Getpos(l,sq1) > Getpos(B.l,sq1)) return 0; return r < B.r; } }Q[maxn]; void Dfs1(int x,int from) { DFN[x] = low[x] = ++dfs_clock; Name[DFN[x]] = x; for (int i = 0; i < v[x].size(); i++) { int to = v[x][i]; if (to == from) continue; if (!DFN[to]) { Dfs1(to,x); low[x] = min(low[x],low[to]); } else low[x] = min(low[x],DFN[to]); } } void Dfs2(int x,int from) { dfn[x] = ++dfs_clock; siz[x] = 1; for (int i = 0; i < v[x].size(); i++) { int to = v[x][i]; if (to == from) continue; if (!dfn[to] && low[to] >= DFN[x]) { Dfs2(to,x); siz[x] += siz[to]; } } for (int i = 0; i < v[x].size(); i++) { int to = v[x][i]; if (to == from) continue; if (!dfn[to] && low[to] < DFN[x]) { Dfs2(to,x); siz[Name[low[to]]] += siz[to]; } } } void Add(int x) { int pos = Getpos(x,sq2); if (cnt[x]&1) --sum[pos][1],++sum[pos][0]; else if (cnt[x]) --sum[pos][0],++sum[pos][1]; else ++sum[pos][1]; ++cnt[x]; } void Dec(int x) { int pos = Getpos(x,sq2); if (cnt[x] == 1) --sum[pos][1]; else if (cnt[x]&1) --sum[pos][1],++sum[pos][0]; else --sum[pos][0],++sum[pos][1]; --cnt[x]; } int getint() { char ch = getchar(); int ret = 0; while (ch < '0' || '9' < ch) ch = getchar(); while ('0' <= ch && ch <= '9') ret = ret*10 + ch - '0',ch = getchar(); return ret; } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif n = getint(); m = getint(); for (int i = 1; i <= n; i++) a[i] = getint(),cur = max(cur,a[i]); sq1 = sqrt(n); sq2 = sqrt(cur); while (m--) { int x = getint(),y = getint(); v[x].push_back(y); v[y].push_back(x); } Dfs1(1,0); dfs_clock = 0; Dfs2(1,0); for (int i = 1; i <= n; i++) s[dfn[i]] = a[i]; m = getint(); for (int i = 1; i <= m; i++) { int x,y,t = getint(); x = getint(); y = getint(); Q[i] = Query(dfn[x],dfn[x] + siz[x] - 1,t,y,i); } sort(Q + 1,Q + m + 1); int L = 1,R = 0; for (int i = 1; i <= m; i++) { while (R < Q[i].r) Add(s[++R]); while (L > Q[i].l) Add(s[--L]); while (R > Q[i].r) Dec(s[R--]); while (L < Q[i].l) Dec(s[L++]); int Ans = 0,po = Getpos(Q[i].y,sq2); for (int j = 1; j < po; j++) Ans += sum[j][Q[i].t]; for (int j = po*sq2 - sq2 + 1; j <= Q[i].y; j++) { if (!cnt[j]) continue; Ans += ((cnt[j]&1) == Q[i].t)?1:0; } ans[Q[i].num] = Ans; } for (int i = 1; i <= m; i++) printf("%d\n",ans[i]); return 0; }