洛谷 P2757 [国家集训队] 等差子序列

背景

不知道想干啥，只是脑海中的绘图仍在回荡…
等差子序列题解，开讲…

---

正解(线段树、哈希)

• 只要存在长度为 $3$ 的子序列就行

• 中间项特殊，考虑枚举 $i=1\to n$，让 $a_i$ 作为中间项。发现由于是$1\to n$ 的排列，所以如果 $x$ 没有出现在 $a_i$ 的左侧，那么一定出现在 $a_i$ 的右侧。

• 如果存在一个 $k$，使得 $a_i-k$ 在 $a_i$ 左侧，$a_i+k$ 在 $a_i$ 右侧，那么就有解了。也就是说，在从左到右扫到 $a_i$ 时，$a_i-k$ 和 $a_i+k$ 不能都出现，也不能都不出现。

• 考虑一个长度为 $n$ 的 $01$数组 $b$，$b_j=0$ 表示 $j$ 还没有出现，$b_j=1$表示已经出现。那么只需看 $b$ 数组在以 $a_i$ 为中心下的回文半径长度就行了。可以用哈希判断。

• 由于需要单点修改，区间查询哈希值，所以用线段树就行了。

先来解释一下题意:对于一串数列，存在长度为 $3$ 的等差子序列就输出 “Y”，否则是 “N”。

很简明的题意，倒是如此折磨人…

1 2 3
4 5 6
6 4 2
-8 -9 -10

以上都是长度为 $3$ 的等差子序列，查找这些序列即可。
问题是怎样查找。

可以简单计算两两之间的差值，保证这差值相等即可，很简单的证明。
对于三个数$a$，$b$，$c$，满足 $b-a=c-b$，即 $c=2b-a$。

鉴于要求两种差值，还得先判 $3$ 个元素，哈希冲突可不是你能惹的，不得不使用双哈希。单哈希错死我咯，取了好多模数

选择取两种哈希，一种正向，一种反向。(一个从左到右计算哈希值，一个从右到左)

利用线段树的节点维护 $[l,r]$的哈希值，$ls$和$rs$数组存储左右节点，节点哈希值通过子节点哈希值拼接计算。(就像字符串哈希区间合并一样)

然后就是初始化，在这上面费了老遭。尤其是合并的时候初始化ls和rs数组。

哈希得有基数，这里用一个数组 $qpow[N][N]$ 记录幂次更准确些。

inline void pre(){qpow[0] = 1;for(int i = 1; i < N; ++i)  qpow[i] = qpow[i-1]*b;
}

然后是子节点的处理:

• 正向哈希模拟从左到右的字符串拼接，左子树哈希需乘以右子树长度的基数幂
• 反向哈希模拟从右到左的字符串拼接，右子树哈希需乘以左子树长度的基数幂
• 该操作确保线段树节点的哈希值能正确表示区间内所有元素的存在性

