好心人看到了点点赞，不点赞的谭总祝你RP++

· · 题解

望着全是随机化的题解区，仅有着一篇稍稍提起过一种不优美的分块，经过一中午的冥思苦想和带着分块的忠诚，一篇 O(n\sqrt{n}) 的题解终于诞生！！！好了批话结束

Solution

不优美的分块原理是对于每一个前缀，用一个 n 位的二进制串记录每个数出现次数的奇偶性。查询时异或一下，找到最低的非零位即可。因为空间爆炸，所以对原序列分块，记录每个整块末尾时的情况，因为只用奇偶性，所以可以用 bitset 来记录，关于这种情况可以去看 Mars_Dingdang 大佬的题解。

我们沿用这个思想，唯一不是 \sqrt{n} 的操作为值域上找到最低的非零位，为了去除这个污点，我们可以想到值域分块，可是如何操作呢？

我们需要了解一点，值域分块的块标记不是来记录具体信息的，而是判断此处有没有解的标识，bitset 就是用二进制串来充当了具体信息，由于是记录每个数出现次数的奇偶性，所以它的异或就是在查看两处是否有差异，是否出现了奇数次出现次数。

所以我们将 bitset 的 64 位扩大为 \sqrt{n} 位，不记录这具体信息，而是改用哈希，这里并不是其他题解的随机化的异或哈希，这只是将 \sqrt{n} 位哈希变为一个抽象信息。

在原序列分块处，你再记录一下每个整块末尾时，从第一位到当前整块末尾时值域分块上每个块的抽象信息。这里的空间复杂度是 O(\sqrt{n} \times \sqrt{n}) = O(n) 的。

接下来，小于两个块长的区间暴力处理，否则先将左右两边散块分别合并到左端点所在块和右端点所在块左边的块，然后在值域分块上找最小的有差异的块，再在该块中找到最小的有差异的数，即使答案。

到此，全操作都为 \sqrt{n} 的操作。

实现代码时，要注意离散化，还有这代码虽然时间复杂度为 O(n\sqrt{n})，但是这常数可能有点大，需加上快读和火车头。这怎么比不优美的分块还慢啊！！！

Code

AC code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9,M=1e6+9,mod=1e9+7,has=131;
int a[N],b[N],bel[N],lenn;
bitset<200002> qq[600],q;
int f[600][600];//f[i][j] : 从第一个数到第i个序列块末尾时值域块上的抽象信息
int bell[600],lin[N];
long long op[600];int n;
inline int fac(int a,int b)//取模优化
{
    if(a>b) return a-b;
    return a-b+mod;
}
inline int qw(int a,int b)
{
    if(a+b>mod) return a+b-mod;
    return a+b;
}
inline int findd(int l,int r)//值域分块
{
    for(int i=1;i<=bel[n];i++)
    {
        if(f[l][i]!=f[r][i])
        {
            for(int j=(i-1)*lenn+1;j<=i*lenn;j++)
            {
                if(qq[l][j]!=qq[r][j])
                {
                    return j;
                }
            }
            return 0;
        }
    }
    return 0;
}
signed main()
{
    cin>>n;
    lenn=sqrt(n);
    for(int i=1;i<=n;i++)
        cin>>a[i],b[i]=a[i],bel[i]=(i-1)/lenn+1;
    op[0]=1;
    for(int i=1;i<=lenn;i++)
    {
        op[i]=op[i-1]*has%mod;
    }
    sort(b+1,b+1+n);
    int len=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+1+len,a[i])-b;//离散化
    int bl=1;
    for(int i=1;i<=n;i++)//预处理
    {
        if(bl!=bel[i])
        {
            qq[bl]=q;
            for(int j=1;j<=bel[n];j++)
            {
                f[bl][j]=bell[j];
            }
            bl=bel[i];
        }
        if(q[a[i]]) q[a[i]]=0,bell[bel[a[i]]]=fac(bell[bel[a[i]]],op[a[i]-(bel[a[i]]-1)*lenn]);
        else q[a[i]]=1,bell[bel[a[i]]]=qw(bell[bel[a[i]]],op[a[i]-(bel[a[i]]-1)*lenn]);
    }
    bl=bel[n];
    qq[bl]=q;
    for(int j=1;j<=bel[n];j++)
    {
        f[bl][j]=bell[j];
    }
    int m,last=0;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        l^=last;
        r^=last;
        int ans=99999999;
        if(bel[r]-bel[l]<=1)
        {
            for(int j=l;j<=r;j++)
            {
                lin[a[j]]++;
            }
            for(int j=l;j<=r;j++)
            {
                if(lin[a[j]]&1)
                    ans=min(ans,a[j]);
            }
            for(int j=l;j<=r;j++)
            {
                lin[a[j]]=0;
            }
            if(ans==99999999)
                ans=0;
            last=b[ans];
        }
        else
        {
//          cout<<141;
            int ll=bel[l],rr=bel[r];
            for(int j=l;j<=ll*lenn;j++)//处理散块
            {
                if(qq[ll][a[j]])
                {
                    qq[ll][a[j]]=0;
                    f[ll][bel[a[j]]]=fac(f[ll][bel[a[j]]],op[a[j]-(bel[a[j]]-1)*lenn]);
                }
                else
                {
                    qq[ll][a[j]]=1;
                    f[ll][bel[a[j]]]=qw(f[ll][bel[a[j]]],op[a[j]-(bel[a[j]]-1)*lenn]);
                }
            }
            for(int j=(rr-1)*lenn+1;j<=r;j++)
            {
                if(qq[rr-1][a[j]])
                {
                    qq[rr-1][a[j]]=0;
                    f[rr-1][bel[a[j]]]=fac(f[rr-1][bel[a[j]]],op[a[j]-(bel[a[j]]-1)*lenn]);
                }
                else
                {
                    qq[rr-1][a[j]]=1;
                    f[rr-1][bel[a[j]]]=qw(f[rr-1][bel[a[j]]],op[a[j]-(bel[a[j]]-1)*lenn]);
                }
            }
            ans=findd(ll,rr-1);
            last=b[ans];
            for(int j=l;j<=ll*lenn;j++)//还原
            {
                if(qq[ll][a[j]])
                {
                    qq[ll][a[j]]=0;
                    f[ll][bel[a[j]]]=fac(f[ll][bel[a[j]]],op[a[j]-(bel[a[j]]-1)*lenn]);
                }
                else
                {
                    qq[ll][a[j]]=1;
                    f[ll][bel[a[j]]]=qw(f[ll][bel[a[j]]],op[a[j]-(bel[a[j]]-1)*lenn]);
                }
            }
            for(int j=(rr-1)*lenn+1;j<=r;j++)
            {
                if(qq[rr-1][a[j]])
                {
                    qq[rr-1][a[j]]=0;
                    f[rr-1][bel[a[j]]]=fac(f[rr-1][bel[a[j]]],op[a[j]-(bel[a[j]]-1)*lenn]);
                }
                else
                {
                    qq[rr-1][a[j]]=1;
                    f[rr-1][bel[a[j]]]=qw(f[rr-1][bel[a[j]]],op[a[j]-(bel[a[j]]-1)*lenn]);
                }
            }
        }
        cout<<last<<endl;
    }
    return 0;
}