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

这个题数据给的很小，$N<=10000$ 暴力就是开一个桶记录每一个数的位置 枚举首项、公差，判断即可 这样就可以拿到$45$分的好成绩 ~~如果你常数够小的话可以得到$50$或$55$~~ 讲一下$100$分做法： 这是一个$1$到$n$的排列 用一个$01$串来表示各个数字的出现情况 例如序列为${1,6,4,2,5,3}$，从前往后扫到$2$的时候 $01$串长这样：${110101}$ 可以发现，如果以一个出现的数为中心，两边对称的地方有$1$，则存在等差数列 用线段树或树状数组维护$hash$值 从左往右扫，对于每一个$a_i$查询它两边的$hash$值是否相等 如果不相等，那么后面一定会有数补过来形成等差数列，输出$Y$即可 所以区间查询单点修改，总复杂度$O(nlogn)$ $CF452F$也是这个题，不过数据范围$3e5$嘿嘿嘿 ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; typedef unsigned long long ll; const int N=1e4+5,base=127; int n,a[N]; ll pw[N],hs1[N<<2],hs2[N<<2]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void pushup(int now,int l,int r) { hs1[now]=(hs1[now<<1]*pw[r]+hs1[now<<1|1]); hs2[now]=(hs2[now<<1]+hs2[now<<1|1]*pw[l]); } void update(int l,int r,int now,int x) { if (l==r){hs1[now]=hs2[now]=1; return;} int mid=(l+r)>>1; if (x<=mid) update(l,mid,now<<1,x); else update(mid+1,r,now<<1|1,x); pushup(now,mid-l+1,r-mid); } ll query1(int L,int R,int l,int r,int now) { if (l>R||r<L) return 0; if (l>=L&&r<=R) return hs1[now]; int mid=(l+r)>>1; if (mid>=R) return query1(L,R,l,mid,now<<1); if (mid<L) return query1(L,R,mid+1,r,now<<1|1); return (query1(L,mid,l,mid,now<<1)*pw[R-mid]+query1(mid+1,R,mid+1,r,now<<1|1)); } ll query2(int L,int R,int l,int r,int now) { if (l>R||r<L) return 0; if (l>=L&&r<=R) return hs2[now]; int mid=(l+r)>>1; if (mid>=R) return query2(L,R,l,mid,now<<1); if (mid<L) return query2(L,R,mid+1,r,now<<1|1); return (query2(L,mid,l,mid,now<<1)+query2(mid+1,R,mid+1,r,now<<1|1)*pw[mid-L+1]); } int main() { pw[0]=1; for (reg int i=1;i<=10000;i++) pw[i]=pw[i-1]*base; for (reg int T=read();T;T--) { memset(hs1,0,sizeof(hs1)); memset(hs2,0,sizeof(hs2)); n=read(); bool flag=0; for (reg int i=1;i<=n;a[i++]=read()); if (n<3) {puts("N"); continue;} for (reg int i=1;i<=n;i++) { int len=min(a[i]-1,n-a[i]); if (query1(a[i]-len,a[i]-1,1,n,1)!=query2(a[i]+1,a[i]+len,1,n,1)){flag=1; break;} update(1,n,1,a[i]); } if (flag) puts("Y"); else puts("N"); } return 0; } ```