2020 ICPC Asia East Continent Final G. Prof. Pang‘s sequence 线段树/扫描线

题目分析

给定序列 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1​,a2​,…,an​以及 m m m个询问。对于每个询问 ( l , r ) (l, r) (l,r)回答区间 [ l , r ] [l, r] [l,r]中满足不同数字个数为奇数的子区间个数。

首先将所有询问离线，然后考虑对同一 L L L回答所有 R R R的答案。

我们可以通过维护所有以 L L L为起点，以 i ( 1 ≤ i ≤ n ) i(1 \leq i \leq n) i(1≤i≤n)为终点的区间奇偶结果序列。那么考虑区间如何扩展：

设 p r e [ a [ i ] ] pre[a[i]] pre[a[i]]表示上个 a [ i ] a[i] a[i]的位置。

对于 [ L + 1 , n ] → [ L , n ] [L+ 1,n] \rightarrow [L, n] [L+1,n]→[L,n]，如果存在 i i i使得 p r e [ a [ i ] ] = L pre[a[i]] = L pre[a[i]]=L，则 [ i , n ] [i, n] [i,n]所有区间所有的右端点和 L L L组成的区间都不会发生奇偶性反转，而 [ L , i ] [L, i] [L,i]会反转。

扩展完区间后，我们可以直接查询区间和，即为最终答案。

那么我们需要使用线段树维护

1. 区间和以及奇偶区间和
2. 奇偶性统计
3. 更新标记/懒标记
4. 反转标记

注意进行反转操作的时候，需要交换 l a z y lazy lazy标记。

Code

#include 
#pragma gcc optimize(2)
#define SEGRG 1, 1, n
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 10;
int a[N], pre[N], lst[N], ans[N];

namespace SegmentTree{
    #define ls rt > r;
        q[l].emplace_back(query{.r = r, .id = i});
    }
    SegmentTree::build(SEGRG);
    for(int i = n; i >= 1; i--){
        SegmentTree::update(SEGRG, i, n);
        for(int j = 0; j