Znzryb's Blog

Leetcode 3721. 最长平衡子数组 II（最大后缀和，最小后缀和线段树）

Posted on 2026-02-12 Edited on 2026-02-14

题目大意

给你一个整数数组 nums。

如果子数组中 不同偶数 的数量等于 不同奇数 的数量，则称该 子数组 是 平衡的 。

返回最长平衡子数组的长度。

子数组 是数组中连续且非空的一段元素序列。

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

思路讲解

https://leetcode.cn/problems/longest-balanced-substring-ii/description/?envType=daily-question&envId=2026-02-13

其实这种平衡子串类似的问题，都是枚举右维护左。就是我们先确定了结尾，然后要去比较快速的找到开头，那么像这道，上面这道题目也是一样的。

这道题目维护左是采用的是线段数二分，使用线段数二分，在知道右边的情况下去找到左边。这该线段树需要维护区间，其实就是该线段树需要~~维护最大子段和~~和~~最小子段和~~。该线段树需要能够支持查询区间最大子段和和最小子段和。

不过我们仔细细想以后发现，应该这道题目维护的是最大后缀和和最小后缀和。实际上我们使用小白逛公园的线段树也可以维护最大后缀和和最小后缀和。

为什么要维护最大子段和和最小子段和呢？它实际上是这样子，它首先是把奇数变成一，偶数变成负一。当然都是最右边的那个值啊，奇数变成一，偶数变成负一。然后如果说我们知道了这一段的最大子段和是多少，最小子段和是多少，那么其实这一段的子段和是否有零？

显然，暴力解法无法满足时间要求，我们需要找到一个时间复杂度较低的方法来快速找到最长平衡子数组，于是我想到了线段树，通过区间修改和快速查询，可以实现时间复杂度O(N log N)。

那么如何用线段树快速找到最长平衡子数组呢，我们可以规定，如果数字是偶数+1，反之，如果是奇数-1。那这个问题就转换为，我们要找到 区间和 为0 的最长子区间长度。

但题目还有一个数字去重的要求，如果数字相同，则不能重复计算贡献，那我们可以这么想：

换句话说，我更新区间和的时候，只从 j 点更新到上一次这个数字出现前的位置（也就是图中1的位置），再往后这个数字就不能贡献计数了。

好了，线段树构造好了，那如何快速找到区间和为 0 的子区间呢？由于这个线段树没有单调性，如果用朴素的方法，我们可能需要遍历整棵树，复杂度来到了O(N)，不符合要求，解决方法是，采取Min/Max 剪枝策略，具体如下：在每个节点除了记录区间和，还要记录区间最大和 Max 和区间最小和 Min，并在寻找区间和为 0 的时候做以下判断：

这样，就像走迷宫有了导航，复杂度可以下降到 O(Log N) :

以下为具体线段树更新和查找步骤图示：

回顾一下线段树算法的核心流程：

AC代码

源代码

// 线段树节点
type Node struct {
	Min int // 区间内的最小值
	Max int // 区间内的最大值
}

// 全局变量，避免传参过多
var (
	tree []Node
	lazy []int
	n    int
)

// 初始化线段树
func build(node, start, end int) {
	if start == end {
		tree[node] = Node{0, 0}
		return
	}
	mid := (start + end) / 2
	build(2*node, start, mid)
	build(2*node+1, mid+1, end)
	tree[node] = Node{0, 0} // 初始全为0
}

// 下推懒标记
func pushDown(node int) {
	if lazy[node] != 0 {
		lazy[2*node] += lazy[node]
		tree[2*node].Min += lazy[node]
		tree[2*node].Max += lazy[node]

		lazy[2*node+1] += lazy[node]
		tree[2*node+1].Min += lazy[node]
		tree[2*node+1].Max += lazy[node]

		lazy[node] = 0
	}
}

// 区间更新
func update(node, start, end, l, r, val int) {
	if l > end || r < start {
		return
	}
	if l <= start && end <= r {
		tree[node].Min += val
		tree[node].Max += val
		lazy[node] += val
		return
	}
	pushDown(node)
	mid := (start + end) / 2
	update(2*node, start, mid, l, r, val)
	update(2*node+1, mid+1, end, l, r, val)
	
	// 更新当前节点的最值
	tree[node].Min = min(tree[2*node].Min, tree[2*node+1].Min)
	tree[node].Max = max(tree[2*node].Max, tree[2*node+1].Max)
}

