题解：P14764 [Opoi 2025] CCD 的不难题

· · 题解

提供一个比 std 好写些的分块做法，码量只有 std 的约 1/3。

Part 1:预处理

我们将整个序列每 B 个数分一块，共分为 \lceil\frac{n}{B}\rceil 块。然后对于每个满足 1\le l\le r\le\lceil\frac{n}{B}\rceil 的对 (l,r)，开 n 个桶记录 l 到 r 这几个块中每个数字的出现次数，同时开 n 个链表，第 i 个链表有序记录了 l 到 r 这几个块中出现次数为 i 的数字。

由于有 O(\frac{n^2}{B^2}) 对 (l,r)，预处理每一对的时空复杂度均为 O(n)，故这段预处理的时空复杂度均为 O(\frac{n^3}{B^2})。

Part 2:查询

对于每一次查询，我们先找出 l，r 所在的块 L，R，并计算出块 L 的左边界 l' 与块 R 的右边界 r'，然后扫一遍区间 [l',l) 与区间 (r,r']，在对 (L,R) 所对应的那 n 个桶上直接修改，得到区间 [l,r] 中每个数字的出现次数。

接下来我们思考可能会有哪些数出现次数可能为 k。除了在区间 [l',l) 与区间 (r,r'] 出现过的数外，剩下的数在区间 [l,r] 的出现次数与在 L 到 R 的块中出现次数相同，故剩下的数中只有在 L 到 R 的块中出现次数为 k 的数中的最大者可能成为答案。

因此，我们可以再扫一遍区间 [l',l) 与区间 (r,r']，找出里面满足询问条件的最大数，随后由大到小遍历对 (L,R) 所对应的第 k 个链表，且在找到首个不在区间 [l',l) 与区间 (r,r'] 的数后停止遍历。而很明显的，对那个链表里的数来说，不在区间 [l',l) 与区间 (r,r'] 也即满足询问条件，所以不用在开一个桶记录区间 [l',l) 与区间 (r,r'] 中出现过的数。

因为对 (L,R) 所对应的那 n 个桶的信息后续询问可能还要用到，故在找到答案后还要再扫一遍区间 [l',l) 与区间 (r,r'] 还原这 n 个桶的信息。

由于区间 [l',l) 与区间 (r,r'] 的长度为 O(B)， 故链表中只会有 O(B) 个数在这两个区间中出现，因而只要在链表中遍历 O(B) 个数就一定能找到满足条件的数。故遍历链表的时间复杂度为 O(B)，而扫三遍区间 [l',l) 与区间 (r,r'] 的时间复杂度也为 O(B)。综上，一次查询的复杂度为 O(B)，q 次即为 O(qB)。

Part 3:最小化时间复杂度

由上述分析可知该分块算法的总复杂度为 O(\frac{n^3}{B^2}+qB)，在认为 n 与 q 同阶时取 B=n^\frac{2}{3} 时总复杂度最小，为 O(n^\frac{5}{3})，比 std 的 O(n^\frac{3}{2}) 劣，但仍可通过本题，只是需要简单卡常，如在一些地方用 unsigned short 而不是 int。

附代码：

#include<bits/stdc++.h>
using namespace std;
int n,B,a[50001],q,l,r,k,ans;
unsigned short cnt[41][41][50001],hd[41][41][50001],nxt[41][41][50001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;B=pow(n,2.0/3);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int l=1;l<=(n-1)/B+1;l++)
    {
        for(int r=l;r<=(n-1)/B+1;r++)
        {
            int l2=(l-1)*B+1,r2=min(n,r*B);
            for(int i=l2;i<=r2;i++)
            {
                cnt[l][r][a[i]]++;
            }
            for(int i=1;i<=n;i++)
            {
                nxt[l][r][i]=hd[l][r][cnt[l][r][i]];
                hd[l][r][cnt[l][r][i]]=i;
            }
        }
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>l>>r>>k;
        l^=ans;r^=ans;k^=ans;ans=0;
        int L=(l-1)/B+1,R=(r-1)/B+1;
        int l2=(L-1)*B+1,r2=min(n,R*B);
        for(int j=l2;j<l;j++)
        {
            cnt[L][R][a[j]]--;
        }
        for(int j=r+1;j<=r2;j++)
        {
            cnt[L][R][a[j]]--;
        }
        for(int j=l2;j<l;j++)
        {
            if(cnt[L][R][a[j]]==k)ans=max(ans,a[j]);
        }
        for(int j=r+1;j<=r2;j++)
        {
            if(cnt[L][R][a[j]]==k)ans=max(ans,a[j]);
        }
        for(int j=hd[L][R][k];j;j=nxt[L][R][j])
        {
            if(cnt[L][R][j]==k)
            {
                ans=max(ans,j);
                break;
            }
        }
        for(int j=l2;j<l;j++)
        {
            cnt[L][R][a[j]]++;
        }
        for(int j=r+1;j<=r2;j++)
        {
            cnt[L][R][a[j]]++;
        }
        cout<<ans<<'\n';
    }
}