P 277[国家合宿隊]等差サブシーケンス(線分樹+hash/bitset)

テーマリンク
P 277[国家合宿隊]等差サブシーケンス
件名:
一つの配列が与えられています.3より長い等差数列の複数グループのデータが見つかりました.(n<=1 e 4)(n==1 e 4)(n<=1 e 4)(n<=1 e 4)
考え方:
長さが3 3の等差数列があるかどうかを判断します.一つの配列なので、左から順に数字をスキャンします.一つの数字が現れたら、その対応する位置を1にします.一つの数字a[i]a[i]a[i]a[i]a[i]に対して、等差数列の中間項目であれば、必ず一つのx xが存在します.位置a[i]−x[i]-a[i]とa[x]は同じです.したがって、a[i]a[i]a[i]を中心とする文字列に対しては、回文列であればa[i]a[i]a[i]a[i]を中心とする等差数列は存在しない.では、どのように判断すればいいですか?線分樹で01列に向かうh＿h＿hash＿hash値と逆方向のh＿h＿hash＿hash値を維持し、左から右に向かって毎回更新して判断すればいいです.もう一つの方法はbitsetを利用して直接判断することです.a,b,c a,b,c,b,cが等差数列であれば、2∗b=a+c 2*b=a+c 2∗b=a+c 2∗b=a+cとなり、左から右にスキャンして、a[i]a[i]a[i]a]a[i]a]a]a[i]をb]として、現在のb i t e bitsetを重ね合わせて、左にスキャンした部分があるか否かを説明します.
コード:
線分木+hash

#include 
#define ls x<<1
#define rs x<<1|1
#define ull unsigned long long
using namespace std;
const int N=1e4+10;
const int base=2333;
int T,n;
ull p[N],vl[N*4],vr[N*4];
void add(int x,int l,int r,int pos){
	if(l==r){
		vl[x]=vr[x]=1;return;
	}
	int mid=(l+r)/2;
	if(pos<=mid)add(ls,l,mid,pos);else add(rs,mid+1,r,pos);
	vl[x]=vl[ls]*p[r-mid]+vl[rs];
	vr[x]=vr[rs]*p[mid-l+1]+vr[ls];
}
ull query(int x,int l,int r,int LL,int RR,int id){
	if(l>=LL&&r<=RR){
		if(id==1)return vl[x];else return vr[x];
	}
	int mid=(l+r)/2;
	if(LL>mid)return query(rs,mid+1,r,LL,RR,id);
	else if(RR<=mid)return query(ls,l,mid,LL,RR,id);
	else{
		if(id==1)return query(ls,l,mid,LL,RR,id)*p[min(RR,r)-mid]+query(rs,mid+1,r,LL,RR,id);//      
		else return query(rs,mid+1,r,LL,RR,id)*p[mid-max(LL,l)+1]+query(ls,l,mid,LL,RR,id);//   max min
	}
}
bool pd(int pos){
	int len=min(pos,n-pos+1);
	ull t1=query(1,1,n,pos,pos+len-1,1);
	ull t2=query(1,1,n,pos+1-len,pos,2);
	if(t1!=t2)return 1;else return 0;
}
int main()
{
	scanf("%d",&T);
	p[0]=1;for(int i=1;i<N;i++)p[i]=p[i-1]*base;
	while(T--){
		memset(vl,0,sizeof(vl));memset(vr,0,sizeof(vr));//     
		scanf("%d",&n);int flag=0;
		for(int i=1,x;i<=n;i++){
			scanf("%d",&x);
			if(flag)continue;
			add(1,1,n,x);
			if(pd(x)){
				flag=1;
			}
		}
		if(flag)puts("Y");else puts("N");
	}
}

ビットセット

#include 
using namespace std;
const int N=2e4+10;
int T,n;
int a[N];
bool pd(){
	bitset<N>t1,t2;
	for(int i=1;i<=n;i++)t1[a[i]]=1;
	for(int i=1;i<=n;i++){
		t1[a[i]]=0;
		if(((t2>>(N-2*a[i]))&t1).any())return 1;// a[i]       ，a+c=2*b
		t2[N-a[i]]=1;
	}
	return 0;
}
int main()
{
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		if(pd())puts("Y");
		else puts("N");
	}
}