// 带有范围限制的查询
func queryRangeZero(node, start, end, L, R int) int {
	// 区间无交集
	if start > R || end < L {
		return -1
	}
	// 剪枝
	if tree[node].Min > 0 || tree[node].Max < 0 {
		return -1
	}
	if start == end {
		if tree[node].Min == 0 {
			return start
		}
		return -1
	}
	
	pushDown(node)
	mid := (start + end) / 2
	
	res := queryRangeZero(2*node, start, mid, L, R)
	if res != -1 {
		return res
	}
	return queryRangeZero(2*node+1, mid+1, end, L, R)
}

func longestBalanced(nums []int) int {
    n = len(nums)
	if n == 0 {
		return 0
	}

	// 初始化线段树大小 (4 * n)
	tree = make([]Node, 4*n)
	lazy = make([]int, 4*n)
	build(1, 0, n-1)

	lastPos := make(map[int]int) // 记录元素上一次出现的位置
	maxLen := 0

	for i := 0; i < n; i++ {
		val := nums[i]
		
		// 获取该元素上一次出现的位置，如果没有则视为 -1
		prev, exists := lastPos[val]
		if !exists {
			prev = -1
		}
		
		// 确定更新方向：偶数+1，奇数-1
		diff := 0
		if val%2 == 0 {
			diff = 1
		} else {
			diff = -1
		}
		
		// 核心逻辑：只更新 (上一次出现位置, 当前位置] 这个范围
		// 这意味着对于在这个范围内的起始点 start，nums[i] 是一个新的 distinct 元素
		update(1, 0, n-1, prev+1, i, diff)
		
		// 记录位置
		lastPos[val] = i
		
		firstZeroIndex := queryRangeZero(1, 0, n-1, 0, i)
		if firstZeroIndex != -1 {
			currentLen := i - firstZeroIndex + 1
			if currentLen > maxLen {
				maxLen = currentLen
			}
		}
	}

	return maxLen
}

心路历程（WA，TLE，MLE……）

Int 和 Long long 的循环变量类型性能基准测试

Posted on 2026-02-12 Edited on 2026-02-13

使用 int integer 作为循环变量类型和使用 long long 作为循环变量类型，这个速度几乎是一模一样的。所以之后可你可以这个，之后我们就用 long long 吧，避免这个溢出风险。

https://quick-bench.com/q/QWglJiYzyTVmjjHDhioI4S2UDOk

#include <benchmark/benchmark.h>
#include <cstdint>

constexpr int N = 100000000;

static void BM_loop_int(benchmark::State& state) {
    for (auto _ : state) {
        std::uint64_t acc = 0;
        for (int i = 0; i < N; ++i) {
            acc += (unsigned)i;
        }
        benchmark::DoNotOptimize(acc);
    }
}
BENCHMARK(BM_loop_int);

static void BM_loop_ll(benchmark::State& state) {
    for (auto _ : state) {
        std::uint64_t acc = 0;
        for (long long i = 0; i < (long long)N; ++i) {
            acc += (unsigned)i;
        }
        benchmark::DoNotOptimize(acc);
    }
}
BENCHMARK(BM_loop_ll);

The 2025 ICPC 德国 German Collegiate Programming Contest——F. Fair and Square

Posted on 2026-02-12 Edited on 2026-02-13

题目大意

题目背景
Felix 的生日派对上，一张 $H \times W$ 的矩形披萨被客人吃掉了一些部分，剩下的部分由若干 $1 \times 1$ 的正方形单元格组成。

题目描述
给出一个 $H \times W$ 的网格，其中字符 # 表示剩下的披萨块，. 表示已经被吃掉（空缺）的部分。
你需要将所有剩下的披萨块（#）划分成若干个边长为 $k$ 的正方形区域。
要求：

每个划分出的正方形必须完全由 # 组成。
所有 # 必须被恰好覆盖一次（不能重叠，不能遗漏）。
只能沿网格线切割。
划分出的所有正方形边长必须相等。

求满足上述条件的最大边长 $k$ 。

输入格式
第一行包含两个整数 $H$ 和 $W$ ( $1 \le H, W \le 2500$ )，表示网格的高度和宽度。
接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串，由 # 和 . 组成。
保证输入中至少包含一个 #。

输出格式
输出一个整数，表示最大的可行边长 $k$ 。

样例 1

Input
4 7
####...
####.##
.######
.####..

Output
2

样例 1 解释
对于第一个样例，最大边长为 2。
剩下的披萨块可以被划分为 5 个 $2 \times 2$ 的正方形，其左上角坐标 $(r, c)$ 分别为： $(0,0), (0,2), (1,5), (2,1), (2,3)$ 。
所有 # 均被这 5 个正方形不重不漏地覆盖。

