YZOJ P3367 魔术帽游戏

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() 。