bzoj2124 等差子序列（hash+线段树）

2124: 等差子序列

Time Limit: 3 Sec Memory Limit: 259 MB
Submit: 719 Solved: 261
[Submit][Status][Discuss]

Description

给一个1到N的排列{Ai}，询问是否存在1<=p1=3），使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。

Input

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

Output

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

Sample Input

2
3
1 3 2
3
3 2 1

Sample Output

N
Y

HINT

对于100%的数据，N<=10000，T<=7

Source

【思路】

转化+hash+线段树。

首先需要明确的一点：A是一个1..n的排列。

其次将出现情况统计为01字符串分别表示该数字目前为止是否出现，因此对于一个数字当前没有出现以后一定会出现。例如对于{5,2,1,4,3,6}且已经扫到了4，则有01状态为110010，可以看出如果有一对数字以4为中心分别为01则一定有等差数列。又因为非0即1的性质，所以问题可以转化为两个字串是否相等的问题，对应到例子中即s(2,3)是否等于s(6,5)，如果相等则必无等差数列反之则必有一个或多个等差数列。

线段树维护hash，[区间查询单点修改]，O(logn)的查询时间，O(logn)的维护时间，总时间为O(nlogn)。

注：求Hash对应一个区间查询。

【代码】

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)

 using namespace std;

 typedef long long LL;

 const int maxn = +;

 const int MOD = ;

 int read() {

     char c=getchar();

     while(!isdigit(c)) c=getchar();

     int x=;

     while(isdigit(c)) {

         x=x*+c-'';

         c=getchar();

     }

     return x;

 }

 int n;

 int a[maxn],xp[maxn];

 LL sumv[*maxn][];

 int v;

 void update(int u,int L,int R) {

     int lc=u<<,rc=lc+;

     if(L==R) {

         sumv[u][]=sumv[u][]=;

     }

     else {

         int M=L+(R-L)/;

         if(v<=M) update(lc,L,M);

         else update(rc,M+,R);

         sumv[u][]=(sumv[rc][]+xp[R-M]*sumv[lc][]%MOD)%MOD;

         sumv[u][]=(sumv[lc][]+xp[M-L+]*sumv[rc][]%MOD)%MOD;

     }

 }

 LL query(int node,int l,int r,int a,int b,int x){

     int lc=node<<,rc=lc+;

     if(l==a&&r==b)return sumv[node][x];

     int m=(l+r)>>;

     LL left=,right=;

     if(m<b)right=query(rc,m+,r,max(m+,a),b,x);

     if(a<=m)left=query(lc,l,m,a,min(m,b),x);

     return (x?left+right*xp[max(,m-a+)]%MOD:right+left*xp[max(,b-m)]%MOD)%MOD;

 }

 int main()

 {

     freopen("cin.in","r",stdin);

     freopen("coutme.out","w",stdout);

     int T;

     T=read();

     while(T--) {

         memset(sumv,,sizeof(sumv));

         n=read();

         xp[]=;    FOR(i,,n+) xp[i]=(xp[i-]<<)%MOD;

         FOR(i,,n) a[i]=read();

         bool f=;

         FOR(i,,n) {

             int x=a[i];

             LL lf,rf;

             int len=min(x-,n-x);

             if(len&&query(,,n,x-len,x-,)!=query(,,n,x+,x+len,)){

                 f=;

                 break;

             }

             v=x;

             update(,,n);

         }

         if(f) printf("Y\n");

         else printf("N\n");

     }

     return ;

 }

秒客网