这道题说白了其实意思很简单，就是井号的地方代表就是披萨，然后你要把披萨切成正方形的，大小相同的块，问这些切出来的正方形块的最大边长是多少？

样例 2

Input
3 5
#####
#####
###..

Output
1

样例 3

Input
3 5
.##..
#####
##.##

Output
1

样例 4

Input
5 13
....###......
....###..###.
.######..###.
.###.....###.
.###.........

Output
3

思路讲解

首先呢我们还是要想到啊，就是我我们首先还是要想到一个算法，能够判定在此边长下能否切割出这样子的东西啊。

这个算法的时间复杂度就是 $O (H \times W)$ 就行，可以了。

这算法其实很简单，也不需要前缀和啊什么之类的。其实只需要一个贪心即可。就说白了，最上面的那个点，最上面最左边的那个点，或者你倒过来做最最左边最上面的那个点。你不放一个正方形在上面，就不以这个正方形，不放一个正方形在这里的话，没有正方形可以覆盖这个点，所以这里必须放一个正方形。就这个披萨点。必须放一个正方形。那么你放了这，放下去这个正正方形以后，你就判断一下这个正方形会不会和其他你放的正方形重叠，啊什么之类的就行了。说白了就是一个贪心。

auto check=[&](ll len) -> bool {
      ++tim;
      for (ll i=1;i<=N;++i) {
          for (ll j=1;j<=M;++j) {
              if (vis[i][j]>=tim) continue;
              if (maze[i][j]=='#') {
                  if (i+len-1>N) {
                      return false;
                  }
                  if (j+len-1>M) {
                      return false;
                  }
                  for (ll x=i;x<i+len;++x) {
                      for (ll y=j;y<j+len;++y) {
                          if (maze[x][y]!='#') {
                              return false;
                          }
                          if (vis[x][y]>=tim) {
                              return false;
                          }
                          vis[x][y]=tim;
                      }
                  }
              }
          }
      }
      return true;
  };

现在问题就来到什么呢？就是我不可能枚举2500次是吧？枚举2500次就超了。那我怎么样枚举的次数少一点？我其实就加一个非常简单的一个判定即可。它 cnt 的因数数量肯定是根号下 cnt，也就是数量级是2500。又因为 i 乘 i 才是才能组成 cnt 的一个因数，所以实际上 i 只有50的量级。

for (ll i=min(N,M);i>=2;--i) {
    if (cnt%(i*i)!=0) {
        continue;
    }
    if (check(i)) {
        cout<<i<<"\n";
        return;
    }
}
cout<<1<<"\n";

AC代码

AC
https://codeforces.com/gym/106129/submission/362620886

源代码

/**
 * Problem: F. Fair and Square
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106129/problem/F
 * Created: 2026-02-11 17:46:33
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
//  minp[i] 存储的是i的最小素因数
// https://www.luogu.com.cn/record/221554377
vector<ll> minp,primes;
void sieve(ll n){
    minp.assign(n+5,0);
    // minp[1]=1;  // 加了这句话可能把 1 误判成素数，要小心
    for(int i=2;i<=n;++i){
        if(minp[i]==0){		// 是素数
            minp[i]=i;
            primes.push_back(i);
        }
        for(auto p:primes){
            if(i*p>n){	// 超范围了
                break;
            }
            minp[i*p]=p;
            // 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
            // i * p_next = (p * k) * p_next 最小的应该是p
            if(p==minp[i]){
                break;
            }
        }
    }
}

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<char>> maze(N+2,vector<char>(M+2));
    ll cnt=0;
    for (ll x=1;x<=N;++x) {
        for (ll y=1;y<=M;++y) {
            cin>>maze[x][y];
            if (maze[x][y]=='#') {
                ++cnt;
            }
        }
    }
    int tim=0;
    vector<vector<int>> vis(N+2,vector<int>(M+2));
    auto check=[&](ll len) -> bool {
        ++tim;
        for (ll i=1;i<=N;++i) {
            for (ll j=1;j<=M;++j) {
                if (vis[i][j]>=tim) continue;
                if (maze[i][j]=='#') {
                    if (i+len-1>N) {
                        return false;
                    }
                    if (j+len-1>M) {
                        return false;
                    }
                    for (ll x=i;x<i+len;++x) {
                        for (ll y=j;y<j+len;++y) {
                            if (maze[x][y]!='#') {
                                return false;
                            }
                            if (vis[x][y]>=tim) {
                                return false;
                            }
                            vis[x][y]=tim;
                        }
                    }
                }
            }
        }
        return true;
    };
    for (ll i=min(N,M);i>=2;--i) {
        if (cnt%(i*i)!=0) {
            continue;
        }
        if (check(i)) {
            cout<<i<<"\n";
            return;
        }
    }
    cout<<1<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif
    sieve(2600);
    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106129/submission/362620886

*/

