#P11807. [PA 2017] 抄作业

    ID: 13060 远端评测题 5000ms 1024MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>2017二分可持久化线段树哈希 hashingPA(波兰)

[PA 2017] 抄作业

题目背景

译自 PA 2017 R3T2。

TL=5~10s,ML=512MB。

「你抄就抄吧,但是稍微改改,别和我的一模一样就行。」

题目描述

mm 个长度为 nn 的非负整数序列。第 ii 个序列的第 jj 项为 ai,ja_{i,j}

给定 a1,1,a1,2,,a1,na_{1,1},a_{1,2},\cdots,a_{1,n}

对于 2im2\le i\le m,给定 pi,xip_i,x_i,表示:

  • 1jn\forall 1\le j\le n 满足 jpij\neq p_i,有 ai,j=ai1,ja_{i,j}=a_{i-1,j}
  • ai,pi=xia_{i,p_i}=x_i

将这 mm 个序列以字典序为第一关键字,编号为第二关键字排序,输出排序后的序列编号。

输入格式

第一行,两个正整数 n,mn,m

第二行,nn 个非负整数 a1,1,a1,2,,a1,na_{1,1},a_{1,2},\cdots,a_{1,n}

接下来 (m1)(m-1) 行,第 ii 行两个整数 pi+1,xi+1p_{i+1},x_{i+1}

输出格式

输出一行 mm 个正整数,第 ii 个数表示排名为 ii 的序列的编号。

5 8
4 2 1 7 3
3 6
1 2
2 5
5 5
1 5
1 4
1 5
3 4 5 1 2 7 6 8

提示

  • 1n5×1051\le n\le 5\times 10^5
  • 2m5×1052\le m\le 5\times 10^5
  • 0a1,i,xi1090\le a_{1,i},x_i\le 10^9
  • 1pin1\le p_i\le n