【問題解】ルーグSP 3267 DQUERY-D-query

原題転送ゲート

この問題はLuogu P 1972[SDOI 2009]HHのネックレスに似ていますが、データの大きさが少し違います。

私のブログではモズの紹介をしています。

私たちが質問を並べ替えるとき、普通はこのようにqaqです。

inline bool cmp(register query a,register query b)
{
    return a.bl==b.bl?a.r

パリティ最適化を追加しました:パリティブロックでソートします。区間の左端点のあるブロックが異なる場合は、直接左端点を押して小から大列に並びます。同じ場合、奇数ブロックは右端を小から大まで、偶数ブロックは右端を大から小まで押します。

inline bool cmp(register query a,register query b)
{
    return a.bl!=b.bl?a.lb.r);
}

残りはモズの板でシミュレートすればいいqaq

完全なコード:

#pragma GCC optimize("O3")
#include 
#define N 500005
using namespace std;
inline int read()
{
    register int x=0,f=1;register char ch=getchar();
    while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
inline void write(register int x)
{
    if(!x)putchar('0');if(x<0)x=-x,putchar('-');
    static int sta[25];int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
struct query{
    int l,r,id,bl;
}q[N];
int num[1000001],blocksize=0,a[N],ans[N];
inline bool cmp(register query a,register query b)
{
    return a.bl!=b.bl?a.lb.r);
}
int main()
{
    int n=read();
    blocksize=sqrt(n);
    for(register int i=1;i<=n;++i)
        a[i]=read();
    int m=read();
    for(register int i=1;i<=m;++i)
    {
        int l=read(),r=read();
        q[i]=(query){l,r,i,l/blocksize};
    }
    sort(q+1,q+1+m,cmp);
    int l=1,r=0,sum=0;
    for(register int i=1;i<=m;++i)
    {
        int ll=q[i].l,rr=q[i].r;
        while(lll)
            sum-=!--num[a[l++]];
        while(rr>r)
            sum+=!num[a[++r]]++;
        while(rr