[题解] CFgym103069G Prof. Pang's sequence

G. Prof. Pang's sequence

给一个长度为 \(n\) 的序列 \(a\)，多次询问区间 \([l, r]\) 内有多少个子区间的颜色数是奇数。
\(n, m \le 10^5\)。

先按照 HH 的项链 的套路，对于每个数记一下 \(lst_i\) 表示 \(a_i\) 上一次出现的位置。然后扫描线，将所有子区间的答案转化成历史和。颜色出现次数为奇数可以对每个左端点 \(l\) 记一下 \(cnt_{0/1}\) 表示区间 \([l, r]\) 的颜色数为偶数 / 奇数。

在扫描线的过程中，右端点每右移 \(1\)，对 \(cnt\) 的影响就是 \([lst_r + 1, r]\) 的 \(cnt_0\) 和 \(cnt_1\) swap 一下，对历史和的影响是 \(ans \leftarrow ans + cnt_1\)。

然后问题就转化成了维护三元组 \((cnt_0, cnt_1, ans)\)，每次有操作 swap \(cnt_0\) 和 \(cnt_1\)，\(ans \leftarrow ans + x \cdot cnt1\)。

手玩一下发现最后标记的形式一定是 \((cnt_0, cnt_1, ans + add_0 \times cnt_0 + add_1 \times cnt_1)\)，然后分别维护就行。

时间复杂度 \(O((n + q) \log n)\)。

constexpr int MAXN = 5e5 + 9;
int n, q, a[MAXN];
int bin[MAXN], lst[MAXN];
vector<pair<int, int> > que[MAXN];
ll ans[MAXN];

struct Info {
	ll cnt[2], ans;
	
	Info() { cnt[0] = cnt[1] = 0, ans = 0; return; }
	Info(ll x, ll y, ll z) { cnt[0] = x, cnt[1] = y, ans = z; return; }
	friend Info operator + (Info x, Info y) {
		return Info(x.cnt[0] + y.cnt[0],
					x.cnt[1] + y.cnt[1],
					x.ans + y.ans);
	}
};
struct Tag {
	bool swp; ll add0, add1;
	
	Tag(): swp(false), add0(0), add1(0) { return; }
	Tag(bool x, ll a, ll b):
		swp(x), add0(a), add1(b) { return; }
	operator bool() const { return swp || add0 || add1; }
	friend Tag operator * (Tag x, Tag y) {
		Tag ans;
		if (x.swp) swap(y.add0, y.add1);
		ans.swp = x.swp ^ y.swp;
		ans.add0 = x.add0 + y.add0;
		ans.add1 = x.add1 + y.add1;
		return ans;
	}
	Info Apply(Info x) {
		if (swp) swap(x.cnt[0], x.cnt[1]);
		x.ans += add0 * x.cnt[0] + add1 * x.cnt[1];
		return x;
	}
};
struct Node {
	Info dat; Tag tag;
} sgt[MAXN << 2];

void Push_Up(int p) {
	sgt[p].dat = sgt[p << 1].dat + sgt[p << 1 | 1].dat;
	return;
}
void Push_Tag(int p, Tag tg) {
	sgt[p].tag = tg * sgt[p].tag;
	sgt[p].dat = tg.Apply(sgt[p].dat);
	return;
}
void Push_Down(int p) {
	if (sgt[p].tag) {
		Push_Tag(p << 1, sgt[p].tag);
		Push_Tag(p << 1 | 1, sgt[p].tag);
		sgt[p].tag = Tag();
	}
	return;
}
void Build(int L = 1, int R = n, int p = 1) {
	if (L == R) { sgt[p].dat.cnt[0] = 1; return; }
	int Mid = L + R >> 1; Build(L, Mid, p << 1);
	Build(Mid + 1, R, p << 1 | 1); Push_Up(p); return;
}
void Update(int l, int r, Tag tg, int L = 1, int R = n, int p = 1) {
	if (l <= L && R <= r) { Push_Tag(p, tg); return; }
	Push_Down(p); int Mid = L + R >> 1;
	if (r <= Mid) Update(l, r, tg, L, Mid, p << 1);
	else if (Mid < l) Update(l, r, tg, Mid + 1, R, p << 1 | 1);
	else Update(l, r, tg, L, Mid, p << 1), Update(l, r, tg, Mid + 1, R, p << 1 | 1);
	Push_Up(p); return;
}
ll Query(int l, int r, int L = 1, int R = n, int p = 1) {
	if (l <= L && R <= r) return sgt[p].dat.ans;
	Push_Down(p); int Mid = L + R >> 1;
	if (r <= Mid) return Query(l, r, L, Mid, p << 1);
	if (Mid < l) return Query(l, r, Mid + 1, R, p << 1 | 1);
	return Query(l, r, L, Mid, p << 1) + Query(l, r, Mid + 1, R, p << 1 | 1);
}

void slv() {
	n = Read<int>();
	for (int i = 1; i <= n; i ++) a[i] = Read<int>();
	for (int i = 1; i <= n; i ++) lst[i] = bin[a[i]], bin[a[i]] = i;
	q = Read<int>(), Build();
	for (int i = 1; i <= q; i ++) {
		int l = Read<int>(), r = Read<int>();
		que[r].emplace_back(l, i);
	}
	for (int r = 1; r <= n; r ++) {
		Update(lst[r] + 1, r, Tag(1, 0, 0));
		Update(1, r, Tag(0, 0, 1));
		for (auto _ : que[r]) {
			int l = _.fir, id = _.sec;
			ans[id] = Query(l, r);
		}
	}
	for (int i = 1; i <= q; i ++) Write(ans[i], '\n');
	return;
}