2020 ICPC Asia East Continent Final G Prof. Pang's sequence

题目描述

https://codeforces.com/gym/103069/problem/G

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次询问，每次询问给定区间 $[l,r]$，求区间 $[l,r]$ 有多少对子区间 $[i,j]$， 满足 $[i,j]$ 内不同的 $a_i$ 有奇数个

$n,m \le 5\times 10^5$

Solution

我们考虑扫描线扫右端点，然后用线段树维护左端点 $0/1$ 表示这个区间合法

那么我们的一次询问相当于求一段区间的历史和，同时右端点移动时，我们需要将一段区间的 $0$ 和 $1$ 翻转

我们考虑维护区间 $0$ 的个数 $v[0]$、区间 $1$ 的个数 $v[1]$、区间历史和 $tv$、区间翻转 $rev$，为了维护区间历史和，我们需要维护一个 $t[2]$，表示区间 $0$ 对区间历史和的贡献以及区间 $1$ 对区间历史和的贡献

我们令区间翻转标记优先级最高，同时区间历史和的形式表示为

if (rev) T[i].tv += t[0] * T[i].v[1] + t[1] * T[i].v[0];
else T[i].tv += t[0] * T[i].v[0] + t[1] * T[i].v[1];

那么我们容易得到 $rev$ 对 $t[2]$ 的影响如下

if (rev) swap(T[i].t[0], T[i].t[1]), T[i].rev ^= 1;

#include <iostream>
#include <vector>
#define maxn 500010
#define ll long long
using namespace std;

int n, m, a[maxn];

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    ll v[2], tv;
    int t[2]; bool rev;
} T[maxn * 4];
inline void maintain(int i) {
    T[i].v[0] = T[lc].v[0] + T[rc].v[0];
    T[i].v[1] = T[lc].v[1] + T[rc].v[1];
    T[i].tv = T[lc].tv + T[rc].tv;
}

void build(int i, int l, int r) {
    if (l == r) return T[i] = { 1, 0, 0, 0, 0, 0 }, void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i);
}

inline void Update(int i, int t[], bool rev) {
    if (rev) T[i].tv += t[0] * T[i].v[1] + t[1] * T[i].v[0];
    else T[i].tv += t[0] * T[i].v[0] + t[1] * T[i].v[1];
    if (rev) swap(T[i].v[0], T[i].v[1]);
    
    if (rev) swap(T[i].t[0], T[i].t[1]), T[i].rev ^= 1;
    T[i].t[0] += t[0]; T[i].t[1] += t[1];
}

inline void pushdown(int i) {
    int *t = T[i].t; bool &rev = T[i].rev;
    Update(lc, t, rev); Update(rc, t, rev);
    t[0] = t[1] = rev = 0;
}

int emp_t[2], t_1[2] = { 0, 1 };
void update(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, emp_t, 1);
    int m = l + r >> 1; pushdown(i);
    update(lc, l, m, L, R); update(rc, m + 1, r, L, R);
    maintain(i);
}

ll query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].tv;
    int m = l + r >> 1; pushdown(i);
    return query(lc, l, m, L, R) + query(rc, m + 1, r, L, R); 
}

int vis[maxn];
vector<pair<int, int>> A[maxn];
ll ans[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        A[y].emplace_back(x, i); 
    } build(1, 1, n);
    for (int i = 1; i <= n; ++i) {
        update(1, 1, n, vis[a[i]] + 1, i); vis[a[i]] = i; 
        Update(1, t_1, 0);
        for (auto [k, id] : A[i]) ans[id] = query(1, 1, n, k, i);
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
    return 0;
}