bzoj2124: 等差子序列线段树+hash

时间：2023-03-09 20:06:02
bzoj2124: 等差子序列线段树+hash

bzoj2124: 等差子序列线段树+hash

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2124

思路

找大于3的等差数列其实就是找等于三的等差数列

三个等差数列的话，枚举中间点。

如果有对称点(a[i]-j,a[i]+j)在两侧，那么就能构成一个等差数列

我们可以转化为权值数组中a[i]能到达的最远对称串是否是回文串。

马拉车？？不不。hash是万能的。

这里hash可以用线段树维护

错误

我太菜了，代码写的特恶心

代码

#include <iostream>

#include <cstring>

#include <cstdio>

#define ull unsigned long long

using namespace std;

const int N=2e5+7;

const int mod=233;

int read() {

    int x=0,f=1;char s=getchar();

    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return x*f;

}

int n,pos[N],a[N];

ull my_pow[N];

namespace BIT {

    int lowbit(int x) {return x&-x;}

    ull sum[2][N];

    void add(int id) {

    	for(int i=id;i<=n;i+=lowbit(i))

    		sum[0][i]+=my_pow[id];

    	for(int i=n-id+1;i<=n;i+=lowbit(i))

    		sum[1][i]+=my_pow[n-id+1];

    }

	ull QQ0(int x,int y) {

		ull ans=0;

		if(x-1) for(int i=x-1;i>=1;i-=lowbit(i)) ans-=sum[0][i];

		for(int i=y;i>=1;i-=lowbit(i)) ans+=sum[0][i];

		return ans;

	}

	ull QQ1(int x,int y) {

		ull ans=0;

		if(x-1) for(int i=x-1;i>=1;i-=lowbit(i)) ans-=sum[1][i];

		for(int i=y;i>=1;i-=lowbit(i)) ans+=sum[1][i];

		return ans;

	}

}

// bool dsr[N];

int main() {

	// freopen("1.in","r",stdin);

	int T=read();

	my_pow[1]=1;

    for(int i=2;i<=10000;++i) my_pow[i]=my_pow[i-1]*233;

	while(T--) {

		memset(BIT::sum,0,sizeof(BIT::sum));

		n=read();

		for(int i=1;i<=n;++i) a[i]=read();

		bool flag=false;

		for(int i=1;i<=n;++i) {

			int len=min(a[i]-1,n-a[i]);

			// for(int k=1;k<=n;++k) cout<<dsr[k]<<" <";puts("");

			// cout<<a[i]-len<<" "<<a[i]<<" vs "<<a[i]<<" "<<a[i]+len<<"  <len\n";

			int x=a[i]-len,y=a[i];

			int y_=n-a[i]+1,x_=n-(a[i]+len)+1;

			int tmp0=1,tmp1=1;

			// cout<<x<<" "<<y<<" vs "<<x_<<" "<<y_<<"\n";

			if(x>x_) tmp1+=x-x_;

			else tmp0+=x_-x;

			// cout<<tmp0<<" "<<tmp1<<"\n";

			if(BIT::QQ0(x,y)*my_pow[tmp0]!=BIT::QQ1(x_,y_)*my_pow[tmp1]) {

				puts("Y");

				// cout<<i<<" "<<a[i]<<"\n";

				flag=true;

				break;

			}

			BIT::add(a[i]);

			// dsr[a[i]]=1;

		}

		if(!flag) puts("N");

	}

    return 0;

}

相关文章