我们寻找一个东西总是比判断一个东西复杂,对吧;
那么就转化思路:如果我们知道等差数列的中间项mid,那么就是寻找一对数(l,r),使得abs(mid-l)==abs(mid-r),且l<mid<r;
可以枚举每个数作为中间项,然后O(n)的判断是否存在这样的数对(l,r);
但这是O(n^2)的,复杂度无法接受;
那么考虑优化:
我们知道,对于每次枚举只要有一个数对就存在答案;
对于已经枚举过的点,标记为1;否则是0;
这样序列就变成了一个01序列;
对于每个中间项,存在答案当且仅当左右的一个对称位置的01数值不同;
也就是说:对于每个中间项只有左右两侧的序列的hash值只有在完全相同的情况下才不存在解;
hash值可以使用树状数组或者线段树来维护;
复杂度变成了O(nlogn);
#include <bits/stdc++.h> #define inc(i,a,b) for(register int i=a;i<=b;i++) #define ull unsigned long long using namespace std; int a[100010]; ull hash1[100010],hash2[100010],pre[100010]; const int p=1e9+7; int n; class node{ public: int lowbit(int x){return x&(-x);} void adda(int x,ull v){while(x<=n) hash1[x]+=v,x+=lowbit(x);} void addb(int x,ull v){while(x<=n) hash2[x]+=v,x+=lowbit(x);} ull aska(int x){ull sum=0;while(x) sum+=hash1[x],x-=lowbit(x);return sum;} ull askb(int x){ull sum=0;while(x) sum+=hash2[x],x-=lowbit(x);return sum;} }tree; int main() { int T; cin>>T; while(T--){ memset(hash1,0,sizeof(hash1)); memset(hash2,0,sizeof(hash2)); scanf("%d",&n); inc(i,1,n) scanf("%d",&a[i]); pre[0]=1; inc(i,1,n) pre[i]=pre[i-1]*p; bool flag=1; inc(i,1,n){ tree.adda(a[i],pre[a[i]]); tree.addb(a[i],pre[n-a[i]+1]); register int tmp=min(a[i]-1,n-a[i]); ull tmp1=tree.aska(a[i])-tree.aska(a[i]-tmp-1); ull tmp2=tree.askb(a[i]+tmp)-tree.askb(a[i]-1); if(a[i]<n-a[i]+1) tmp1=tmp1*pre[n-a[i]+1-a[i]]; else if(a[i]>n-a[i]+1) tmp2=tmp2*pre[a[i]-(n-a[i]+1)]; if(tmp1!=tmp2){ printf("Y\n"); flag=0; break; } } if(flag){ printf("N\n"); } } return 0; }