题解：P16333 [DSDOI Round 1] 邓少分小组

StepByStep_666 · 2026-05-10 16:05:35 · 题解

P16333 邓少分小组

题目传送门

思路分析

首先，很容易想到的做法：直接枚举所有区间 [L,R]，然后挨个检查里面每个 i 是否满足 A_i 和 B_i 都在 [L,R] 里。

但一看数据范围 n \le 5 \times 10^5，O(n^2) 暴力直接 TLE 飞到天上，根本跑不动。

暴力代码大概长这样：

for(int L=1;L<=n;L++)
for(int R=L;R<=n;R++){
    bool ok=1;
    for(int i=L;i<=R;i++){
        if(A[i]<L||A[i]>R) ok=0;
        if(B[i]<L||B[i]>R) ok=0;
    }
    if(ok) ans++;
}

直接超时，连样例都过不去。

优化思路

那怎么办？这种区间封闭性题目，有个经典技巧：随机哈希 + 前缀和。

思路很简单：给每个位置 i 赋一个巨大的随机 64 位权值，把两个条件合并成一个总和为 0 的式子。然后用前缀和判断：如果 f[R] = f[L-1]，说明 [L,R] 合法。

这样复杂度直接变成 O(n)，完美通过。

Code

#include<bits/stdc++.h>
#define int long long
#define cyx using
#define is namespace
#define handsame std
cyx is handsame;
typedef long long ll;
int read()
{
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
const int MAXN=500005;
ll a[MAXN],b[MAXN],val[MAXN],f[MAXN];
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;i++) val[i]=rnd();
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];

        unordered_map<ll,ll>mp;
        mp[0]=1;
        ll ans=0;

        for(int i=1;i<=n;i++){
            f[i]=f[i-1]+(val[i]-val[a[i]])+(val[i]-val[b[i]]);
            ans+=mp[f[i]];
            mp[f[i]]++;
        }
        cout<<ans<<endl;
    }
    return 0;
}