树上莫队算法

算法

欧拉序

\$1\ 2\ 3\ 4\ 4\ 5\ 5\ 6\ 6\ 3\ 7\ 7\ 2\ 1\$

相关证明

• 为什么出现两次的点不统计答案

• 为什么当\$lca(x,y) \not =x\$时需要从\$ed[x]\$开始遍历

代码

```#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
char buf[1 << 21], *p1 = buf, *p2 = buf;
using namespace std;
const int MAXN = 1e5 + 10;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, Q;
int belong[MAXN], block;
struct Query {
int l, r, ID, lca, ans;
bool operator < (const Query &rhs) const{
return belong[l] == belong[rhs.l] ? r < rhs.r : belong[l] < belong[rhs.l];
//    return belong[l] < belong[rhs.l];
}
}q[MAXN];
vector<int>v[MAXN];
int a[MAXN], date[MAXN];
void Discretization() {
sort(date + 1, date + N + 1);
int num = unique(date + 1, date + N + 1) - date - 1;
for(int i = 1; i <= N; i++) a[i] = lower_bound(date + 1, date + num + 1, a[i]) - date;
}
int deep[MAXN], top[MAXN], fa[MAXN], siz[MAXN], son[MAXN], st[MAXN], ed[MAXN], pot[MAXN], tot;
void dfs1(int x, int _fa) {
fa[x] = _fa; siz[x] = 1;
st[x] = ++ tot; pot[tot] = x;
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(deep[to]) continue;
deep[to] = deep[x] + 1;
dfs1(to, x);
siz[x] += siz[to];
if(siz[to] > siz[son[x]]) son[x] = to;
}
ed[x] = ++tot; pot[tot] = x;
}
void dfs2(int x, int topfa) {
top[x] = topfa;
if(!son[x]) return ;
dfs2(son[x], topfa);
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(top[to]) continue;
dfs2(to, to);
}
}
int GetLca(int x, int y) {
while(top[x] != top[y]) {
if(deep[top[x]] < deep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return deep[x] < deep[y] ? x : y;
}
for(int i = 1; i <= Q; i++) {
if(st[x] > st[y]) swap(x, y);
int _lca = GetLca(x, y);
q[i].ID = i;
if(_lca == x) q[i].l = st[x], q[i]. r = st[y];
else q[i].l = ed[x], q[i].r = st[y], q[i].lca = _lca;
}
}
int Ans, out[MAXN], used[MAXN], happen[MAXN];
if(++happen[x] == 1) Ans++;
}
void delet(int x) {
if(--happen[x] == 0) Ans--;
}
used[x] ? delet(a[x]) : add(a[x]); used[x] ^= 1;
}
void Mo() {
sort(q + 1, q + Q + 1);
int l = 1, r = 0, fuck = 0;
for(int i = 1; i <= Q; i++) {
while(l < q[i].l) Add(pot[l]), l++, fuck++;
while(l > q[i].l) l--, Add(pot[l]), fuck++;
while(r < q[i].r) r++, Add(pot[r]), fuck++;
while(r > q[i].r) Add(pot[r]), r--, fuck++;
q[i].ans = Ans;
}
for(int i = 1; i <= Q; i++) out[q[i].ID] = q[i].ans;
for(int i = 1; i <= Q; i++)
printf("%d\n", out[i]);
}
int main() {
//block = 1.5 * sqrt(2 * N) + 1;
//block = pow(N, 0.66666666666);
block = sqrt(N);
for(int i = 1; i <= N; i++) a[i] = date[i] = read();
for(int i = 1; i <= N * 2; i++) belong[i] = i / block + 1;
Discretization();
for(int i = 1; i <= N - 1; i++) {
v[x].push_back(y); v[y].push_back(x);
}
deep[1] = 1; dfs1(1, 0);
dfs2(1, 1);
/*    for(int i = 1; i <= N; i++)
for(int j = 1; j <= i - 1; j++)
printf("%d %d %d\n", i, j, GetLca(i, j));*/
Mo();
return 0;
}```

0 条评论

• BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

Description 一个无向连通图，顶点从1编号到N，边从1编号到M。  小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当...

• 2017.5.20欢(bei)乐(ju)赛解题报告

预计分数：100+20+50=first 实际分数：20+0+10=gg 水灾（sliker.cpp/c/pas） 1000MS  64MB 大雨应经下了几天雨...

• cf1037D. Valid BFS?(BFS?)

可以这样想，在BFS序中较早出现的一定是先访问的，所以把每个点连出去的边按出现的前后顺序排个序

• LeetCode 323. 无向图中连通分量的数目（并查集）

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。

• 挑战程序竞赛系列（23）：3.2折半枚举

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• 2017.5.20欢(bei)乐(ju)赛解题报告

预计分数：100+20+50=first 实际分数：20+0+10=gg 水灾（sliker.cpp/c/pas） 1000MS  64MB 大雨应经下了几天雨...

• BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

Description 一个无向连通图，顶点从1编号到N，边从1编号到M。  小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当...

• OpenCV图像处理专栏十 | 利用中值滤波进行去雾

这是OpenCV图像处理专栏的第十篇文章，介绍一种利用中值滤波来实现去雾的算法。这个方法发表于国内的一篇论文，链接我放附录了。

• 排序算法——一篇文章搞懂常用的排序算法

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记...