给一个长度为 \(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;
}