题面

​ 小 B 忘记做作业了！昨天的作业是对 $n$ 个不同的数从小到大进行排序，然而小 B 作业本上的数依旧是乱序的。老师正在检查作业，还要检查 $m$ 个同学就要到达小 B 这里了，检查每个同学的时间都是 $t/m+10^{-100}$ 秒( $t$ 为本题时限)。

​ 小 B 知道，自己的作业如果做的太差，一定能得到和老师谈心的好机会。不过好在，老师已经把答案写在了黑板上,因此这时小 B 的作业可以看成一个长度为 $n$ 的排列 $a_1,a_2,\dots,a_n$ ，$a_i$ 表示小 B 作业中第 $i$ 位的数在 $n$ 个数中是第 $a_i$ 小。而且老师也公布了评分的标准：按字典序评分。也就是说对于两种排序方式，分别为 $p_1,p_2,…,p_n$ 和 $q_1,q_2,…,q_n$ ，设 $x_0 = min\{x|p_x ≠q_x\}$ ，那么第 $x_0$ 位较小的那个排序方式可以获得更高的分数。

​ 由于数字很多，抄已经来不及了。于是小 B 打算使用交换的方式，在老师检查到每个同学的时候，小 B 都会观察出一个区间 $[l,r]$ ，在这个区间内交换两个数不会被老师察觉。小 B 眼疾手快，他观察老师和交换两个数的用时总和是 $10^{-100}$秒。小 B 希望每一次交换，他都能选取交换后得分最高，即字典序最小的交换方式。然而他并不能在 $t$ 秒中找出答案，于是他向同桌的你求助，希望你能告诉他每一步该如何交换。

对于部分数据：
性质 A ：逆序对数小于等于 $100$ 。
性质 B ：排列和询问随机

思路

题目大意：给定一个排列，每次给定一个区间，交换区间内的两个数使得排列字典序最小，询问交换的位置，多次询问。

算法1

按照题意模拟，枚举交换位置并比较。时间复杂度 $O(mn²)$。期望得分 $20$ 分。

算法 2

不难发现给定区间之外的位置对每个询问的答案无影响，所以每次的问题就是取出一个子段，问这个子段怎样交换一次字典序最小。根据字典序定义，我们需要找到最小的位置满足通过交换可以使这个位置变小，也就是说这个位置不是后缀最小值，因此从后往前取最小值，找出可以变小的位置中最靠前的一个。最后与把这个位置与这个位置之后的最小值交换就是最优的了。时间复杂度 $O(mm)$ 。期望得分 $40－50$ 分。

算法3

对于性质 A 可以用 $\tt set$ 暴力找出这些逆序对。因为每次交换的时候一定会使逆序对减少，所以对于每个询问，枚举哪些逆序对在区间中，选择最优的交换，并更新减少的逆序对。时间复杂度 $O(n\log n+100m)$ 结合前面的算法，期望得分 $55－60$ 分。

算法 4

对于性质 B 可以发现每个区间第一个可以交换变优的位置会很靠前。直接暴力枚举前几位看一下是不是能交换，用线段树维护区间最小值。应该可以取得不错的效果。结合前面的算法，期望得分 $65-70$ 分。

正解

​ 问题在于如何求出第一个能变小的位置。可以找出这一段区间从开头开始的最长的连续上升段，那么交换的一定是连续上升段内和连续上升段后的数字。可以求出连续上升段之后的最小值，然后找到连续上升段中第一个比这个最小值大的位置，交换这两个位置就是最优的。
​ 求连续上升段可以为每个位置维护一个标记，表示这个位置是否比下一个位置大。使用线段树二分查找第一个有标记的位置就能找到最长连续上升段。线段树维护最小值很简单。最后查询连续上升段中比一个数大的最小位置，这个可以维护区间的最大值，同样二分查找即可。
​ 时间复杂度 $O(n\log n)$ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod = 1e9+7, N = 1e6+10;
struct Sgt {int l, r, len, mn, pos;} tr[N << 2];
int n, m, a[N];

inline void pushup(Sgt &fa, Sgt l, Sgt r) {
    if(l.r - l.l + 1 == l.len && a[r.l] > a[l.r])
        fa.len = l.len + r.len;
    else fa.len = l.len;
    if(l.mn < r.mn) fa.pos = l.pos, fa.mn = l.mn;
    else fa.pos = r.pos, fa.mn = r.mn;
    fa.l = l.l, fa.r = r.r;
}

inline void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if(l == r) {
        tr[u].mn = a[r];
        tr[u].len = 1;
        tr[u].pos = r;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int pos, int &x) {
    if(tr[u].l == pos && tr[u].r == pos) {
        tr[u].mn = x;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(pos <= mid) modify(u << 1, pos, x);
    else if(pos > mid) modify(u << 1 | 1, pos, x);
    pushup(u);
}

Sgt query(int u, int l, int r) {
    if(l <= tr[u].l && tr[u].r <= r) 
        return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    if(r <= mid) return query(u << 1, l, r);
    else if(l > mid) return query(u << 1 | 1, l, r);
    else {
        Sgt res;
        pushup(res, query(u << 1, l, r), query(u << 1 | 1, l, r));
        return res;
    }
}

int main() {
    freopen("swap.in", "r", stdin);
    freopen("swap.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    build(1, 1, n);
    int l, r;
    while(m --) {
        cin >> l >> r;
        Sgt sg = query(1, l, r);
        if(sg.mn != a[l]) {
            cout << l << ' ' << sg.pos << '\n';
            int t1 = a[l], t2 = a[sg.pos];
            swap(a[l], a[sg.pos]);
            modify(1, sg.pos, t1);
            modify(1, l, t2);
        } else {
            if(sg.len == r - l + 1)
                cout << "-1\n";
            else {
                int tl = min(r, l + sg.len);
                Sgt st = query(1, tl, r);
                int pos = upper_bound(a + l, a + tl, st.mn) - a;
                cout << pos << ' ' << st.pos << '\n';
                int t1 = a[st.pos], t2 = a[pos];
                swap(a[st.pos], a[pos]);
                modify(1, pos, t1);
                modify(1, st.pos, t2);
            }
        }
    }
    return 0;
}