题意分析

给定整数 $n$，并给出 $0$至 $n−1$ 的一个排列 $p$（下标从 $0$ 开始），判断这个排列是否满足：对于任意的 $0≤i<j<k<n$，不存在 $(pi ,pj ,pk)$ 构成等差数列。如果满足，则称这个序列为"antiarithmetic" 的。

解题思路

考虑将等差的问题转化为序列染色问题，遍历整个序列 $p$，将 $pi$对应的点染色。如果 pi两边的染色序列是对称的，则说明$pi+j$ 和 $pi−j$ 在序列 $p$ 的同一侧出现，故没有发现等差序列。如果暴力比对 $pi$ 两边的染色序列会 TLE，可以开两棵线段树维护染色序列两个方向的哈希值，然后单点改区间查哈希值即可。

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

bool isAntiArithmetic(const vector<int>& perm) {
    int n = perm.size();

    // 对于每个元素，记录其在排列中的位置
    vector<int> pos(n);
    for (int i = 0; i < n; i++) {
        pos[perm[i]] = i;
    }

    // 检查所有可能的三元组
    for (int a = 0; a < n; a++) {
        for (int b = a + 1; b < n; b++) {
            // 计算等差数列的第三项
            int c = 2 * b - a;
            if (c < n && pos[a] < pos[b] && pos[b] < pos[c]) {
                return false;  // 找到等差数列，不是反算术排列
            }
        }
    }

    return true;  // 没有找到等差数列，是反算术排列
}

int main() {
    int n;
    char colon;

    while (cin >> n && n != 0) {
        cin >> colon;  // 读取冒号

        vector<int> perm(n);
        for (int i = 0; i < n; i++) {
            cin >> perm[i];
        }

        if (isAntiArithmetic(perm)) {
            cout << "yes" << endl;
        }
        else {
            cout << "no" << endl;
        }
    }

    return 0;
}