Codeforces Round 821 (Div. 2) C. Parity Shuffle Sorting （构造之全变成一样的）

给你一个数组 $a$ ，其中有 $n$ 个非负整数。你可以对它进行以下操作。

选择两个索引 $l$ 和 $r$ $(1\le l<r\le n)$。
如果 $a_l+a_r$ 是奇数，则进行 $a_r:=a_l$ 运算。如果 $a_l+a_r$ 是偶数，则执行 $a_l:=a_r$ .求最多有 $n$ 次操作的序列，使得 $a$ 不递减。可以证明这总是可能的。需要注意的是，你并不需要尽量减少运算次数。

当且仅当 $a_1\le a_2\le \dots \le a_n$ 时，数组 $a_1,a_2,\dots ,a_n$ 是非递减的。

输入
第一行包含一个整数 $t(1\le t\le 10^5)$ - 测试用例数。

每个测试用例由两行组成。每个测试用例的第一行包含一个整数 $n(1\le n\le 10^5)$ - 数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n(0\le a_i\le 10^9)$ - 数组本身。

保证所有测试用例中 $n$ 的总和不超过 $10^5$ 。

输出
对于每个测试用例，在第一行打印一个整数 $m(0\le m\le n)$，即操作次数。

然后打印 $m$ 行。每行必须包含两个整数 $l_i,r_i$ ，即在 $i-th$ 操作中选择的索引$(1\le l_i<r_i\le n)$。

如果有多个解，请打印任意一个。

---

不递增就是 $a_i<=a_{i+1}$ ，那么就可以取一个特殊情况让所有数都相等，这样就是简单的构造方法。

还需要处理奇偶数的问题。
并且注意读题，奇偶数是操作相反而不是不能操作，本人读题的时候就读了半句话发现题做不出来。

首先让 $a[1]$ 和 $a[n]$ 相等，如果两者相加是偶数，那么就是让 $a[1]=a[n]$，所以之后的目标就是让所有数都等于 $a[n]$，相加等于奇数时同理。

以相加为偶数为例，之后，如果中间的任何数和 $a[n]$ 相加等于奇数，那么就意味着要让 $a[r]=a[l]$ ，我们要让 $a[l]=a[n]$，但是题目要求 $l<r$，所以就输出 1 i，如果中间的任何数和a[n]相加等于偶数，就意味着要让 $a[l]=a[r]$，那么就让 $a[r]=a[n]$，就输出 i n。

---

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;

int a[N];

void solve(){
    int n;cin >> n;
    bool ok = 1;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        if(a[i] < a[i-1])ok = 0;
    }

    if(ok){
        cout << 0 << endl;
        return;
    }
    
    cout << n-1 << endl;
    cout << 1 << ' ' << n << endl;
    int x;
    if((a[1] + a[n]) % 2 == 0){
        x = a[n];
    }else x = a[1];

    for(int i = 2;i <= n-1;i++){
        if((x + a[i]) % 2 != 0)cout << 1 << " " << i << endl;
        else cout << i << " " << n << endl;
    }
}

int main(){
    int T;cin >> T;
    while(T--){
        solve();
    }
    return 0;
}
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