bzoj4564: [Haoi2016]地图 仙人掌的圆方树 莫队 分块
bzoj4564: [Haoi2016]地图
Description
一天rin来到了一个遥远的都市。这个都市有n个建筑，编号从1到n，其中市中心编号为1，这个都市有m条双向通
行的街道，每条街道连接着两个建筑，其中某些街道首尾相连连接成了一个环。rin通过长时间的走访，已经清楚
了这个都市的两个特点：1. 从市中心出发可以到达所有的建筑物。2. 任意一条街道最多存在与一个简单环中。令
rin心花怒放的是，每个建筑物都会有拉面售卖。拉面有很多不同的种类，但对于rin而言只有油腻程度的不同，因
此我们把油腻程度相同的拉面看做同一种拉面。由于不同建筑物的拉面的油腻程度可能不同，我们用一个正整数来
表示拉面的油腻程度。要知道，拉面可是rin的最爱，但是现在到了下班高峰期，都市的交通变得非常的堵塞。 ri
n只能通过没有被堵死的街道通行，去品尝所在建筑物的拉面。现在rin想知道，如果她正在编号为x的建筑物，那
么在从市中心到x的所有简单路径经过的街道都被堵死的情况下，rin可以品尝到的拉面中（注意没有出现的拉面是
不能算在里面的）：
- 油腻程度≤ y且品尝次数为奇数次的拉面有多少种？
- 油腻程度≤ 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
分析
可以走到的节点仙人掌的子树所有节点。
好像仙人掌子树dfs序有一些奇技淫巧来着？
不过我是直接上了圆方树。
剩下的转化为某个区间内小于某个权值的数中出现奇数/偶数次的数的个数。
可以用莫队+分块解决。
做法参见gty的二逼妹子序列
代码
码农题
#include<bits/stdc++.h>
const int N = 2e5 + 10, Bs = 320;
int ri() {
char c = getchar(); int x = 0, f = 1; for(;c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
for(;c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c; return x * f;
}
int a[N], in[N], id[N], b[N], out[N], ps[N], l[N], r[N], A[N], tot;
struct Edge {
int pr[N], to[N << 1], nx[N << 1], tp;
void add(int u, int v) {to[++tp] = v; nx[tp] = pr[u]; pr[u] = tp;}
void adds(int u, int v) {add(u, v); add(v, u);}
};
struct Round_Square_Tree {
Edge T; int tot;
void dfs(int u, int ff) {
in[u] = ++tot; ps[tot] = u;
for(int i = T.pr[u]; i; i = T.nx[i])
if(T.to[i] != ff) dfs(T.to[i], u);
out[u] = tot;
}
}rst;
struct Tarjan {
Edge G; int fa[N], dfn[N], low[N], st[N], tp, tm;
void dfs(int u, int ff) {
fa[u] = ff; dfn[u] = low[u] = ++tm; st[++tp] = u;
for(int i = G.pr[u], v; i; i = G.nx[i])
if((v = G.to[i]) != ff) {
if(!dfn[v]) {
dfs(v, u), low[u] = std::min(low[u], low[v]);
if(low[v] >= dfn[u])
for(rst.T.adds(u, ++tot); st[tp + 1] != v;)
rst.T.adds(st[tp--], tot);
}
else low[u] = std::min(low[u], dfn[v]);
}
}
}tar;
struct Block {
int cnt[Bs]; int odd, sum;
void Ins(int x, int p) {
sum -= cnt[x] ? 1 : 0; odd -= cnt[x] & 1;
sum += (cnt[x] += p) ? 1 : 0; odd += cnt[x] & 1;
}
};
struct Ask {bool t; int l, r, y, id;};
bool cmp(Ask a, Ask c) {
return b[a.l] == b[c.l] ? ((b[a.l] & 1) ? a.r < c.r : a.r > c.r) : b[a.l] < b[c.l];
}
struct MT {
Block b[Bs]; Ask q[N]; int n;
void Add(int x, int p) {
int v; if(!(v = a[ps[x]])) return ;
b[id[v]].Ins(v - l[id[v]], p);
}
int Query(int v, int t) {
int odd = 0, x = 1, sum = 0;
for(;r[x] <= v; ++x) odd += b[x].odd, !t ? sum += b[x].sum : 0;
for(int i = l[x];i <= v; ++i)
odd += b[x].cnt[i - l[x]] & 1, !t ? (sum += b[x].cnt[i - l[x]] ? 1 : 0) : 0;
return t ? odd : sum - odd;
}
void Work() {
std::sort(q + 1, q + n + 1, cmp);
int L = 1, R = 0;
for(int i = 1;i <= n; ++i) {
for(;R < q[i].r;) Add(++R, 1);
for(;L > q[i].l;) Add(--L, 1);
for(;L < q[i].l;) Add(L++, -1);
for(;R > q[i].r;) Add(R--, -1);
A[q[i].id] = Query(q[i].y, q[i].t);
}
}
}mt;
struct Init {
int c[N], nn, n, m, B, Q;
int F(int x) {
if(x < c[1]) return 0;
int L = 1, R = nn, m;
for(;L != R; c[m = L + R + 1 >> 1] <= x ? L = m : R = m - 1) ;
return L;
}
void Value_Init() {
tot = n = ri(); m = ri();
for(int i = 1;i <= n; ++i) c[i] = a[i] = ri();
std::sort(c + 1, c + n + 1);
nn = 1; for(int i = 2;i <= n; ++i) if(c[i] != c[i - 1]) c[++nn] = c[i];
for(int i = 1;i <= n; ++i) a[i] = F(a[i]);
B = sqrt(nn);
for(int i = 1;i <= nn; ++i) {
id[i] = (i - 1) / B + 1;
if(!l[id[i]]) l[id[i]] = i; r[id[i]] = i;
}
r[id[nn] + 1] = l[id[nn] + 1] = nn + 1;
}
void Tree_Init() {
for(;m--;) tar.G.adds(ri(), ri());
tar.dfs(1, 0); rst.dfs(1, 0);
B = sqrt(tot) + 1;
for(int i = 1;i <= tot; ++i) b[i] = (i - 1) / B + 1;
Q = ri();
for(int i = 1;i <= Q; ++i) {
int t = ri(), u = ri(), y = ri();
y = F(y); if(!y) continue;
mt.q[++mt.n] = (Ask) {t, in[u], out[u], y, i};
}
}
}pre;
int main() {
pre.Value_Init();
pre.Tree_Init();
mt.Work();
for(int i = 1;i <= pre.Q; ++i) printf("%d\n", A[i]);
return 0;
}