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

题目分析

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

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

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

设$pre[a[i]]$表示上个$a[i]$的位置。

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

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

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

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

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

Code

#include <bits/stdc++.h>
#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 << 1
    #define rs rt << 1 | 1
    #define lson ls, l, mid
    #define rson rs, mid + 1, r

    int tree[N << 1], cnt[N << 1][2], lazy[N << 1][2];
    bool flip[N << 1];

    inline void flip01(int rt){
    
        std::swap(cnt[rt][0], cnt[rt][1]);
        std::swap(lazy[rt][0], lazy[rt][1]);
        flip[rt] ^= 1;
    }

    inline void apply_tag(int rt, int k0, int k1){
    
        tree[rt] += k0 * cnt[rt][0] + k1 * cnt[rt][1];
        lazy[rt][0] += k0, lazy[rt][1] += k1;
    }

    inline void push_up(int rt){
    
        tree[rt] = tree[ls] + tree[rs];
        cnt[rt][0] = cnt[ls][0] + cnt[rs][0];
        cnt[rt][1] = cnt[ls][1] + cnt[rs][1];
    }

    inline void push_down(int rt){
    
        if(flip[rt]) flip01(ls), flip01(rs), flip[rt] ^= 1;
        apply_tag(ls, lazy[rt][0], lazy[rt][1]);
        apply_tag(rs, lazy[rt][0], lazy[rt][1]);
        lazy[rt][0] = lazy[rt][1] = 0;
    }

    void build(int rt, int l, int r){
    
        if(l == r){
     cnt[rt][0] = 1; return; }
        int mid = l + r >> 1;
        build(lson), build(rson);
        push_up(rt);
    }

    void update(int rt, int l, int r, int L, int R){
    
        if(l >= L && r <= R){
    
            flip01(rt);
            return;
        }
        push_down(rt);
        int mid = l + r >> 1;
        if(mid >= L) update(lson, L, R);
        if(mid < R) update(rson, L, R);
        push_up(rt);
    }

    int query(int rt, int l, int r, int L, int R){
    
        if(l >= L && r <= R) return tree[rt];
        push_down(rt);
        int mid = l + r >> 1, ans = 0;
        if(mid >= L) ans += query(lson, L, R);
        if(mid < R) ans += query(rson, L, R);
        return ans;
    }
}


struct query{
     int r, id; };

vector<query> q[N];
vector<int> mk[N];


inline void solve(){
    
    int n = 0; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], pre[i] = lst[a[i]], lst[a[i]] = i;
    for(int i = 1; i <= n; i++) mk[pre[i]].emplace_back(i);
    int m = 0; cin >> m;
    for(int i = 1; i <= m; i++){
    
        int l, r; cin >> l >> 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 < mk[i].size(); j++) SegmentTree::update(SEGRG, mk[i][j], n);
        SegmentTree::apply_tag(1, 0, 1);
        if(!q[i].size()) continue;
        for(auto x : q[i]) ans[x.id] = SegmentTree::query(SEGRG, i, x.r);
    }
    
    for(int i = 1; i <= m; i++) cout << ans[i] << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}