「UTR 3」去月球 - trie树+栈 | Bill Yang's Blog

「UTR 3」去月球 - trie树+栈

题目大意

    Scape和Mythological交流了玩几何冲刺的经验之后,Mythological非常高兴,又推荐给Scape一款游戏To the moon。
    游戏中一位老人John的记忆被药物尘封,进行了解除尘封的仪式之后,Scape走入了他的记忆。
    John的记忆中有一个唤做River女孩的身影,有着数不尽的纸兔子,有一个沙包,一只鸭嘴兽玩偶,一座灯塔。Scape被深深的打动了。
    “我的鸭嘴兽和沙包又在哪里呢?” Scape这样想到,不禁幻想出Mythological决定给他送$n$份礼物,其中第$i$份的种类是$a_i$。这些礼物按顺序排成一行。
    她挑选礼物的方式很特别,她每次会选择两份种类相同的礼物,并且这对礼物满足它们之间没有尚未拿走的礼物,并将这对礼物拿走。
    现在Scape给出了若干次询问,每次询问如果他送给她的是区间$[L_i,R_i]$之间的礼物,那么她最多能拿走多少份礼物。

传送门


题目分析

官方题解

易证明,最终答案与消除顺序无关。
因此我们可以维护一个类似与栈的trie树。
从$now=0$开始建树,若$a[i]=a[now]$,返回父亲结点,否则前往$a[i]$对应的儿子结点(不存在就新建)。
不难发现,这样若出现消除一定会返回到消除前的结点。

如$123324441$,最终会到达深度为$3$的$1$处。
这样,答案即为$r-l+1-dist[l-1,r]$,$dist[x,y]$表示第$x$个操作所在结点与第$y$个操作所在结点在树上的距离。

预处理ST表,查询LCA,乱搞一波即可。


代码

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
#include "mythological.h"
#include<cstring>
#include<map>
using namespace std;
const int maxn=300005,K=20;
int p[maxn][K],pos[maxn],Depth[maxn];
map<int,int> child[maxn];
void init(int n,int,int a[],int) {
memset(p,-1,sizeof(p));
pos[0]=0;
int now=0;
for(int i=1; i<=n; i++) {
if(a[i]==a[now])now=p[now][0];
else {
if(!child[now].count(a[i]))p[child[now][a[i]]=i][0]=now;
now=child[now][a[i]];
}
pos[i]=now;
}
for(int i=1; i<=n; i++)Depth[i]=Depth[p[i][0]]+1;
for(int j=1; j<K; j++)
for(int i=1; i<=n; i++)
if(~p[i][j-1])p[i][j]=p[p[i][j-1]][j-1];
}
int LCA(int x,int y) {
if(Depth[x]<Depth[y])swap(x,y);
for(int i=K-1; i>=0; i--)
if(Depth[x]==Depth[y])break;
else if(Depth[x]-(1<<i)>=Depth[y])x=p[x][i];
if(x==y)return y;
for(int i=K-1; i>=0; i--)
if(~p[x][i]&&p[x][i]!=p[y][i]) {
x=p[x][i];
y=p[y][i];
}
return p[x][0];
}
int query(int l,int r) {
l--;
int x=pos[l],y=pos[r];
return r-l-(Depth[x]+Depth[y]-(Depth[LCA(x,y)]<<1));
}
本篇文章有用吗?有用还不快点击!
0%