题目概述

Prof. Pang's sequence

解题报告

首先根据经典套路，我们记录 $pre_i$ 表示 $i$ 上次的出现位置，这样的话对于一个左端点 $L$ ，只有 $pre_i<L$ 有贡献。

考虑离线+扫描线，我们倒着添加元素。添加位置 $L$​​ 的时候，$pre_i=L$​​ 的 $i$​​​ 就会变得没有贡献，同时 $pre_L$ ​​会进入贡献。

由于这道题要求不同数出现个数是奇数，因此我们考虑对于每个 $L$ 维护一个 $01$ 序列 $\{a_{L,n}\}$ 表示以当前 $L$ 为左端点，以 $i$​​ 为右端点是奇数还是偶数。

没添加 $L$​​​​ 时，$\{a_{L,n}\}$​​​​ 继承 $\{a_{L+1,n}\}$​​​ ，添加位置 $L$​​​​ 的时候，会改变 $[L,n]$​​​​ 所有 $a_{L,i}$​​​​ 的奇偶性，并且如果存在 $pre_i=L$​​​​ ，那么 $[i,n]$​​​​ 所有 $a_{L,i}$​​​​ 也会改变奇偶性。每次维护好 $\{a_{L,n}\}$​​​​ 后，对于一次询问 $[L,R]$​​​​ ，答案就是所有 $j\ge L,L\le i\le R$ 中 $a_{j,i}=1$ 的个数。

整理一下，我们需要实现：

1. 维护当前 $01$ 序列 $\{a_{L,n}\}$​ ，需要支持区间 $01$ 反转
2. 记录序列 $\{sum_n\}$ ，$sum_i=\sum_{j\ge L} a_{j,i}$​ ，每次处理完 $\{a_{L,n}\}$ 之后更新 $\{sum_n\}$
3. 每次询问 $[L,R]$ ，答案为 $\sum_{i=L}^{R}sum_i$​

考虑用线段树维护这些操作，需要用到两个标记，反转标记和更新标记。每个点记录下面的信息：

1. $cnt_{p,0/1}$ ：线段里 $0/1$​ 的个数
2. $sum_p$ ：线段里 $sum_{[L,R]}$ 的和
3. $tag_{p,0/1}$ ：$0/1$ 更新标记，$tag_{p,0}$ 表示由 $0$ 提供的贡献，$tag_{p,1}$ 表示由 $1$ 提供的贡献
4. $flip_p$ ：反转标记

每次下传标记的时候，规定先传反转标记，后传更新标记。那么在反转时，$cnt_{p,0/1}$​ 和 $tag_{p,0/1}$​ 都会进行 $0/1$​​ 交换（因为 $tag_{p,0/1}$​ 对应 $cnt_{p,0/1}$​ ，$cnt_{p,0/1}$​ 交换 $tag_{p,0/1}$​ 也需要跟着交换）。在更新时，$sum_p$​ 加上 $\sum_{i=0}^{1}cnt_{p,i}\cdot TAG_{i}$​ ，其中 $TAG_{0/1}$ 是上面传下来的标记。

这样添加完 $L$ 之后，每次查询 $[L,R]$​ 时只需要在线段树里查找 $[L,R]$ 中 $sum$ 的和就行了。

示例程序

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=500000,maxt=maxn<<2;

int n,m,a[maxn+5],lst[maxn+5],c[maxn+5];vector<int> e[maxn+5];
struct data {int R,id;};vector<data> q[maxn+5];
int tag[maxt+5][2],cnt[maxt+5][2];bool flip[maxt+5];LL sum[maxt+5],ans[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
void Build(int L,int R,int p=1){
    if (L==R) {cnt[p][0]=1;return;} int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);
    sum[p]=sum[p<<1]+sum[p<<1|1];
    cnt[p][0]=cnt[p<<1][0]+cnt[p<<1|1][0];
    cnt[p][1]=cnt[p<<1][1]+cnt[p<<1|1][1];
}
void Addflip(int p) {swap(cnt[p][0],cnt[p][1]);swap(tag[p][0],tag[p][1]);flip[p]^=1;}
void Addtag(int p,LL A,LL B){
    sum[p]+=A*cnt[p][0]+B*cnt[p][1];
    tag[p][0]+=A;tag[p][1]+=B;
}
void Pushdown(int p){
    if (flip[p]) Addflip(p<<1),Addflip(p<<1|1),flip[p]=0;
    Addtag(p<<1,tag[p][0],tag[p][1]);
    Addtag(p<<1|1,tag[p][0],tag[p][1]);
    tag[p][0]=tag[p][1]=0;
}
void Flip(int L,int R,int l=1,int r=n,int p=1){
    if (L==l && r==R) return Addflip(p);
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Flip(L,R,l,mid,p<<1); else if (L>mid) Flip(L,R,mid+1,r,p<<1|1);
    else Flip(L,mid,l,mid,p<<1),Flip(mid+1,R,mid+1,r,p<<1|1);
    sum[p]=sum[p<<1]+sum[p<<1|1];
    cnt[p][0]=cnt[p<<1][0]+cnt[p<<1|1][0];
    cnt[p][1]=cnt[p<<1][1]+cnt[p<<1|1][1];
}
LL Ask(int L,int R,int l=1,int r=n,int p=1){
    if (L==l && r==R) return sum[p];
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) return Ask(L,R,l,mid,p<<1); else if (L>mid) return Ask(L,R,mid+1,r,p<<1|1);
    else return Ask(L,mid,l,mid,p<<1)+Ask(mid+1,R,mid+1,r,p<<1|1);
}
int main(){
    readi(n);for (int i=1;i<=n;i++) readi(a[i]),c[i]=lst[a[i]],lst[a[i]]=i;
    for (int i=1;i<=n;i++) e[c[i]].push_back(i);
    readi(m);for (int i=1,L,R;i<=m;i++) readi(L),readi(R),q[L].push_back((data){R,i});
    Build(1,n);
    for (int i=n;i;i--){
        Flip(i,n);for (int j=0,si=e[i].size();j<si;j++) Flip(e[i][j],n);Addtag(1,0,1);
        for (int j=0,si=q[i].size();j<si;j++) ans[q[i][j].id]=Ask(i,q[i][j].R);
    }
    for (int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}