【题解】[国家集训队] 等差子序列 线段树维护区间哈希值 LuoguP2751/BZOJ2124/CF452F – 良月澪二

循序渐进地来

Pre-section

分析题目要求
要找长度 $>3$的等差序列
那么这个等差序列一定有一个长度为 3 的等差子序列
显然长度为 $3$的好找
还好找的不是一点点
所以我们的问题变成了找序列中是否有长度为 3 的等差子序列

Grade 1

首先想暴力
我们可以直接枚举公差和首项
设公差为 $d$，首项为 $a$
这样的话第一项第二项第三项就都有了
就分别为 $a$，$a+d$，$a+d+d$
上面只是举个栗子
通过记录每个数出现的位置就可以判断这个三个数是否满足条件
需要满足（第一项小于第二项且第二项小于第三项）或反过来
核心代码如下：

for (int i = 1; i <= n; i++) scanf("%d", &a), pos[a] = i;
for (int d = 1; d <= n / 2; d++)
    for (int j = 1; j <= n - d - d; j++)
        if ((pos[j] < pos[j + d] and pos[j + d] < pos[j + d + d]) or
            (pos[j] > pos[j + d] and pos[j + d] > pos[j + d + d]))
            {puts("Y"); break;}

显然
这样的复杂度是比较高的
相当于用桶记录每个数出现的位置
公差是 $n/2$的级别，首项是 $n$减去两个公差（因为要保证 $a+d+d$不会越界）的级别
不是标准的 $n^2$
在洛谷上这样的做法就可以 $A$了
BZOJ 上虽然数据范围相同但是跑不过去
CF 的 $3e5$的数据更是稳稳的过不去
所以我们需要继续往下想

Grade 2

题目给出的是一个 $1$~$n$的排列
对于一个长度为 $3$的等差子序列
设这三项分别为 $a$，$b$，$c$
那么有 $b-a=c-b$
也就是 $a+c=2*b$
对于固定的 $a$和 $b$
$c$的值也是固定的
如果 $c$在 $b$的前面
他们是构不成等差子序列的
因为在这个排列中 $c$有且只有一个
不是在 $b$的前面就是在 $b$的后面

那么现在我们要枚举所有可能的 $b$
判断它的前后是否有这样的 $a$和 $c$满足条件
如果有一组 $a$和 $c$分别在 $b$的前后
那么就可以构成等差子序列
怎么判断呢？

我们开一个 $bool$数组来表示这个位置的元素是否出现
那么如果以当前枚举到的点为中心
构成了一个回文串
那么可以和 $b$构成等差子序列的值都在它前面出现过了
因为我们的元素是挨个插入的
所以我们把问题转化成了带修判断区间回文问题
这个回文半径是多少呢？
能是多长就是多长
其中一个端点一定是 $1$或者 $n$
对于这个回文判定我们可以开两个 $bitset$
一个从前面做，一个从后面做
插入一个数滴时候第一个 $bitset$需要 set(x)
第二个 $bitset$由于是从后往前维护，所以是 set(n-a+1)
具体我也没写
不太熟 $bitset$
复杂度显然是 $\frac{n^2}{32}$的
BZOJ 上还是过不了

Grade 3

其实到这里已经很明显了
区间回文我们可以哈希判断
由于带修改，加上一个线段树就可以
主要是代码实现上会有些问题
我们开两棵线段树分别维护正反的哈希值
关于哈希值的维护网上的做法都是在 pushup 的时候维护进制
首先要搞明白为什么要维护进制：
考虑如何取出一段区间的哈希值
可以来这里看一看
我对主要内容在这里截一下屏

看完这个例子应该就很明白了
我们要让进制对齐
我这里的（权值）线段树维护做法和网上不一样
线段树只是维护区间和
对齐进制是在查询的时候对齐
下面的写法可以当做参考加深理解
这是洛谷 P2757 和 BZOJ2124 的 AC 代码
CF452F 改大一下数组去掉多组数据就可以了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define A 40010
#define B 2010

using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
struct node {
    int l, r; ll w;
}tree[A][2];
int T, n, a[A >> 2]; ll p[A >> 2];
void build(int k, int l, int r, int f) {
    tree[k][f].l = l; tree[k][f].r = r;
    if (l == r) {
        tree[k][f].w = 0;
        return;
    }
    int m = (l + r) >> 1;
    build(k << 1, l, m, f);
    build(k << 1 | 1, m + 1, r, f);
}
void up(int k, int f) {
    tree[k][f].w = tree[k << 1][f].w + tree[k << 1 | 1][f].w;
}
void change(int k, int pos, ll val, int f) {
    if (tree[k][f].l == tree[k][f].r) {
        tree[k][f].w = val;
        return;
    }
    int m = (tree[k][f].l + tree[k][f].r) >> 1;
    if (pos <= m) change(k << 1, pos, val, f);
    else change(k << 1 | 1, pos, val, f);
    up(k, f);
}
ll ask(int k, int l, int r, int f) {
    if (tree[k][f].l >= l and tree[k][f].r <= r) return tree[k][f].w;
    int m = (tree[k][f].l + tree[k][f].r) >> 1; ll ans = 0;
    if (l <= m) ans = (ans + ask(k << 1, l, r, f)) % mod;
    if (r > m) ans = (ans + ask(k << 1 | 1, l, r, f)) % mod;
    return ans;
}

int main(int argc, char const *argv[]) {
    p[1] = 1; for (int i = 2; i <= 10000; i++) p[i] = (p[i - 1] * 123) % mod;
    cin >> T;
    while (T--) {
        memset(tree, 0, sizeof tree);
        scanf("%d", &n); build(1, 1, n, 0); build(1, 1, n, 1);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) {
            int len = min(a[i] - 1, n - a[i]); //回文半径不能越界

            int s1 = a[i] - len, t1 = a[i]; //正向区间
            ll ha1 = ask(1, s1, t1, 0); //正向哈希值

            int s2 = n - a[i] - len + 1, t2 = n - a[i] + 1; //反向区间
            ll ha2 = ask(1, s2, t2, 1); //反向哈希值

            if (s2 > s1) ha1 = (ha1 * p[s2 - s1 + 1]) % mod; //对齐进制
            else ha2 = (ha2 * p[s1 - s2 + 1]) % mod;
            if (ha1 != ha2) {
                puts("Y");
                goto portal;
            }
            change(1, a[i], p[a[i]], 0); //分别修改两棵树
            change(1, n + 1 - a[i], p[n - a[i] + 1], 1);
        }
        puts("N");
        portal:;
    }
    return 0;
}