P16333 [DSDOI Round 1] 邓少分小组题解-171主机测评

P16333 [DSDOI Round 1] 邓少分小组

Link: https://www.luogu.com.cn/problem/P16333

题目背景

邓少是一个学校的老师，他需要给学生分组。

题目描述

具体地，邓少有

$n$ 个学生，编号为

…

1,2,3,\\dots,n

$1, 2, 3, \dots, n$ 。邓少需要选出其中连续的一部分人分组成一个小组，具体地，他需要选出一个区间

[

]

[L,R]

$[L, R]$ ，让编号在

$L$ 到

$R$ 之间的人组成一个小组。

邓少让每个人选出一个喜欢的人，记

A_i

$A_{i}$ 表示编号为

$i$ 的人喜欢的人，邓少要求

$A$ 是一个排列。

同时，邓少给每个人选择了一个伙伴，记

B_i

$B_{i}$ 表示编号为

$i$ 的人的伙伴，邓少保证了

$B$ 是一个排列。

邓少希望能让同学和自己喜欢的人在一组，于是他希望：如果他选择的人的编号区间是

[

]

[L,R]

$[L, R]$ ，那么有

∀

∈

[

]

∈

[

]

\\forall i\\in[L,R],A_i\\in[L,R]

$\forall i \in [L, R], A_{i} \in [L, R]$ 。

同学们希望自己喜欢的人与自己喜欢的人的伙伴在一组，他们希望：如果邓少选择的人的编号区间是

[

]

[L,R]

$[L, R]$ ，那么有

∀

∈

[

]

∈

[

]

\\forall i\\in[L,R],B_{A_i}\\in[L,R]

$\forall i \in [L, R], B_{A_{i}} \in [L, R]$ 。

邓少当然知道同学们的心思，他想知道，有多少种选出一个小组的方式，使得选出的这个小组满足邓少和同学们的要求。

形式化题意

给定一个正整数

$n$ 和两个排列

A,B

$A, B$ ，求有多少个区间

[

]

[L,R]

$[L, R]$ 满足：

$\\forall i\\in[L,R],A_i \\in [L,R] ∀i∈[L,R],Ai∈[L,R]。$
$\\forall i\\in[L,R],B_{A_i} \\in [L,R] ∀i∈[L,R],BAi∈[L,R]。$

输入格式

本题有多组测试数据。

第一行包含一个正整数

$t$ ，表示测试数据组数。

接下来包含

$t$ 组数据，每组数据的格式如下：

第一行包含一个正整数

$n$ ，表示学生数量。

第二行包含

$n$ 个正整数，表示排列

$A$ 。

第三行包含

$n$ 个正整数，表示排列

$B$ 。

输出格式

对于每组测试数据，输出一行，包含一个正整数，表示方案数。

输入输出样例 #1

输入 #1

3
5
1 2 3 4 5
2 3 1 5 4
3
1 2 3
3 2 1
7
6 7 3 5 4 1 2
1 6 3 4 5 2 7

输出 #1

3
2
4

说明/提示

【样例解释】

对于样例一的三组测试数据，符合条件的选取方法分别是：

容易发现没有其他区间满足要求。

【数据范围】

对于所有测试数据，保证：

$\\le T \\le 5 1≤T≤5；$
$\\le n \\le 5 \\times 10^5 1≤n≤5×105；$
给出的

测试点编号

\\le n≤特殊性质

$\\sim 3 1∼3$
$\\sim 6 4∼6$	$10^5 105$
$\\sim 20 7∼20$	$\\times 10^5 5×105$

特殊性质 $A_i=i Ai=i。$

Solution

1. 题意

给定一个正整数

$n$ 和两个排列

A,B

$A, B$ ，求有多少个区间

[

]

[L,R]

$[L, R]$ 同时满足：

条件 $\\forall i\\in[L,R],A_i \\in [L,R] ∀i∈[L,R],Ai∈[L,R]。$
条件 $\\forall i\\in[L,R],B_{A_i} \\in [L,R] ∀i∈[L,R],BAi∈[L,R]。$

2. 分析

95 分做法

题目要求区间

[

]

[L,R]

$[L, R]$ 内所有元素

$i$ 满足

∈

[

]

A_i \\in [L,R]

$A_{i} \in [L, R]$ 且

∈

[

]

B_{A_i} \\in [L,R]

$B_{A_{i}} \in [L, R]$ 。此条件可等价转化为

min

⁡

∈

[

]

{

min

⁡

(

)

}

≥

∧

max

⁡

∈

[

]

{

max

⁡

(

)

}

≤

