线段树维护哈希值
要求出现长度大于三的等差子序列，我们只要找到长度等于三的就可以了
初看本题没有思路，只能暴力枚举，O（n^4） 后来发现，这个序列是n的一个排列，那么每个数字都只会出现一次 我们可以维护一个 \(01\) 序列 B ，表示某个数字是否出现过， 然后我们从左往右枚举等差中项x并将该项在B中置为1，存在等差数列当且仅当， B序列以x为中心的极大子区间不是回文子区间 我们该如何高效的判断回文子区间呢，首先维护B的正反两个序列 然后有两种做法 1.线段树维护 \(01\) 序列的哈希值，要注意预处理，以及具体在某步中移多少位 2.用bitset维护线段树维护哈希值，64位自然溢出
#include#include #include #include #include #include #define lson l, mid, rt<<1#define rson mid + 1, r, rt<<1|1#define ll unsigned long long using namespace std;const int MAXN = 10005, base = 233;int init() { int rv = 0, fh = 1; char c = getchar (); while(c < '0' || c > '9') { if(c == '-') fh = -1; c = getchar(); } while(c >= '0' && c <= '9') { rv = (rv<<1) + (rv<<3) + c - '0'; c = getchar(); } return fh * rv;}int T, n;ll hash1[MAXN<<2], hash2[MAXN<<2], idx[MAXN<<2];ll Query1(int L, int R, int l, int r,int rt) { if(L > R) return 0; if(L <= l && r <= R) { return hash1[rt]; } int mid = (l + r) >>1; ll ans = 0; if(L <= mid) ans = Query1(L, R, lson); if(mid < R) { ans *= idx[min(R, r) - mid]; //注意min（R,r） ans += Query1(L, R, rson); } return ans;}ll Query2(int L, int R, int l, int r, int rt) { if(L > R) return 0; if(L <= l && r <= R) { return hash2[rt]; } int mid = (l + r) >>1; ll ans = 0; if(mid < R) ans = Query2(L ,R, rson); if(L <= mid){ ans *= idx[mid - max(L, l) + 1]; ans += Query2(L, R, lson); } return ans;}void PushUp(int rt, int m) { hash1[rt] = hash1[rt<<1] * idx[m>>1] + hash1[rt<<1|1]; hash2[rt] = hash2[rt<<1|1] * idx[m - (m>>1)] + hash2[rt<<1];}void Update(int x, int l, int r, int rt) { if(l >= r) { hash1[rt] = hash2[rt] = 1; return; } int mid = (l + r) >>1; if(x <= mid) Update(x, lson); else Update(x, rson); PushUp(rt, r - l + 1);}int main() { freopen("in.txt", "r", stdin); T = init(); idx[0] = 1; for(int i = 1 ; i <= MAXN ; i++) { idx[i] = idx[i-1] * base; } while(T--) { n = init(); memset(hash1, 0, sizeof(hash1)); memset(hash2, 0, sizeof(hash2)); bool f = 0; for(int i = 1 ; i <= n ; i++) { int x = init(); int len = min(x - 1, n - x); if((!f) && (Query1(x - len, x - 1, 1, n, 1) != Query2(x + 1, x + len, 1, n, 1))) { f = 1; } Update(x, 1, n, 1); } printf("%c\n", f?'Y':'N'); } fclose(stdin); return 0;}