心路历程（WA，TLE，MLE……）

https://qoj.ac/submission/2030500

出问题的代码

/**
 * Problem: F. Fair and Square
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106129/problem/F
 * Created: 2026-02-11 17:46:33
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<char>> maze(N+2,vector<char>(M+2));
    for (ll x=1;x<=N;++x) {
        for (ll y=1;y<=M;++y) {
            cin>>maze[x][y];
        }
    }
    int tim=0;
    vector<vector<int>> vis(N+2,vector<int>(M+2));
    auto check=[&](ll len) -> bool {
        ++tim;
        for (ll i=1;i<=N;++i) {
            for (ll j=1;j<=M;++j) {
                if (vis[i][j]>=tim) continue;
                if (maze[i][j]=='#') {
                    if (i+len-1>N) {
                        return false;
                    }
                    if (j+len-1>M) {
                        return false;
                    }
                    for (ll x=i;x<i+len;++x) {
                        for (ll y=j;y<j+len;++y) {
                            if (maze[x][y]!='#') {
                                return false;
                            }
                            if (vis[x][y]>=tim) {
                                return false;
                            }
                            vis[x][y]=tim;
                        }
                    }
                }
            }
        }
        return true;
    };
    ll ans=1;
    for (ll len=2;len*len<=max(N,M);++len) {
        if (check(len)) {
            ans*=len;
        }
    }
    ans=min(ans,min(N,M));
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

*/

上面这个代码的问题是出在哪里呢？首先第一啊，就是这个因数啊，你直接乘起来，它去找这个最大，其实是不大对的。那么在 m 比较小的情况下，不如直接倒序遍历 m ，然后检验这个 m 的所有的素因数。是否全部都在我们可以凑出来的素因数集合之中。

不过后面我们发现更加大的问题，就是它这个道题目，它其实并不符合说有这个因数，然后我们乘，然后它就能够合在一起，即只要素因数合法，那么所凑出来的合数也合法，这其实是不对的，它们乘起来的合数是不一定合法的。其实很简单吧，就是边长为2和边长为3是没有反例的（即满足边长为2和满足边长为3，在不限制这个长度的情况下，应该是有满足边长为6的解决方案）。这个状况，让我们造成了一些错觉，以为说这个其实是可以乘的。但实际上不是这样子的。**满足边长为2，那一定满足边长为4吗？**一定满足边长为8吗？你看它这个2，它可以乘，它，但是它乘上去它就不一定对了。

CF-1079-B. Array and Permutation

Posted on 2026-02-11 Edited on 2026-02-13

题目大意

给定一个长度为 $n$ 的排列 $p$ 和一个长度为 $n$ 的数组 $a$ 。

你可以进行任意次操作，每次操作选择一个下标 $i$ （ $1 \le i < n$ ），然后执行以下两种之一：

把 $p_i$ 的值覆盖为 $p_{i+1}$ （即 $p_i := p_{i+1}$ ）
把 $p_{i+1}$ 的值覆盖为 $p_i$ （即 $p_{i+1} := p_i$ ）

也就是说，每次选两个相邻元素，把其中一个的值复制到另一个上。

判断是否能通过若干次操作，把排列 $p$ 变成数组 $a$ 。

样例解释：

第一组： $p = [1, 2, 3]$ ， $a = [1, 2, 2]$ 。选 $i = 2$ ，把 $p_2$ 的值复制到 $p_3$ ，得到 $[1, 2, 2]$ ，与 $a$ 相同，输出 YES。

第二组： $p = [3, 1, 2, 4]$ ， $a = [3, 4, 2, 2]$ ，无论如何操作都无法得到 $a$ ，输出 NO。

第三组： $p = [1, 3, 2, 5, 4]$ ， $a = [3, 3, 3, 5, 4]$ 。先选 $i = 1$ ，把 $p_2$ 的值复制到 $p_1$ ，得到 $[3, 3, 2, 5, 4]$ ；再选 $i = 2$ ，把 $p_2$ 的值复制到 $p_3$ ，得到 $[3, 3, 3, 5, 4]$ ，与 $a$ 相同，输出 YES。