\\min_{i \\in [L,R]} \\{\\min(A_i, A_{B_i})\\} \\ge L \\quad \\land \\quad \\max_{i \\in [L,R]} \\{\\max(A_i, A_{B_i})\\} \\le R

$i \in [L, R] min {min (A_{i}, A_{B_{i}})} \geq L \land i \in [L, R] max {max (A_{i}, A_{B_{i}})} \leq R$

由于

A,B

$A, B$ 不含重复元素，因此上面的公式会自然倒逼两者取遍

[

]

[L,R]

$[L, R]$ 范围的所有整数。这是一个充要条件。

到这里，容易想到的办法是采用分治策略，取区间

[

]

[l, r]

$[l, r]$ 的中间，分成两半，分别考虑左半边、右半边以及“横跨”的情况。然后你就会发现自己喜提 95 分，在最后一个测试点超时了，甚至还是 1.03 秒，恰好差一点的这种，属实能让不少人心态爆炸。

为什么？

原因也很简单，上面思路中，分治的壳子会产生对数的时间复杂度，里面的排序、建立树状数组等操作又是

(

log

⁡

)

O(n\\log n)

$O (n lo g n)$ 的时间复杂度，因此全局的时间复杂度是

(

log

⁡

)

O(n\\log ^2 n)

$O (n lo g^{2} n)$ ，对于

5\\times 10^5

$5 \times 1 0^{5}$ 的数据规模而言非常悬；同时外面的常数

$T$ 会让情况雪上加霜。

一份 95 分代码样例

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 500005;
int n, A[MAXN], B[MAXN], C[MAXN], mn[MAXN], mx[MAXN];
int bit[MAXN];

inline long long NextInt()
{
long long x = 0; char ch = getchar(); bool f = 0;
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
if (f) return –x; return x;
}

inline void Print(long long x)
{
if (x < 0) putchar('-'), x = –x;
if (x > 9) Print(x / 10);
putchar(x % 10 + '0');
}

inline void add(int x, int v)
{
for (; x <= n; x += x & –x) bit[x] += v;
}

inline int query(int x)
{
int s = 0;
for (; x > 0; x -= x & –x) s += bit[x];
return s;
}

inline int query(int l, int r)
{
if (l > r) return 0;
return query(r) – query(l – 1);
}

int mn_l[MAXN], mx_l[MAXN], mn_r[MAXN], mx_r[MAXN];

ll divide(int l, int r)
{
if (l == r) return (mn[l] >= l && mx[l] <= l);
int mid = (l + r) >> 1;
ll res = divide(l, mid) + divide(mid + 1, r);

mn_l[mid] = mn[mid]; mx_l[mid] = mx[mid];
for (int i = mid – 1; i >= l; i—)
{
mn_l[i] = min(mn_l[i + 1], mn[i]);
mx_l[i] = max(mx_l[i + 1], mx[i]);
}
mn_r[mid + 1] = mn[mid + 1]; mx_r[mid + 1] = mx[mid + 1];
for (int i = mid + 2; i <= r; i++)
{
mn_r[i] = min(mn_r[i – 1], mn[i]);
mx_r[i] = max(mx_r[i – 1], mx[i]);
}

vector<pair<int, int>> pts;
pts.reserve(r – mid);
for (int j = mid + 1; j <= r; j++)
{
if (mx_r[j] <= j) pts.push_back({mn_r[j], j});
}
sort(pts.rbegin(), pts.rend());

int pt = 0, sz = pts.size();
for (int i = mid; i >= l; i—)
{
if (mn_l[i] < i) continue;
int L_bound = max(mid + 1, mx_l[i]);
if (L_bound > r) continue;

int threshold = i;
while (pt < sz && pts[pt].first >= threshold)
{
add(pts[pt].second, 1);
pt++;
}
res += query(L_bound, r);
}
for (int k = 0; k < pt; k++)
{
add(pts[k].second, –1);
}
return res;
}

void solve()
{
n = NextInt();
for (register int i = 1; i <= n; i++) A[i] = NextInt();
for (register int i = 1; i <= n; i++) B[i] = NextInt();
for (register int i = 1; i <= n; i++) C[i] = B[A[i]];
for (register int i = 1; i <= n; i++)
{
mn[i] = min(A[i], C[i]);
mx[i] = max(A[i], C[i]);
}
Print(divide(1, n));
putchar(10);
}

int main()
{
int t = NextInt();
while (t—) solve();
}

100 分做法

回到题目的条件，既然

A,B

$A, B$ 是排列，那么

$A$ 中的元素互不相同，进而将这些

A_i

$A_{i}$ 作为下标时，

