YZOJ P3367 魔术帽游戏

时间限制：1000MS                       内存限制：262144KB

难度：$6.0$           出题人：zzx

• 题目描述

有 $n$ 顶外形相同的魔术帽和一个魔术球，每次游戏开始前，魔术帽会被倒扣放置排成一排，这些魔术帽从左到右依次编号为 $1, 2, \cdots , n$ 。

每一局游戏，魔术球会被放在其中一顶魔术帽底下，然后进行若干次交换，每次交换时可以选出两顶魔术帽，交换它们的位置。整个过程对于小朋友们而言都是可见的。交换结束后，小朋友们可以打开魔术帽，正确找到魔术球则游戏胜利。

为了进行多局游戏，现有一个长度为 $m$ 的操作序列 $(a_1,b_1), (a_2,b_2), \cdots ,(a_m,b_m)$，其中 $(a_i,b_i)$ 表示反转 $a_i$ 号和 $b_i$ 号魔术帽之间的魔术帽的顺序（如原来魔术帽从左到右为 $a,b,c,d,e,f,g$，则操作 $(3,6)$ 进行后顺序变为 $a,b,f,e,d,c,g$ 。之后，小朋友们会玩 $q$ 局游戏。其中，第 $j$ 轮游戏，魔术球会被放在 $x_j$ 号魔术帽下，然后进行操作序列中 $[l_j,r_j]$ 这个片段，即依次进行反转操作 $(a_{l_j},b_{l_j}),(a_{l_j+1},b_{l_j+1}), \cdots ,(a_{r_j},b_{r_j})$ 。请求出每次游戏反转操作结束时，魔术球位于在哪一顶魔术帽下。注意：这里的魔术帽编号始终是按照位置从左到右编号的，即每次交换魔术帽之后，所有魔术帽会按照从左到右的顺序重新编号为 $1,2,\cdots,n$ 。

• 输入格式

第一行有三个整数 $n,m,q$，其中 $n$ 代表魔术帽的数量，$m$ 代表操作序列的长度，$q$ 代表游戏次数。

接下来 $m$ 行，其中第 $i$ 行两个整数 $a_i,b_i$，表示操作序列的第 $i$ 项。接下来 $q$ 行，其中第 $j$ 行三个正整数 $x_j,l_j,r_j$，表示第 $j$ 局游戏。保证 $1 \leq a_i \leq b_i \leq n$，$1 \leq x_j \leq n$，$1 \leq l_j \leq r_j \leq m$ 。

• 输出格式

输出 $q$ 行，每行一个整数，第 $j$ 行的整数表示第 $j$ 局游戏的交换结束后，魔术球所在的魔术帽编号。

• 样例输入

• 样例输出

• 数据规模与约定

$10\%$：$n=2$ 。

$40\%$：$n \leq 15$ 。

$100\%$：$1 \leq n,m,q \leq 100,000$ 。

 

 

 

---

 

 

 

先不考虑交换区间的操作的话，可以做到线性复杂度处理。

首先考虑对所有的查询离线，然后分别把这个查询挂到操作区间的左端点和右端点。由于每次交换魔术帽之后，所有魔术帽会按照从左到右的顺序重新编号，所以我们对于每局游戏只需要记住球一开始放在哪一个魔术帽，结束时这个魔术帽在哪就行了。

扫过一遍操作序列，若是遇到一个点为一个查询的左端点，就记录下当前查询位置上的编号，遇到右端点时找到这个编号现在在哪一个位置，就是这个询问的答案了。

由于有翻转整个区间的操作，使用平衡树优化。

值得注意的是（会写 Splay 的可以走了orz），使用无旋 Treap 的时候，由于有区间操作，必须按照子树大小 split() ，所以在找某一节点的 order 时不能直接分治。其实只要在 PushUp() 的时候顺便记录一下每个节点的父节点，然后查询的时候不断往上跳，若这个点为它父亲节点的右儿子那么说明它的 order 加上左子树大小加 1。不要忘了 PushDown() 。