题目大意：有一串数为$1\sim n(n\leqslant2\times10^5)$，$m(m\leqslant5\times10^4)$次询问，每次问交换位置为$l,r$的两个数后数列中逆序对的个数。
题解：发现交换位置为$l,r$的数后，逆序对的变化只和区间$(l,r)$内的数与$s_l,s_r$的大小关系有关，设$S_i$表示区间$(l,r)$中比$s_i$小的数，$B_i$表示区间$(l,r)$中比$s_i$大的数，$ans'=ans+S_r-B_r-S_l+B_l$。设$len=r-l-1$，$ans'=ans+S_r-(len-S_r)-S_l+(len-S_l)=ans+2(S_r-S_l)$。
考虑分块，设块大小为$S$，在块内排序，在边角处暴力，在整块处二分查找位置，询问的复杂度是$O(2S+\dfrac n S\log_2S)$；修改为二分处位置直接插入或删除，复杂度$O(4S)$，所以当$S$略大于$\sqrt n$时最优。（反正我懒得算，随便猜一个）
卡点：
1. 计算$2(S_r-S_l)$时使用了位运算，当$S_r-S_l$为负数时出锅
2. 最开始块大小设成了$512$，计算块时用了$2^8$
C++ Code：
#include#include #include #define maxn 200010const int BSZ = 1000, BNUM = maxn / BSZ + 10;int n, m;long long ans;int L[BNUM], R[BNUM], bel[maxn], s[maxn];std::vector V[BNUM];int query(int l, int r, int x) { if (l > r) return 0; const int lb = bel[l], rb = bel[r]; int res = 0; if (lb == rb) for (int i = l; i <= r; ++i) res += s[i] < x; else { for (int i = l; i <= R[lb]; ++i) res += s[i] < x; for (int i = lb + 1; i < rb; ++i) res += std::upper_bound(V[i].begin(), V[i].end(), x) - V[i].begin(); for (int i = L[rb]; i <= r; ++i) res += s[i] < x; } return res;}int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) V[bel[i] = i / BSZ + 1].push_back(s[i] = i); const int B = bel[n]; for (int i = 1; i <= B; ++i) { L[i] = (i - 1) * BSZ; R[i] = L[i] + BSZ - 1; } L[1] = 1, R[B] = n; while (m --> 0) { int l, r; scanf("%d%d", &l, &r); if (l == r) { printf("%lld\n", ans); continue; } if (l > r) std::swap(l, r); const int lb = bel[l], rb = bel[r]; ans += (query(l + 1, r - 1, s[r]) - query(l + 1, r - 1, s[l])) * 2; ans += (s[l] < s[r]) ? 1 : -1; printf("%lld\n", ans); if (lb != rb) { V[lb].erase(std::lower_bound(V[lb].begin(), V[lb].end(), s[l])); V[lb].insert(std::upper_bound(V[lb].begin(), V[lb].end(), s[r]), s[r]); V[rb].erase(std::lower_bound(V[rb].begin(), V[rb].end(), s[r])); V[rb].insert(std::upper_bound(V[rb].begin(), V[rb].end(), s[l]), s[l]); } std::swap(s[l], s[r]); } return 0;}