B_{A_i}

$B_{A_{i}}$ 一定也互不相同。

重新审视一下题意：

条件

1

1

$1$ ：

∀

i

∈

[

L

,

R

]

,

A

i

∈

[

L

,

R

]

\\forall i\\in[L,R],A_i \\in [L,R]

$\forall i \in [L, R], A_{i} \in [L, R]$ 。
条件

2

2

$2$ ：

∀

i

∈

[

L

,

R

]

,

B

A

i

∈

[

L

,

R

]

\\forall i\\in[L,R],B_{A_i} \\in [L,R]

$\forall i \in [L, R], B_{A_{i}} \in [L, R]$ 。

翻译成大白话就是对于原数组及其变换

\\sigma_A,\\sigma_B

$σ_{A}, σ_{B}$ ，有多少子区间经过这两次变换后，依然是子区间的排列，没有出现不在这个子区间范围内的元素。

“子区间是不是排列”的问题催生我们产生前缀和+扫描的思路求解。容易想到的办法是对于区间

[

]

[L,R]

$[L, R]$ ，判断下面的两个条件是否同时成立即可

∑

(

−

)

∧

∑

(

−

)

\\sum_{k=L}^R(A_i – i) = 0 \\quad \\land \\quad \\sum_{k=L}^R(B_{A_i} – i) = 0

$k = L \sum R (A_{i} - i) = 0 \land k = L \sum R (B_{A_{i}} - i) = 0$

这也是 @Cifera_meow 在 ta 的题解里提到的，ta 说的容易被 hack 的言下之意是，求和运算的线性性质使得上面的条件只是题目要求的必要不充分条件。

那么我们只要利用哈希和随机化操作尽可能破坏掉上面提到的线性规律性，就能有很大把握设计出可靠，时间复杂度为

(

)

O(n)

$O (n)$ 的算法。

设哈希函数为

r_A,r_B

$r_{A}, r_{B}$ ，则条件转化为

∑

(

)

−

(

)

∧

∑

(

)

−

(

)

\\sum_{i=L}^R(r_A(A_i) – r_A(i)) = 0 \\quad \\land \\quad \\sum_{i=L}^R(r_B(B_{A_i}) – r_B(i)) = 0

$i = L \sum R (r_{A} (A_{i}) - r_{A} (i)) = 0 \land i = L \sum R (r_{B} (B_{A_{i}}) - r_{B} (i)) = 0$

之所以只是说“有很大把握”，是因为这其实依然是必要不充分条件，但是在哈希操作（尤其是如果是自己写的哈希函数）的加持下，“被 hack”的概率已经微乎其微。

上述条件转换为

∑

(

)

(

)

−

(

)

−

(

)

\\sum_{i=L}^R \\Big( r_A(A_i) + r_B(B_i) – r_A(i) – r_B(i) \\Big) = 0

$i = L \sum R (r_{A} (A_{i}) + r_{B} (B_{i}) - r_{A} (i) - r_{B} (i)) = 0$

于是我们只要定义一个新的数列

{

}

\\{D_i\\}

${D_{i}}$ 满足

∀

⋯

(

)

(

)

−

(

)

−

(

)

\\forall i = 1,2,\\cdots, n, \\quad D_i = r_A(A_i) + r_B(B_i) – r_A(i) – r_B(i)

$\forall i = 1, 2, \dots, n, D_{i} = r_{A} (A_{i}) + r_{B} (B_{i}) - r_{A} (i) - r_{B} (i)$

并定义前缀和

∑

S_k = \\sum_{i=1}^k D_i

$S_{k} = \sum_{i = 1}^{k} D_{i}$ （特别的，

S_0=0

$S_{0} = 0$ ），则区间合法等价于

−

S_R = S_{L-1}

$S_{R} = S_{L - 1}$ 。

对数组

{

}

\\{D_i\\}

${D_{i}}$ 进行扫描，统计前缀和为零的区段即可。

// 为两个数组生成随机 id
for (int i = 1; i < MAXN; ++i)
{
rnda[i] = dist(rng);
rndb[i] = dist(rng);
}

// 前缀和 & 哈希表统计
ll cnt = 0, ans = 0;
mp[0] = 1; // P_0 = 0，记录初始状态
for (int i = 1; i <= n; ++i) // 扫描数组累加答案
{
cnt += rnda[a[i]] + rndb[b[i]] – rnda[i] – rndb[i]; // 维护 S[i]
auto it = mp.find(cnt);
if (it != mp.end())
{
ans += it->second; // 记录此前出现过的次数，就是新增的合法区间数
it->second++;
}
else
{
mp[cnt] = 1;
}
}

