BZOJ2124: 等差子序列

 1 {$inline on}
 2 const base=3;p=100000007;maxn=10000+10;
 3 type node=record
 4      l,r,mid,s:longint;
 5      v1,v2:int64
 6      end;
 7 var t:array[0..6*maxn] of node;
 8     a:array[0..maxn] of longint;
 9     b:array[0..maxn] of int64;
10     i,n,x,y,cs:longint;
11     xx,yy:longint;
12     function min(x,y:longint):longint;inline;
13      begin
14        if x<y then exit(x) else exit(y);
15      end;
16 
17 procedure build(k,x,y:longint);inline;
18  begin
19    with t[k] do
20      begin
21        l:=x;r:=y;mid:=(l+r)>>1;s:=r-l+1;v1:=0;v2:=0;
22        if l=r then exit;
23        build(k<<1,l,mid);
24        build(k<<1+1,mid+1,r);
25      end;
26  end;
27 procedure change(k,x,y:longint);inline;
28  begin
29    with t[k] do
30      begin
31       if l=r then
32        begin
33          v1:=y;v2:=y;;exit;
34        end;
35       if x<=mid then change(k<<1,x,y)
36       else change(k<<1+1,x,y);
37       v1:=(t[k<<1].v1*b[t[k<<1+1].s]+t[k<<1+1].v1) mod p;
38       v2:=(t[k<<1+1].v2*b[t[k<<1].s]+t[k<<1].v2) mod p;
39      end;
40  end;
41 function query1(k,x,y:longint):int64;inline;
42  begin
43    with t[k] do
44      begin
45       if (l=x) and (r=y) then exit(v1);
46       if y<=mid then exit(query1(k<<1,x,y))
47       else if x>mid then exit(query1(k<<1+1,x,y))
48       else exit(((query1(k<<1,x,mid)*b[(y-mid)]+query1(k<<1+1,mid+1,y))) mod p);
49      end;
50  end;
51 function query2(k,x,y:longint):int64;inline;
52  begin
53    with t[k] do
54      begin
55       if (l=x) and (r=y) then exit(v2);
56       if y<=mid then exit(query2(k<<1,x,y))
57       else if x>mid then exit(query2(k<<1+1,x,y))
58       else exit(((query2(k<<1+1,mid+1,y)*b[(mid-x+1)]+query2(k<<1,x,mid))) mod p);
59      end;
60  end;
61 procedure init;
62  begin
63    readln(n);
64    for i:=1 to n do read(a[i]);readln;
65    build(1,1,n);
66  end;
67 function check:boolean;inline;
68  begin
69    if n<=2 then exit(false);
70    for i:=1 to n do
71     begin
72       x:=a[i];
73       y:=min(n-a[i],a[i]-1);
74       if (a[i]<>1) and (a[i]<>n) then
75         begin
76           xx:=query1(1,x-y,x-1);yy:=query2(1,x+1,x+y);
77           if xx<>yy then exit(true);
78         end;
79       change(1,a[i],1);
80     end;
81    exit(false);
82  end;
83 begin
84   assign(input,‘input.txt‘);assign(output,‘output.txt‘);
85   reset(input);rewrite(output);
86   readln(cs);
87   b[1]:=base;
88   for i:=2 to maxn do b[i]:=b[i-1]*base mod p;
89   while cs>0 do
90    begin
91      dec(cs);
92      init;
93      if check then writeln(‘Y‘) else writeln(‘N‘);
94    end;
95   close(input);close(output);
96 end.
97