$$\{\begin{array}{l}正向哈希：左子树哈希\ast 右子树长度的基数幂+右子树哈希\\ 反向哈希：右子树哈希\ast 左子树长度的基数幂+左子树哈希\end{array}$$

inline void update(int t){sum[t][0] = sum[ls[t]][0]*qpow[rr[rs[t]]-ll[rs[t]]+1]+sum[rs[t]][0];sum[t][1] = sum[rs[t]][1]*qpow[rr[ls[t]]-ll[ls[t]]+1]+sum[ls[t]][1];ll[t] = ll[ls[t]], rr[t] = rr[rs[t]];
}

接下线段树的构建与修改：

• 构建时初始化叶子节点哈希值为 1 (表示 1 到 N 的元素初始存在)
• 进行合并操作时将指定位置的哈希值置 0 (标记元素已被使用)
• 每次修改后递归更新父节点哈希值，保持线段树的正确性(不然要挂)

哈希区间查询：

• query函数返回区间[L,R]的双哈希值，通过递归拆分区间并合并结果
• get_Node函数实现两个子区间哈希值的拼接，规则与update一致
• 当区间完全包含于查询范围时直接返回节点哈希值，否则合并左右子区间结果

之后这样写了几次，挂了不少，以为自己算法不对…
双哈希都不够你算，那线段树也得完蛋!

最后就是判断了，按照上面的说法判即可。
需要考虑数值的范围判断，处理越界问题，处理完一个节点后记得标记为false，避免重复使用。
具体看成码。

Code ED:

//ls、rs数组初始化... 还有lf、rt...
//算法:线段树、哈希hashing
//时间复杂度:O(nlog(n)) 
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
#define uint unsigned long long
using namespace std;
constexpr int b = 1331, N = 5e5+9;struct Node{uint first,second;//双哈希值int l,r;//区间左右端点
};
int T,n;
uint qpow[N];
int f[N];
int root = 1;
int id = 0;
int ls[N<<2],rs[N<<2];//左右子节点编号
int ll[N<<2],rr[N<<2];//节点对应区间
uint sum[N<<2][2];inline void pre(){qpow[0] = 1;for(int i = 1; i < N; ++i)  qpow[i] = qpow[i-1]*b;
}inline void update(int t){sum[t][0] = sum[ls[t]][0]*qpow[rr[rs[t]]-ll[rs[t]]+1]+sum[rs[t]][0];sum[t][1] = sum[rs[t]][1]*qpow[rr[ls[t]]-ll[ls[t]]+1]+sum[ls[t]][1];ll[t] = ll[ls[t]], rr[t] = rr[rs[t]];//节点区间继承左、右子树左端点
}inline void build(int &t, int l, int r){t = ++id, ll[t] = l, rr[t] = r;if(l == r){sum[t][0] = sum[t][1] = 1;//初始化叶子节点为1(表示存在)return;}int mid = (l+r) >> 1;build(ls[t], l, mid);build(rs[t], mid+1, r);update(t);
}inline void modify(int t, int l, int r, int L, int R){if(l == r){sum[t][0] = sum[t][1] = 0;//标记元素不存在return;}int mid = (l+r) >> 1;if(L <= mid)  modify(ls[t], l, mid, L, R);else  modify(rs[t], mid+1, r, L, R);update(t);
}inline Node get_Node(Node a, Node b){Node res;res.first = a.first*qpow[b.r-b.l+1]+b.first;res.second = b.second*qpow[a.r-a.l+1]+a.second;res.l = a.l, res.r = b.r;return res;
}inline Node query(int t, int l, int r, int L, int R){if(L<=l && r<=R){Node res;res.first = sum[t][0];res.second = sum[t][1];res.l = l, res.r = r;return res;}int mid = (l+r) >> 1;Node lf = {0, 0, -1, -1};Node rt = {0, 0, -1, -1};if(L <= mid)  lf = query(ls[t], l, mid, L, R);if(R > mid)  rt = query(rs[t], mid+1, r, L, R);if(R <= mid)  return lf;if(L > mid)  return rt; else  return get_Node(lf,rt);
}inline void Faith(){id = 0;build(root,1,n);modify(root,1,n,f[1],f[1]);//标记第一个元素已使用bool flag = false;for(int mid = 2; mid <= n; ++mid){int L = max((int)1, 2*f[mid]-n), R = min(n, 2*f[mid]-1);Node res = query(root, 1, n, L, R);//区间[L, R]哈希值if(f[mid]!=1 && f[mid]!=n && res.first!=res.second){flag = true;break;} modify(root, 1, n, f[mid], f[mid]);//标记当前节点已被使用}cout << (flag ? "Y":"N") << "\n";
}signed main(void){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);pre();cin >> T;while(T--){cin >> n;for(int i = 1; i <= n; ++i)  cin >> f[i];Faith();}return 0;
}

---

非正解(好像不叫解)

暴力

思路1

等差子序列嘛，则两两之间的差相等即可。(当时还不知道序列可以不连续)

Code ED

//算法:暴力
//时间复杂度:O(n)
#include <iostream>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;
const int N = 5e5+9;int T;
int n;
int f[N];
int g[N];signed main(void){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin >> T;while(T--){int num = 0;cin >> n;for(int  i = 1; i <= n; ++i){cin >> f[i];}for(int  i = 1; i <= n-1; ++i){g[i] = f[i+1]-f[i];}for(int  i = 1; i <= n-1; ++i){if(g[i] == g[i+1]){num = 2;}}if(n <= 2)  cout << "N" << "\n";if(num == 2)  cout << "Y" << "\n";else  cout << "N" << "\n";}return 0;
}

然后24pts…还以为要切紫
用时5分钟的做法就是不靠谱。

思路2

考虑了半天，序列不连续也可以。

比如：$10305\to 135$

所以，再想想。
取个三维，判断其中两个之间互等即可。

于是写了4分钟，$O(n^3)$的代码来了。

Code ED:

//n方过百万,暴力碾标算
//算法:暴力
//时间复杂度:O(n^3) 
#include <iostream>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;
const int N = 5e5+9;int T;
int n;
int f[N];signed main(void){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin >> T;while(T--){cin >> n;for(int i = 1; i <= n; ++i){cin >> f[i];}bool vis = false;for(int i = 1; i <= n-2; i++){for(int j = i+1; j <= n-1; j++){for(int k = j+1; k <= n; k++){if(f[j]-f[i] == f[k]-f[j]){vis = true;break;}}if(vis) break;}if(vis) break;}cout << (vis ? "Y" : "N") << "\n";}return 0;
}

40pts，算是有些满足了。
不愧为国家集训队的题。

桶

然后翻找到一个博客：洛谷题解 P2757 【[国家集训队]等差子序列】
还有同学的R219620519 记录详情

好吧，又有新思路了…

思路3

介入桶之前，先想想等差数列的核心性质：对于三个下标 $i<j<k$，若满足 $a_j-a_i=a_k-a_j$，则这三个数构成的等差子序列，可变形为 $a_k=2a_j-a_i$;

接下来介入桶。
桶将每个数值最后一次出现的下标记录下来。通过两层循环遍历可能的等差三元组。
共计时间复杂度 $O(n^2)$。

关键部分是记录各数值的下标，然后判 $k$ 下标是否大于 $j$ 下标。还有切勿重复使用首元素 $i$，否则会误判成其它子序列。
所以应定义一个 $vis[f[i]]=0$。

示例运行:
1
3
3 2 11. n = 3, 排列为 [3, 2, 1];
2. 外层循环 i = 1(a[i] = 3), 内层 j = 2(a[j] = 2);° 计算 tar = 2*2-3 = 1;° 检查 vis[1] = 3 > 2, 返回 true, 输出 "Y";
3. 该排列中存在等差子序列 3,2,1(公差-1), 该算法可正确检查到;

然后成码。

Code ED:

//显然,桶的复杂度是过不了的.时代的落泪...
//算法:桶
//时间复杂度:O(n^2) 
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 5e5+9, M = 1e6+9;int T,n;
int f[N];
int vis[M];
inline bool find(){register int i, j, N = n-1;for(i = 1; i < N; ++i){vis[f[i]] = 0;for(j = i+1; j < n; ++j){if(f[j]+f[j]-f[i] > 0 && vis[f[j]+f[j]-f[i]] > j)  return true;}}return false;
}signed main(void){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin >> T;while(T--){cin >> n;memset(vis, 0, sizeof(vis));for(int i = 1; i <= n; ++i){cin >> f[i];vis[f[i]] = i;}if(n < 3){cout << "N" << "\n";continue;}cout << (find() ? "Y":"N") << "\n";}return 0;
}

96pts，算是非正解的极限了。

虽说现在标签里没有桶，或许之前有。
但是…

所以：：：：：关于桶，它死啦！

---

总结

注意线段树中左右子树的节点初始化，还有哈希冲突。
这样的题啊，对于小蒟蒻来说，还是暴力好用…

插例

同学刚做出来的线性解，自行理解。(最优解榜一就是他)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cstdio>using namespace std;const int N = 5e5 + 10;int T, n;
int a[N];
bool vis[N << 1];int rd () {int res = 0; char c = getchar ();while (c < '0' || c > '9') c = getchar ();while (c >= '0' && c <= '9') {res = (res << 1) + (res << 3) + (c ^ 48);c = getchar ();}return res;
}int main () {scanf ("%d", &T);while (T--) {scanf ("%d", &n);memset (vis, 0, sizeof vis);bool fn = 0;for (int i = 1; i <= n; i++) a[i] = rd();for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= i + 4 && j <= n; j++) {if (a[i] - a[j] + a[i] >= 1 && a[i] - a[j] + a[i] <= n && vis[a[i] - a[j] + a[i]]) {fn = 1;break;}}if (fn) break;vis[a[i]] = 1;}if (fn) printf ("Y\n");else printf ("N\n");}return 0;
}