Back to Posts

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

Posted in 题解

题目链接

题目大意

给定一个长度为n的序列,询问序列中是否存在下标上升三个数a,b,c使c-b=b-a,即等差数列,多组数据

其中n<10^5(luogu数据10^4),T<7

输入输出样例

输入样例

2

3

1 3 2

3

3 2 1

输出样例

N

Y

大体思路:线段树/树状数组+Hash

先贴个代码,改天再来补题解

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define N 10010
using namespace std;
int t,n,x,power[N];
int const mod=1000000007;
struct Tree{
	int c[N];
	void clear(){memset(c,0,sizeof(c));}
	void add(int pos)
	{
		for(int i=pos;i<=n;i+=(i&-i))
		c[i]=(c[i]+power[i-pos])%mod;
    }
    int q(int pos)
	{
		int rt=0;
		for(int i=pos;i;i-=(i&-i))
		rt=((long long)c[i]*power[pos-i]+rt)%mod;
		return rt;
	}
	int query(int l,int r){
		int xx=q(r),yy=q(l-1);
		return (xx-(long long)yy*power[r-l+1]%mod+mod)%mod;
	}
};
Tree tr1,tr2;
int main()
{
    scanf("%d",&t); power[0]=1;
	for(int i=1;i<N;i++)power[i]=(power[i-1]*2)%mod;
	while(t--)
	{
		tr1.clear();tr2.clear();
		scanf("%d",&n);
		int i,flag=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&x);
			int len=min(x-1,n-x);
			if(len&&tr1.query(x-len,x-1)!=tr2.query(n-x-len+1,n-x))
				flag=1;
			tr1.add(x); tr2.add(n-x+1);
		}
		if(flag==1)printf("Y\n");
		else printf("N\n");
	}
    return 0;
}

Read Next

Test