题解：P10822 [EC Final 2020] Prof. Pang's sequence

· · 题解

先离线。

你考虑维护一个长得像历史和的 DS，你维护一个指针 r 扫一遍整个序列，线段树上每个叶子 l 代表 [l,r]，这段子区间的前缀中有多少个含有奇数个不同的数。

对于不同的数我们有经典 trick 你记一个 pre_i 表示与 a_{pre_i}=a_i 且离 i 最近的数，那你每次要更改的就是 [pre_r+1,r] 这段区间的奇偶性。

然后你对 [1,r] 这段前缀所有为奇数的点进行一个整体加一，你考虑这个玩意咋维护。

一个比较 navie 的想法是上矩阵，常熟太大，我们有全♂新♂做♂法♂。

考虑维护两棵线段树，然后每次反转奇偶性就是交换对应区间，然后整体加一只对一棵线段树做就行了。

bool M1;
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

#define N 500005
#define LL long long

inline int R() {
    int x=0; bool f=0; char c=getchar();
    while (!isdigit(c)) f|=(c=='-'),c=getchar();
    while (isdigit(c)) x=x*10+c-'0',c=getchar();
    return f?-x:x;
}

template<typename T>
void W(T x,char Extra=0) {
    if (x<0) putchar('-'),x=-x; if (x>9) W(x/10);
    putchar(x%10+'0'); if (Extra) putchar(Extra);
}

using namespace std;
int n,m,a[N],tmp[N],pre[N]; LL ans[N];

int tcnt,rt[2];
struct Tree { LL sum,tag; int siz,ls,rs; }t[N<<3];

void build(int &x,int l,int r,int op) {
    x=++tcnt;
    if (l==r) return t[x].siz=(!op),void();
    int mid=(l+r>>1);
    build(t[x].ls,l,mid,op); build(t[x].rs,mid+1,r,op);
    t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz;
}

void pushdown(int x) {
    if (t[x].tag) {
        if (t[x].ls) t[t[x].ls].sum+=1ll*t[t[x].ls].siz*t[x].tag,t[t[x].ls].tag+=t[x].tag;
        if (t[x].rs) t[t[x].rs].sum+=1ll*t[t[x].rs].siz*t[x].tag,t[t[x].rs].tag+=t[x].tag;
        t[x].tag=0;
    }
}

void swp(int &x,int &y,int l,int r,int L,int R) {
    if (L<=l and r<=R) return swap(x,y),void();
    int mid=(l+r>>1); pushdown(x); pushdown(y);
    if (L<=mid) swp(t[x].ls,t[y].ls,l,mid,L,R);
    if (R>mid) swp(t[x].rs,t[y].rs,mid+1,r,L,R);
    t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
    t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz;
    t[y].sum=t[t[y].ls].sum+t[t[y].rs].sum;
    t[y].siz=t[t[y].ls].siz+t[t[y].rs].siz;
}

void upd(int x,int l,int r,int L,int R,int k) {
    if (L<=l and r<=R) return t[x].sum+=t[x].siz*k,t[x].tag+=k,void();
    int mid=(l+r>>1); pushdown(x);
    if (L<=mid) upd(t[x].ls,l,mid,L,R,k);
    if (R>mid) upd(t[x].rs,mid+1,r,L,R,k);
    t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
}

LL ask(int x,int l,int r,int L,int R) {
    if (L<=l and r<=R) return t[x].sum;
    int mid=(l+r>>1); pushdown(x);
    if (R<=mid) return ask(t[x].ls,l,mid,L,R);
    else if (L>mid) return ask(t[x].rs,mid+1,r,L,R);
    else return ask(t[x].ls,l,mid,L,R)+ask(t[x].rs,mid+1,r,L,R);
}

struct Que { int l,id; };
vector<Que> que[N];

bool M2;

int main() {
    // cerr<<(&M2-&M1)/1024.0/1024<<'\n';
    // freopen("task.in","r",stdin);
    // freopen("task.out","w",stdout);
    n=R();
    for (int i=1;i<=n;i++) a[i]=R(),pre[i]=tmp[a[i]],tmp[a[i]]=i;
    m=R();
    for (int i=1;i<=m;i++) {
        int l=R(),r=R();
        que[r].push_back({l,i});
    }
    build(rt[0],1,n,0); build(rt[1],1,n,1);
    for (int i=1;i<=n;i++) {
        swp(rt[0],rt[1],1,n,pre[i]+1,i);
        upd(rt[1],1,n,1,i,1);
        for (auto [l,id]:que[i])
            ans[id]=ask(rt[0],1,n,l,i)+ask(rt[1],1,n,l,i);
    }
    for (int i=1;i<=m;i++) W(ans[i],'\n');
    return 0;
}