用线段树或分块对每个区间维护以下信息即可:

  • 区间反转的 lazytag;
  • 区间内 1\tt 1 的个数。
  • 区间内逆序对的个数。

当反转区间 II 时,设其长度为 ss,后两个标记的值分别为 x,yx,y

  • xsxx' \gets s-x
  • $y' \gets \dfrac{1}{2}s(s-1)-\dfrac{1}{2}x(x-1)-\dfrac{1}{2}(s-x)(s-x-1)-y$。
    • 12s(s1)\dfrac{1}{2}s(s-1) 为总二元组个数。
    • 12x(x1)\dfrac{1}{2}x(x-1) 为反转前的 (1,1)(\tt 1,\tt 1) 二元组个数,反转后变为 (0,0)(\tt 0,\tt 0)
    • 12(sx)(sx1)\dfrac{1}{2}(s-x)(s-x-1) 为反转前的 (0,0)(\tt 0,\tt 0) 二元组个数,反转后变为 (1,1)(\tt 1,\tt 1)
    • yy 为反转前的 (1,0)(\tt 1,\tt 0) 二元组个数,反转后变为 (0,1)(\tt 0,\tt 1)
    • 从总数中减去上面三种不合法情况后,剩下的 yy' 就是合法情况。它表示反转前 (0,1)(\tt 0,\tt 1) 二元组个数,反转后变为 (1,0)(\tt 1,\tt 0)

当合并区间 I1,I2I_1,I_2 至区间 II 时(I1I_1 在前面),设其长度为 s1,s2,ss_1,s_2,s,后两个标记的值分别为 x1,x2,x,y1,y2,yx_1,x_2,x,y_1,y_2,y

  • xx1+x2x \gets x_1 + x_2
  • yy1+y2+x1(s2x2)y \gets y_1 + y_2 + x_1(s_2 - x_2)
    • y1y_1I1I_1 中的逆序对个数。
    • y2y_2I2I_2 中的逆序对个数。
    • x1(s2x2)x_1(s_2 - x_2) 为跨越 I1,I2I_1,I_2 的逆序对个数,它一定由 I1I_1 中的一个 1\tt 1I2I_2 中的一个 0\tt 0 组成,因此其数量等于 I1I_11\tt 1 的个数乘上 I2I_20\tt 0 的个数。
    • 这三种情况加起来,就是总的逆序对个数。
#include <bits/stdc++.h>
#define int unsigned
using namespace std;
const int N = 1 << 16, M = 1 << 18, I = (int) INT_MAX + 1;
int sum[M], invc[M];
bool rev[M];
inline int read()
{
	int x = 0;
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0') x = x * 10 + c - '0', c = getchar_unlocked();
	return x;
}
inline void write(int x)
{
	if (!x) return;
	write(x / 10);
	putchar_unlocked(x % 10 + '0');
}
inline void writeline(int x)
{
	if (x) write(x);
	else putchar_unlocked('0');
	putchar_unlocked('\n');
}
inline int pairs(int x)
{
	return x * (x - 1) >> 1;
}
inline bool update(int pos, int ssz, int all)
{
	rev[pos] = !rev[pos];
	invc[pos] = all - invc[pos];
	invc[pos] -= pairs(sum[pos]);
	sum[pos] = ssz - sum[pos];
	invc[pos] -= pairs(sum[pos]);
	return rev[0];
}
inline bool pushdown(int pos, int spos, int ssz, int all)
{
	rev[pos] = !rev[pos];
	return update(spos, ssz, all) | update(spos | 1, ssz, all);
}
inline bool pushup(int pos, int spos, int ssz)
{
	sum[pos] = sum[spos] + sum[spos | 1];
	invc[pos] = invc[spos] + invc[spos | 1] + sum[spos] * (ssz - sum[spos | 1]);
	return rev[0];
}
bool reverse(int l, int r, int nl, int nr, int sz, int pos)
{
	if (l == nl && r == nr) return update(pos, sz, pairs(sz));
	int lm = (nl + nr) >> 1, rm = lm + 1, ssz = sz >> 1, spos = pos << 1;
	if (rev[pos]) pushdown(pos, spos, ssz, pairs(ssz));
	if (l <= lm) reverse(l, min(lm, r), nl, lm, ssz, spos);
	if (r >= rm) reverse(max(rm, l), r, rm, nr, ssz, spos | 1);
	return pushup(pos, spos, ssz);
}
pair <int, int> count(int l, int r, int nl, int nr, int sz, int pos)
{
	if (l == nl && r == nr) return make_pair(sum[pos], invc[pos]);
	int lm = (nl + nr) >> 1, rm = lm + 1, ssz = sz >> 1, spos = pos << 1;
	pair <int, int> al = make_pair(I, 0), ar = make_pair(I, 0);
	if (rev[pos]) pushdown(pos, spos, ssz, pairs(ssz));
	if (l <= lm) al = count(l, min(lm, r), nl, lm, ssz, spos);
	if (r >= rm) ar = count(max(rm, l), r, rm, nr, ssz, spos | 1);
	int res1 = al.first + ar.first, res2 = max(al.second, ar.second);
	if (res1 < I) res2 = al.second + ar.second + al.first * (r - lm - ar.first);
	return make_pair(res1 & INT_MAX, res2 | pushup(pos, spos, ssz));
}
signed main()
{
	freopen("inversion.in", "r", stdin);
	freopen("inversion.out", "w", stdout);
	int n = read(), q = read() << 1;
	while (q--)
	{
		int l = read(), r = read();
		if (q & 1) reverse(l, r, 0, N - 1, N, 1);
		else writeline(count(l, r, 0, N - 1, N, 1).second);
	}
	return 0;
}