题目背景
译自 PA 2017 R3T2。
TL=5~10s,ML=512MB。
「你抄就抄吧,但是稍微改改,别和我的一模一样就行。」
题目描述
有 m 个长度为 n 的非负整数序列。第 i 个序列的第 j 项为 ai,j。
给定 a1,1,a1,2,⋯,a1,n。
对于 2≤i≤m,给定 pi,xi,表示:
- ∀1≤j≤n 满足 j=pi,有 ai,j=ai−1,j;
- ai,pi=xi。
将这 m 个序列以字典序为第一关键字,编号为第二关键字排序,输出排序后的序列编号。
输入格式
第一行,两个正整数 n,m。
第二行,n 个非负整数 a1,1,a1,2,⋯,a1,n。
接下来 (m−1) 行,第 i 行两个整数 pi+1,xi+1。
输出格式
输出一行 m 个正整数,第 i 个数表示排名为 i 的序列的编号。
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
提示
- 1≤n≤5×105;
- 2≤m≤5×105;
- 0≤a1,i,xi≤109;
- 1≤pi≤n。