BZOJ_2124_等差子序列_线段树+Hash

BZOJ_2124_等差子序列_线段树+Hash

Description

给一个1到N的排列{Ai},询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N (Len>=3),
使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。

Input

输入的第一行包含一个整数T,表示组数。
下接T组数据,每组第一行一个整数N,每组第二行为一个1到N的排列,数字两两之间用空格隔开。
N<=10000,T<=7

Output

对于每组数据,如果存在一个等差子序列,则输出一行“Y”,否则输出一行“N”。

Sample Input

2
3
1 3 2
3
3 2 1

Sample Output

N
Y


其实就是问是否存在一个长度为3的等差数列。

一种暴力:枚举中间数x,然后枚举差d,看x-d和x+d是不是有一个在桶里有一个不在桶里,如果是则x-d,x,x+d构成等差子序列。

然后优化这个暴力,如果把桶看成一个01的字符串,我要找的其实是x左边和右边延伸的一个字符串。

这个字符串如果不回文说明存在等差子序列。

可以用线段树动态维护正串和反串的hash值。

代码:

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
#define N 10050
#define ls p<<1
#define rs p<<1|1
ll h[N<<2][2],mi[N],base=7233913;
int n,a[N];
void build(int l,int r,int p) {
if(l==r) {
h[p][0]=h[p][1]='0';
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls); build(mid+1,r,rs);
h[p][0]=h[ls][0]*mi[r-mid]+h[rs][0];
h[p][1]=h[rs][1]*mi[mid-l+1]+h[ls][1];
}
void update(int l,int r,int x,int p) {
if(l==r) {
h[p][0]=h[p][1]='1';
return ;
}
int mid=(l+r)>>1;
if(x<=mid) update(l,mid,x,ls);
else update(mid+1,r,x,rs);
h[p][0]=h[ls][0]*mi[r-mid]+h[rs][0];
h[p][1]=h[rs][1]*mi[mid-l+1]+h[ls][1];
}
ll query(int l,int r,int x,int y,int flg,int p) {
if(x<=l&&y>=r) return h[p][flg];
int mid=(l+r)>>1;
if(y<=mid) return query(l,mid,x,y,flg,ls);
else if(x>mid) return query(mid+1,r,x,y,flg,rs);
else {
ll lx=query(l,mid,x,mid,flg,ls),rx=query(mid+1,r,mid+1,y,flg,rs);
if(!flg) {
return lx*mi[y-mid]+rx;
}else {
return rx*mi[mid-x+1]+lx;
}
}
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
int i;
for(mi[0]=1,i=1;i<=n;i++) {
scanf("%d",&a[i]);
mi[i]=mi[i-1]*base;
}
memset(h,0,sizeof(h));
build(1,n,1);
int flg=0;
for(i=1;i<=n;i++) {
if(a[i]!=1&&a[i]!=n) {
ll lans,rans;
if(a[i]-1>=n-a[i]) {
lans=query(1,n,2*a[i]-n,a[i]-1,0,1);
rans=query(1,n,a[i]+1,n,1,1);
}else {
lans=query(1,n,1,a[i]-1,0,1);
rans=query(1,n,a[i]+1,2*a[i]-1,1,1);
}
if(lans!=rans) {
flg=1; break;
}
}
update(1,n,a[i],1);
}
puts(flg?"Y":"N");
}
}
上一篇:day30 CRM业务开发之默认删除编辑功能


下一篇:mysql查询两个日期之前相隔的天数