3. 代码

C++ 23

#include <cstdio>
#include <vector>
#include <unordered_map>
#include <random>
#include <chrono>

using ll = long long;
const int MAXN = 500005;
ll rnda[MAXN], rndb[MAXN];

inline ll read()
{
ll x = 0;
int c = getchar();
while (c <= 32) c = getchar();
bool neg = false;
if (c == '-') { neg = true; c = getchar(); }
while (c >= '0' && c <= '9') {
x = x * 10 + (c – '0');
c = getchar();
}
return neg ? –x : x;
}

struct custom_hash
{
static uint64_t splitmix64(uint64_t x)
{
x += 0x1145141919810666;
x = (x ^ (x >> 30)) * 0xF426F426F426F426;
x = (x ^ (x >> 27)) * 0x00AC337500AC3375;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const
{
static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};

int main()
{
std::mt19937_64 rng(0xF426);
std::uniform_int_distribution<ll> dist(1, 100000000000000LL);
for (int i = 1; i < MAXN; ++i) {
rnda[i] = dist(rng);
rndb[i] = dist(rng);
}

int t = (int)read();
while (t—)
{
int n = (int)read();
std::vector<ll> a(n + 1), b(n + 1);
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = 1; i <= n; ++i) b[i] = read();

std::unordered_map<ll, int, custom_hash> mp;
mp.reserve(n * 2);
mp[0] = 1;

ll cnt = 0, ans = 0;
for (int i = 1; i <= n; ++i)
{
cnt += rnda[a[i]] + rndb[b[i]] – rnda[i] – rndb[i];
auto it = mp.find(cnt);
if (it != mp.end())
{
ans += it->second;
it->second++;
}
else
{
mp[cnt] = 1;
}
}
printf("%lld\\n", ans);
}
return 0;
}

C#

不得不承认 C# Mono 环境相较于 Microsoft 官方的 .NET 还是显得太破旧了（隔壁的 CF 和 AT 都换上 .NET 7+ 了），Mono 的随机器甚至不支持生成

$64$ 位随机整数以及 BigInteger。

不过就本题而言，我们可以用 Mono 随机器的随机浮点数（生成一个

[

)

[0,1)

$[0, 1)$ 范围的伪随机浮点数）来作为其替代品。

考虑双精度浮点数的机制，包含

$11$ 位阶码、

$52$ 位尾码还有一个符号位。既然浮点数本质上是在用一系列

$2$ 的幂次尽可能“凑”出一个小数，那么我们只要将这个

[

)

[0,1)

$[0, 1)$ 范围的随机浮点数乘以

(

9007199254740992

)

2^{53}(=9007199254740992)

$2^{53} (= 9007199254740992)$ ，就能得到不会引入浮点误差的随机大范围整数。如此一来这个随机化操作的质量肯定是会略逊于 C++ 的，但是对于本题依然够用。

如果直接乘以

10^{12}

$1 0^{12}$ 之类的数再转化为

$64$ 位整型，反而会因为浮点误差等因素导致 WA 掉两个测试点。

using System;
using System.Collections.Generic;
using System.IO;

class P16333
{
static long[] rnda = new long[500005];
static long[] rndb = new long[500005];

static readonly byte[] buffer = new byte[1 << 16];
static int pos = 0, len = 0;
static readonly Stream input = Console.OpenStandardInput();

static int ReadByte()
{
if (pos >= len)
{
pos = 0;
len = input.Read(buffer, 0, buffer.Length);
if (len == 0) return –1;
}
return buffer[pos++];
}

static long ReadLong()
{
long x = 0;
int c = ReadByte();
while (c <= 32) c = ReadByte();
bool neg = false;
if (c == '-') { neg = true; c = ReadByte(); }
while (c >= '0' && c <= '9')
{
x = x * 10 + (c – '0');
c = ReadByte();
}
return neg ? –x : x;
}

static void Main()
{
var rng = new Random(42);
for (int i = 1; i < 500005; i++)
{
rnda[i] = (long)(rng.NextDouble() * 9007199254740992L);
rndb[i] = (long)(rng.NextDouble() * 9007199254740992L);
}

int t = (int)ReadLong();
var sw = new StreamWriter(Console.OpenStandardOutput());
sw.AutoFlush = true;

while (t— > 0)
{
int n = (int)ReadLong();
long[] a = new long[n + 1];
long[] b = new long[n + 1];
for (int i = 1; i <= n; i++) a[i] = ReadLong();
for (int i = 1; i <= n; i++) b[i] = ReadLong();

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