自动搬运

查看原文

来自洛谷，原作者为

	Nt_Tsumiki 火星咖啡馆 || 我们终将相遇，在那悠远的苍穹 || xp是傲娇少女 || 绀海厨子捏 || 会不定时红温 || NOIP 2024 全国唯一一个 263 || 我是粘土投诉米奇

搬运于2025-08-24 23:01:36，当前版本为作者最后更新于2024-11-23 07:11:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先离线。

你考虑维护一个长得像历史和的 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;
}