第 49 届 ICPC区域赛沈阳站——D. Dot Product Game · znzryb
## 思路讲解
### 交换一定使得逆序对数量奇偶性变化，循环移动一格可以看作交换len-1次
（长度为len的）向左（向右）循环移动一次可以看作交换len-1次
[第 49 届 ICPC区域赛沈阳站——D. Dot Product Game](/2026/01/09/20260109-8c962a9f)
```cpp
FOR(i, 1, N - 1) {
char ch;
ll l, r, d;
cin >> ch >> l >> r >> d;
ll len = r - l + 1;
// 向左循环移动一个可以看作交换len-1次，向左循环移动d次，就是交换d*(len-1)次
if (d != 0)
inva += (len-1)*d;
out();
}
```
然后如何比较快速的求出一个数组中的这个逆序对的奇偶性呢？其实也不难。
众所周知，排列成环，成的环，在环上向左循环移动一次以后就复位了。那么如果说有一个环，（以下说相等，是默认是奇偶性相等），那么逆序对就是N-1，有两个环，逆序对就是N-2。因此只需要知道环的数量即可，会比这个直接用这个树状数组求好写一点。
## AC代码
[https://qoj.ac/submission/1658154](https://qoj.ac/submission/1658154)
::: 源代码
```cpp
// by Gospel_rock
// title: D. Dot Product Game 补题
// timeLimit: 2000
// url: https://codeforces.com/gym/105578/problem/D
#include <array>
#include <bits/stdc++.h>
#include <vector>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)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 debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = (ll)1e9 + 7; // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;
ll fa[MAXN];
ll find(ll x) {
if (x == fa[x])
return x;
return fa[x] = find(fa[x]);
}
void merge(ll u, ll v) {
u = find(u), v = find(v);
fa[u] = v;
}
void Solve() {
cin >> N;
// vector<ll> A(N+5),B(N+5);
vector<array<ll, 2>> A(N + 5);
FOR(i, 1, N) { cin >> A[i][0]; }
FOR(i, 1, N) { cin >> A[i][1]; }
sort(A.begin() + 1, A.begin() + 1 + N);
FOR(i, 1, N) { fa[i] = i; }
FOR(i, 1, N) { merge(A[i][1], i); }
ll invb = 0;
// 直接计算需要多少次交换得到答案比较困难
// 其实这道题目没有那么复杂，我们先要知道轮换次数
FOR(i, 1, N) {
if (fa[i] == i) {
invb++;
}
}
invb = (N - invb) % 2;
// sort(A.begin()+1,A.begin()+1+N,[&](array<ll, 2> &a,array<ll, 2> &b){
// return a[1]<b[1];
// });
// FOR(i,1,N){
// fa[i]=i;
// }
// FOR(i,1,N){
// merge(A[i][0],i);
// }
ll inva = 0;
// FOR(i,1,N){
// if(fa[i]==i){
// inva++;
// }
// }
// inva=(N-inva)%2;
auto out = [&]() {
ll c = inva + invb;
c %= 2;
if (c) {
cout << "A";
} else {
cout << "B";
}
};
out();
FOR(i, 1, N - 1) {
char ch;
ll l, r, d;
cin >> ch >> l >> r >> d;
ll len = r - l + 1;
// 向左循环移动一个可以看作交换len-1次，向左循环移动d次，就是交换d*(len-1)次
if (d != 0)
inva += (len-1)*d;
out();
}
cout << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> lT;
while (lT--)
Solve();
return 0;
}
/*
*AC
*https://qoj.ac/submission/1658154
*
*/
```
:::
## 心路历程（WA，TLE，MLE……）