义乌中学暑假集训 2021.07.13 D

(Updated: )
oi
,

给定 $n$ 个数的序列 ${a_i}$，有 $m$ 组询问，每次询问给定区间 $[l,r]$，问有多少个子区间 $[i,j]$ 满足 $a_i,\dots,a_j$ 中不同的整数的数目是奇数。

$n,m\leq 5\times 10^5,1\leq a_i\leq n$。

Sol

首先肯定是考虑将询问离线。

然后考虑如何维护这个答案。

不难发现，子区间就相当于所有的前缀中取后缀。

那么我们只需要将询问按右端点排序，更新一下这个数上一次出现位置+1到此位置的状态即可。

直接在线段树上打个标记，分别记录一下奇/偶情况的区间个数、数量、上次出现时间、答案即可。

查询就相当于区间求和了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
    Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
    Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=5e5+10;
int n,m,a[N],p[N],v[N],j;
LL Ans[N];
struct Que{int l,r,id;}q[N];
class SegmentTree{
    private:
        struct node{int cnt,sz[2],stk[2],lst,tg;LL Ans;}T[N<<2];
        #define mid (l+r>>1)
        #define PT CI x=1,CI l=1,CI r=n
        #define LT x<<1,l,mid
        #define RT x<<11,mid+1,r
        #define PU(x) (T[x].sz[0]=T[x<<1].sz[0]+T[x<<11].sz[0],T[x].sz[1]=T[x<<1].sz[1]+T[x<<11].sz[1],T[x].Ans=T[x<<1].Ans+T[x<<11].Ans)
        I void PD(CI x,CI l,CI r){
            T[x].stk[T[x].tg]+=j-T[x].lst,T[x].lst=j;
            T[x].Ans+=1LL*T[x].stk[1]*T[x].sz[0]+1LL*T[x].stk[0]*T[x].sz[1];
            if(l<r) T[x<<1].stk[!T[x<<1].tg]+=T[x].stk[1],T[x<<1].stk[T[x<<1].tg]+=T[x].stk[0],T[x<<1].tg^=T[x].tg,
            T[x<<11].stk[!T[x<<11].tg]+=T[x].stk[1],T[x<<11].stk[T[x<<11].tg]+=T[x].stk[0],T[x<<11].tg^=T[x].tg,
            T[x<<1].lst=T[x<<11].lst=j;
            T[x].tg&&(swap(T[x].sz[0],T[x].sz[1]),T[x].tg=0),T[x].stk[0]=T[x].stk[1]=0;
        }
    public:
        I void B(PT){
            if(T[x].sz[0]=r-l+1,l==r) return ;
            B(LT),B(RT);
        }
        I void U(CI L,CI R,PT){
            if(L<=l&&r<=R) return j--,PD(x,l,r),T[x].tg=1,j++,PD(x,l,r),void();
            PD(x,l,r);if(l<r) PD(x<<1,l,mid),PD(x<<11,mid+1,r);
            L<=mid&&(U(L,R,LT),0),R>mid&&(U(L,R,RT),0),PU(x);
        }
        I LL Q(CI L,CI R,PT){
            if(PD(x,l,r),L<=l&&r<=R) return T[x].Ans;
            LL S=0;return L<=mid&&(S+=Q(L,R,LT)),R>mid&&(S+=Q(L,R,RT)),S;
        }
}T;
I bool cmp(Cn Que& x,Cn Que& y){return x.r<y.r;}
int main(){
    RI i;for(read(n),i=1;i<=n;i++) read(a[i]),p[i]=v[a[i]],v[a[i]]=i;
    for(read(m),i=1;i<=m;i++) read(q[i].l,q[i].r),q[i].id=i;
    for(sort(q+1,q+m+1,cmp),T.B(),i=1;i<=m;i++){
        W(j<q[i].r) j++,T.U(p[j]+1,j);
        Ans[q[i].id]=T.Q(q[i].l,q[i].r);
    }for(i=1;i<=m;i++) writeln(Ans[i]);return clear(),0;
}