夏晓光(loveJY)的博客

首先看到n<=1e4我们可以直接写一个n^2暴力

这道题也确实可以过

但是正解还是要想的

考虑我们从前到后枚举等差中项然后判断公差的时候加速一下

于是我们可以考虑判断的充足条件

我们$a_i-d$在前面出现和$a_i+d$在后面出现(或者在后面),也就是说他们出现的vis xor 起来不为0

也就是说我们如果存在一个位置,那么在vis数组上以点$a_i$为中心的回文串一定不会是$a_i$所能形成的最长串,就是$a_i-lt,a_i-1$和$a_i+1,a_i+lt$一定不是一个回文串

这个....其实很显然吧?因为如果我们都相等说明二者出现的次数要么都在前面要么都在后面

而我们想让他不同....这个思想好像hash之前用过呢!

所以可以用线段树维护vis数组区间hash值

lt是$min(a_i-1,n-a_i)$就是可能公差范围!

先留一份暴力

code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
bool vis[MAXN];
int a[MAXN], n, T;

int main() {
	scanf("%d", &T);
	while(T-- > 0) {
		register int i, j, d = 0;
		scanf("%d", &n);
		for(i = 1; i <= n; ++i) {
			scanf("%d", &a[i]);
		}
		vis[a[1]] = 1;
		for(i = 2; i <= n; ++i) {
			if(d == 1000000)break;
			for(j = i; j <= n; ++j) {
				d = a[j] - a[i];
				if(a[i] - d >= 1 && vis[a[i] - d]) {
					puts("Y");
					d = 1000000;
					break;
				}
			}
			vis[a[i]] = 1;
		}
		for(i = 1; i <= n; ++i)vis[a[i]] = 0;
		if(d == 1000000)continue;
		puts("N");
	}
	return 0;
}

正解:

注意我们询问的L,R区间要随着我们询问的变化而缩小啊

否则hash值求出来是错误的

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll P = 1e9 + 7;
const int MAXN = 4e5 + 7;
const int MAXT = 7e5 + 7;
int m, n, a[MAXN];
ll bas[MAXN];
namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = BUF_SIZE + buf, *pend = buf + BUF_SIZE;
	inline char nc() {
		if(p1 == pend) {
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
			p1 = buf;
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;

namespace seg {
	int ls[MAXT], rs[MAXT], T, root;
	ll sum1[MAXT], sum2[MAXT];
	inline void update(int x, int R) {
		int mid = R >> 1;
		sum1[x] = (1ll * sum1[ls[x]] * bas[mid] % P + sum1[rs[x]]) % P;
		sum2[x] = (1ll * sum2[rs[x]] * bas[R - mid] % P + sum2[ls[x]]) % P;
	}
	inline void modify(int &k, int l, int r, int pos) {
		if(!k) {
			k = ++T;
			ls[k] = rs[k] = sum1[k] = sum2[k] = 0;
		}
		if(l == r) {
			sum1[k] = sum2[k] = 1;
			return ;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid)modify(ls[k], l, mid, pos);
		else modify(rs[k], mid + 1, r, pos);
		update(k, r - l + 1);
	}
	inline ll query1(int k, int l, int r, int L, int R) {
		if(L > R)return 0;
		if(!k)return 0;
		if(L == l && r == R) {
			return sum1[k];
		}
		int mid = (l + r) >> 1;
		if(R <= mid)return query1(ls[k], l, mid, L, R);
		else if(L > mid)return query1(rs[k], mid + 1, r, L, R);
		else return (query1(ls[k], l, mid, L, mid) * bas[R - mid] % P + query1(rs[k], mid + 1, r, mid + 1, R)) % P;
	}
	inline ll query2(int k, int l, int r, int L, int R) {
		if(L > R)return 0;
		if(!k)return 0;
		if(L == l && r == R) {
			return sum2[k];
		}
		int mid = (l + r) >> 1;
		if(R <= mid)return query2(ls[k], l, mid, L, R);
		else if(L > mid)return query2(rs[k], mid + 1, r, L, R);
		else return (query2(ls[k], l, mid, L, mid) + query2(rs[k], mid + 1, r, mid + 1, R) * bas[mid - L + 1] % P) % P;
	}
}
using namespace seg;

inline void init() {
	bas[0] = 1;
	for(int i = 1; i <= n; ++i) {
		bas[i] = 1ll * bas[i - 1] * 3 % P;
	}
	T = root = 0;
	return ;
}

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	m = read();
	while(m-- > 0) {
		n = read();
		init();//预处理模数
		for(int i = 1; i <= n; ++i) {
			a[i] = read();
		}
		bool flg = 0;
		for(int i = 1; i <= n; ++i) {
			ll len = min(a[i] - 1, n - a[i]);//range
			if(query1(root, 1, n, a[i] - len, a[i] - 1) != query2(root, 1, n, a[i] + 1, a[i] + len)) {
				flg = 1;
				break;
			}
			modify(root, 1, n, a[i]);
		}
		if(flg)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}