CF-1024-D. Quartet Swapping（四重交换）

思路讲解

那么注意到，在该操作过程中，一个数下标的的奇偶性是不会发生变化的。
还有一个比较隐秘的不变量就是偶数下标的反转数和奇数下标的反转数是相同的，因为每次交换相邻偶数下标时, 会迫不得己地同时交换奇数下标，反之亦然。

那么要用到我们观察出来的第二个性质，就是偶数下标的反转数和奇数下标的反转数是相同的，那么如果说偶数下标序列和奇数下标序列的逆序对数量的奇偶性不相同（逆序对数量其实也就是需交换操作数量，因为本道题目是只能相邻交换，相当于冒泡排序），那么就说明必须要牺牲一个不反转（或者有时是在有序的基础上，再多反转一个，反正无论是 $+1$ 还是 $-1$ 以后奇偶性一定就相同了）。

那么应该反转哪个最优呢？不难发现这样交换最优。

if((revOdd-revEven)%2!=0){
	swap(Ans[N],Ans[N-2]);
}

AC代码

https://codeforces.com/contest/2101/submission/319512581

源代码

// Problem: B. Quartet Swapping
// Contest: Codeforces - Codeforces Round 1024 (Div. 1)
// URL: https://codeforces.com/contest/2101/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN];
ll Ans[MAXN];
/*
交换ai和ai+2，交换ai+1和ai+3
输出通过该操作能够达到的字典序最小的数组
其实就是把两个数当成一块然后换个位置

那么注意到，在该操作过程中，一个数位置的奇偶性是不会发生变化的。
还有一个比较隐秘的不变量就是反转数的奇偶性，因为每次交换相邻偶数下标时, 会迫不得己地同时交换奇数下标。
然后呢，这个其实除了最后的3个位置，其实前面的位置按照奇偶性排序输出即可。

那么最后的问题。最后三个元素的位置是什么？那么其实就是要么就是一奇二偶，要么就是一偶二奇。
奇偶之间亦无需多言，那么就是偶偶奇奇之间如何判断的问题。
*/
struct BIT {  // 普通的单点修改区间查询树状数组，含有查找第K个空位的功能
  vector<ll> tr;
  int n;
  inline int lowbit(int x) { return x & (-x); }
  BIT(int ln) {  // 构造+初始化函数
    n = ln;
    tr.resize(n+5,0);
  }
  inline void add(int p, int x) {
  	if(p==0) return;
    while (p <= n) {
      tr[p] += x;
      p += lowbit(p);
    }
  }
  inline ll query(int l, int r) {
    ll lres = 0, rres = 0;
    l -= 1;
    while (l > 0) {
      lres += tr[l];
      l -= lowbit(l);
    }
    while (r > 0) {
      rres += tr[r];
      r -= lowbit(r);
    }
    return rres - lres;
  }
  inline int findKth(int k) {  // 找到第k个空位
    int cx = 0;
    for (int i = 1 << 20; i > 0; i >>= 1) {  // 这个你可以理解为不断缩小步长的搜索
      if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
        // lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
        k -= lowbit(cx + i) - tr[cx + i];
        cx += i;
      }
    }
    return cx + 1;  // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新空位出现的地方
  }
};
inline void solve(){
	cin>>N;
	priority_queue<ll,vector<ll>,greater<ll>> pqOdd,pqEven;
	BIT oddTree(N),evenTree(N);
	ll revOdd=0,revEven=0;
	FOR(i,1,N){
		cin>>A[i];
		if(i%2==0){
			pqEven.push(A[i]);
			revEven+=evenTree.query(A[i]+1,N);
			evenTree.add(A[i],1);
		}else{
			pqOdd.push(A[i]);
			revOdd+=oddTree.query(A[i]+1,N);
			oddTree.add(A[i],1);
		}
	}
	FOR(i,1,N){
		if(i%2==0){
			Ans[i]=pqEven.top();
			pqEven.pop();
		}else{
			Ans[i]=pqOdd.top();
			pqOdd.pop();
		}
	}
	if((revOdd-revEven)%2!=0){
		swap(Ans[N],Ans[N-2]);
	}
	FOR(i,1,N){
		cout<<Ans[i]<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2101/submission/319512581
*/

心路历程（WA，TLE，MLE……）