[CF 452F] Permutation

作法：

考慮從左邊往右邊掃，當掃到$i$的時候判斷是否存在兩數分別在$i$的左右，使得$a[i]$是他們的平均數。記$a[i]=x$，那麼不存在這樣的兩個數若且唯若「$j$和$2x-j$在$a[1],...,a[i-1]$中同時出現或同時不出現」，對於每個不讓上數值越界的$j$。因此我們考慮維護一個每個數分別出現了幾次的陣列，這樣就會變成詢問這個陣列中的其中一段是否和另一段倒過來一模一樣，並且支援把陣列中的$0$改成$1$。考慮維護正反的這樣的陣列，並且用 hash 來判字串相等，那麼求一個子字串的 hash 值就可以用 BIT 來作。這裡用的 hash 函數和一般的不太一樣，子字串$s[i...j]$的 hash 值會是 $a[i]+a[i+1]x+...+a[j]x^{j-i}$ ，這樣才能用 BIT 算出子字串的 hash 值（因為要修改，所以才用 BIT），並且要預處理出$x^{-1}$的所有冪次，才能快速算出 hash 值。詳細可以參考 code 。

code :

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
#define lowbit(x) (x&(-x))
using namespace std;
const int maxn=300000+10 , X=137 ;
 
LL power(LL x,int n)
{
    if(n<=1) return n ? x : 1 ;
    LL t=power(x,n/2) ;
    if(n%2) return (t*t%MOD)*x%MOD ;
    else return t*t%MOD ;
}
LL inv(int x)
{
    return power(x,MOD-2) ;
}
 
LL bit[2][maxn] ;
void add(int id,int x,LL val)
{
    for(;x<maxn;x+=lowbit(x)) bit[id][x]+=val ;
}
LL query(int id,int l,int r)
{
    LL ret=0 ;
    for(;r;r-=lowbit(r)) ret+=bit[id][r] ;
    for(l=l-1;l;l-=lowbit(l)) ret-=bit[id][l] ;
    ret%=MOD ;
    return ret<0 ? ret+MOD : ret ;
}
 
LL pw[maxn],ipw[maxn] ;
LL query_hash(int id,int l,int r)
{
    LL tmp=query(id,l,r) ;
    return tmp*ipw[l-1]%MOD ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=0;i<=n;i++) pw[i]= i?(pw[i-1]*X%MOD):1 ;
    LL invx=inv(X) ;
    for(int i=0;i<=n;i++) ipw[i]= i?(ipw[i-1]*invx%MOD):1 ;
 
    for(int i=0;i<n;i++)
    {
        int x ; scanf("%d",&x) ;
        int len=min(x-1,n-x) ;
        if(len && query_hash(0,x-len,x-1)!=query_hash(1,n+1-x-len,n-x))
            {printf("YES\n") ; return 0 ;}
        add(0,x,pw[x-1]) ;
        add(1,n+1-x,pw[n-x]) ;
    }
    printf("NO\n") ;
}