Codeforces Round 821 (Div. 2) C. Parity Shuffle Sorting （构造之全变成一样的）
给你一个数组 a a a ，其中有 n n n 个非负整数。你可以对它进行以下操作。
选择两个索引 l l l 和 r r r ( 1 ≤ l < r ≤ n ) ( 1≤l<r≤n ) (1≤l<r≤n)。
如果 a l + a r a_l+a_r al+ar 是奇数，则进行 a r : = a l a_r:=a_l ar:=al 运算。如果 a l + a r a_l+a_r al+ar 是偶数，则执行 a l : = a r a_l:=a_r al:=ar .求最多有 n n n 次操作的序列，使得 a a a 不递减。可以证明这总是可能的。需要注意的是，你并不需要尽量减少运算次数。
当且仅当 a 1 ≤ a 2 ≤ … ≤ a n a_1≤a_2≤…≤a_n a1≤a2≤…≤an 时，数组 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,…,an 是非递减的。
输入
第一行包含一个整数 t ( 1 ≤ t ≤ 1 0 5 ) t ( 1≤t≤10^5 ) t(1≤t≤105) - 测试用例数。
每个测试用例由两行组成。每个测试用例的第一行包含一个整数 n ( 1 ≤ n ≤ 1 0 5 ) n ( 1≤n≤10^5 ) n(1≤n≤105) - 数组的长度。
每个测试用例的第二行包含 n n n 个整数 a 1 , a 2 , … , a n ( 0 ≤ a i ≤ 1 0 9 ) a_1,a_2,…,a_n ( 0≤a_i≤10^9 ) a1,a2,…,an(0≤ai≤109) - 数组本身。
保证所有测试用例中 n n n 的总和不超过 1 0 5 10^5 105 。
输出
对于每个测试用例，在第一行打印一个整数 m ( 0 ≤ m ≤ n ) m ( 0≤m≤n ) m(0≤m≤n)，即操作次数。
然后打印 m m m 行。每行必须包含两个整数 l i , r i l_i,r_i li,ri ，即在 i − t h i -th i−th 操作中选择的索引 ( 1 ≤ l i < r i ≤ n ) ( 1≤l_i<r_i≤n ) (1≤li<ri≤n)。
如果有多个解，请打印任意一个。
不递增就是 a i < = a i + 1 a_i <= a_{i+1} ai<=ai+1 ，那么就可以取一个特殊情况让所有数都相等，这样就是简单的构造方法。
还需要处理奇偶数的问题。
并且注意读题，奇偶数是操作相反而不是不能操作，本人读题的时候就读了半句话发现题做不出来。
首先让 a [ 1 ] a[1] a[1] 和 a [ n ] a[n] a[n] 相等，如果两者相加是偶数，那么就是让 a [ 1 ] = a [ n ] a[1] = a[n] a[1]=a[n]，所以之后的目标就是让所有数都等于 a [ n ] a[n] a[n]，相加等于奇数时同理。
以相加为偶数为例，之后，如果中间的任何数和 a [ n ] a[n] a[n] 相加等于奇数，那么就意味着要让 a [ r ] = a [ l ] a[r] = a[l] a[r]=a[l] ，我们要让 a [ l ] = a [ n ] a[l] = a[n] a[l]=a[n]，但是题目要求 l < r l < r l<r，所以就输出 1 i，如果中间的任何数和a[n]相加等于偶数，就意味着要让 a [ l ] = a [ r ] a[l] = a[r] a[l]=a[r]，那么就让 a [ r ] = a [ n ] a[r] = a[n] 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;
}