【洛谷】题解 P3180 【[HAOI2016]地图】
程序员文章站
2022-05-09 13:50:31
...
首先询问是在一棵仙人掌上进行
对原图进行一次dfs,得到一棵dfs树
对于每个环,称环上的点中在dfs树里深度最小的那个点为该环的环根
考虑原问题的询问,有一个约束,是从1号点到x的所有简单路径都不能通过
那么,对于所有经过点x的环来说,除非x是该点环根,否则该环其它点对答案都没有贡献
因为可以从环根走到该点下面再走上来,或者环根直接走到这个点,这样环上的点就都作废了==
针对这个性质可以将原仙人掌重建
对于每个环,将环上除环根每个点的父亲指定为环根而删去原来指向父亲的边
对新树进行一次dfs,得到dfs序,这样是一个序列
每个询问就可以变成区间询问了。。莫队解决
维护权值的方案,用bzoj3809的分块方法即可
当然,构建新树不需要真的构建出,两边dfs配合tarjan就行了
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <bits/stdc++.h>
#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], a ns[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;
}
上一篇: IKanalyzer中文分词器