codevs 1283等差子シーケンス

リンク:http://codevs.cn/problem/1283/
中国語の問題.
分析:テーマは私达に等差数列が存在するかどうかを探すことを要求して、実は私达は条件を弱めることができて长さが3の等差数列が存在するかどうか、直接暴力はタイムアウトします(しかしこのOJの上のデータはとても弱くて、暴力は过ごすことができます)、私达はこのnの数をゆっくりと1つのカウント配列の中に参加することができて、例えばxを参加して私达はf[x]=1を命令しますこのように我々はxを加える際に1~x−1がx+1~nと対称(xを中心として対称)であるか否かを判断する.これで2つの文字列の判重になり、hashでいいので、更新するとこのf数をセグメントツリーにして、lognの更新とマージのたびにすればいいです.重さを判定する時もlognです.O(nlogn)
コード:

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=10010;
const int MAX=151;
const int mod=100000000;
const int MOD1=1000000007;
const int MOD2=1000000009;
const double EPS=0.00000001;
typedef long long ll;
const ll MOD=998244353;
const ll INF=10000000010;
typedef double db;
typedef unsigned long long ull;
int a[N];
ll ha[N],l[4*N],r[4*N];
void updata(int w,int le,int ri,int x) {
    if (le+1==ri) {
        l[w]=r[w]=1ull;return ;
    }
    int mid=(le+ri)/2;
    if (x<mid) updata(w<<1,le,mid,x);
    else updata((w<<1)+1,mid,ri,x);
    l[w]=(l[w<<1]+l[(w<<1)+1]*ha[mid-le]%MOD)%MOD;
    r[w]=(r[w<<1]*ha[ri-mid]%MOD+r[(w<<1)+1])%MOD;
}
ll getsum(int w,int L,int R,int le,int ri,int rev,int LL,int RR) {
    if (le>=ri) return 0;
    if (L==le&&R==ri) {
        if (rev>0) return l[w]*ha[le-LL]%MOD;
        else return r[w]*ha[RR-ri]%MOD;
    }
    int mid=(L+R)/2;
    if (ri<=mid) return getsum(w<<1,L,mid,le,ri,rev,LL,RR);
    else if (le>=mid) return getsum((w<<1)+1,mid,R,le,ri,rev,LL,RR);
    else return (getsum(w<<1,L,mid,le,mid,rev,LL,RR)+getsum((w<<1)+1,mid,R,mid,ri,rev,LL,RR))%MOD;
}
int main()
{
    int i,n,t,bo;
    ha[0]=1;for (i=1;i<N;i++) ha[i]=ha[i-1]*3%MOD;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (i=1;i<=n;i++) scanf("%d", &a[i]);
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        bo=0;
        for (i=1;i<=n;i++) {
            if (a[i]<=(n+1)/2&&getsum(1,1,n+1,1,a[i],1,1,a[i])!=getsum(1,1,n+1,a[i]+1,2*a[i],-1,a[i]+1,2*a[i])) bo=1;
            if (2*a[i]>n&&getsum(1,1,n+1,2*a[i]-n,a[i],1,2*a[i]-n,a[i])!=getsum(1,1,n+1,a[i]+1,n+1,-1,a[i]+1,n+1)) bo=1;
            if (bo) break ;
            updata(1,1,n+1,a[i]);
        }
        if (bo) printf("Y
");
        else printf("N
");
    }
    return 0;
}