「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，乱搞一波即可。

---

代码

#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));
}