思路讲解

使用类似于双指针的做法，判断这个 A 数组是去重以后是否是 P 数组 P 排列的子序列。具体来说，在实现当中，我们是使用 P 排列去对应 A 的这个数组，去对应 A 数组，就是你可以理解为我们用一个 PI 去消 AJ 去消 A 数组中的元素，那么这个 pi 当然是可以一直消一直消，可以消除连续的 aj 的元素，只要 aj 和 pi 相等，连续的相等就可以。但是 pi 一旦遇到了第一个和自己不相等的 aj 就会停下来。

void Solve() {
    ll N;
    cin >> N;
    vector<ll> P(N+2),A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>P[i];
    }
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    ll bp=1;
    for (ll i=1;i<=N;++i) {
        bool isbreak=false;
        for (ll j=bp;j<=N;++j) {
            if (P[i]!=A[j]) {
                bp=j;
                isbreak=true;
                break;
            }
        }
        if (!isbreak) {
            bp=N+1;
        }
    }
    if (bp==N+1) {
        cout<<"YES\n";
    }else {
        cout<<"NO\n";
    }
}

AC代码

AC
https://codeforces.com/contest/2197/submission/362443575

源代码

/**
 * Problem: B. Array and Permutation
 * Contest: Codeforces Round 1079 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2197/problem/B#
 * Created: 2026-02-11 23:03:41
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> P(N+2),A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>P[i];
    }
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    ll bp=1;
    for (ll i=1;i<=N;++i) {
        bool isbreak=false;
        for (ll j=bp;j<=N;++j) {
            if (P[i]!=A[j]) {
                bp=j;
                isbreak=true;
                break;
            }
        }
        if (!isbreak) {
            bp=N+1;
        }
    }
    if (bp==N+1) {
        cout<<"YES\n";
    }else {
        cout<<"NO\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2197/submission/362443575


*/

心路历程（WA，TLE，MLE……）

CF-1079-D. Another Problem about Beautiful Pairs

Posted on 2026-02-11 Edited on 2026-02-13

题目大意

在数组 $a$ 中，如果满足以下条件，我们称索引对 $i$ , $j$ 为美丽的：

$a_{i} \cdot a_{j} = j - i$ 。

统计数组 $a$ 中美丽对的数量。

思路讲解

使用比较聪明的暴力去枚举这个点，对呀。去枚枚举 X 和 Y 那么枚举 X Y 其实它是 N log N 的，实际上是。这应该也是一个经典结论了，可以使用调和级数证明，应该是。枚举 X 和 Y 以后呢，实际上就非常简单了。就是因为我们已经枚举出来，枚举出来以后，我们只需要验证一下这个数组当中有没有这样子的 X 和 Y 。我们可以选择去遍历 X 所有的位置，然后遍历到 X 位置以后我们直接去检验应该有 Y 的那个地方是不是一个 Y 如果是 Y 的话，我们就给这个答案加一。

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    vector<vector<ll>> val_pos_mtx(N+2);
    for (int i=1;i<=N;++i) {
        if (A[i]<=N) {
            val_pos_mtx[A[i]].push_back(i);
        }
    }
    ll ans=0;
    for (ll x=1;x<=N;++x) {
        if (val_pos_mtx[x].empty()) continue;
        for (ll y=1;y<=N/x;++y) {
            if (val_pos_mtx[y].empty()) continue;
            ll mul=x*y;
            for (auto i:val_pos_mtx[x]) {
                ll j=i+mul;
                if (j<=N && A[j]==y) {
                    ++ans;
                }
            }
        }
    }
    cout<<ans<<"\n";
}

AC代码

https://codeforces.com/contest/2197/submission/362477014

源代码

/**
 * Problem: D. Another Problem about Beautiful Pairs
 * Contest: Codeforces Round 1079 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2197/problem/D
 * Created: 2026-02-11 23:14:12
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    vector<vector<ll>> val_pos_mtx(N+2);
    for (int i=1;i<=N;++i) {
        if (A[i]<=N) {
            val_pos_mtx[A[i]].push_back(i);
        }
    }
    ll ans=0;
    for (ll x=1;x<=N;++x) {
        if (val_pos_mtx[x].empty()) continue;
        for (ll y=1;y<=N/x;++y) {
            if (val_pos_mtx[y].empty()) continue;
            ll mul=x*y;
            for (auto i:val_pos_mtx[x]) {
                ll j=i+mul;
                if (j<=N && A[j]==y) {
                    ++ans;
                }
            }
        }
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*


*/