bitset 解法

一、思路很简单：

首先，找>=3个和找3个没区别。题目大雾。

一个权值bool数组，当这一位是a时，把a这一位设成1， 查询以a位置为中心的，以n或者1为边界的对称区域是否是回文的。

如果是，说明，可以所有和a等差的项都在前面出现了。

反之不是，就说明有一组的一项在前面出现了，而另一项在前面没有出现过。因为序列是一个1~n的排列，所以另一项肯定在后面出现了。

----> 带修判断区间回文问题 转化成功！

二、正解：

这个题正解是线段树维护hash值（可以想象得到）。

但是太难写了（蒟蒻一个）

所以就写了bitset。

（卡n=10000啊，再大了就不行了）

开两个bitset，

一个从前面看叫bf（bitset_front）

一个从后面看叫bb（bitset_back）

每次遇到一个数a，

就bf.set(a),bb.set(n-a+1)

比较的时候，取出两半的回文位置比较是否相等就好啦！

取的时候，

分w>n/2,w<=n/2 讨论，因为回文半径和bf，bb负责的部分是不同的。

由于要去掉其他干扰位置，就又开了一个bas数组。每次O(n)设置1。需要的时候，左移右移按位与去掉干扰位置。

还有注意，bitset是从0开始的。

所以为了去掉可能的0干扰问题，就都每次set(0)就好啦。

复杂度：O(n^2/32 = 3125000 )

至于如何准确取出，

大家看代码，自行画图理解吧。

（真正提升总是要手动理解的嘛）

代码：

#include
     
      using namespace std;const int N=10000+10;int n,t,a;bitset
      
       bf,bb,bas,c,d;void clr(){    bf.reset();bb.reset();bas.reset();}bool che(int w){    if(w>n/2){        c=bf>>(w-1);c.set(0);        d=(bb>>(n-w))&(bas>>(w-1));d.set(0);        if(d!=c) return true;        return false;    }    else{        c=(bf&(bas>>(n-w)));c.set(0);        d=((bb>>(n-2*w+1))&(bas>>(n-w)));d.set(0);        if(c!=d) return true;        return false;    }}int main(){    scanf("%d",&t);    while(t--){        clr();        scanf("%d",&n);        for(int i=1;i<=n;i++) bas.set(i);        bool fl=false;        for(int i=1;i<=n;i++) {             scanf("%d",&a);bf.set(a),bb.set(n-a+1);            if(che(a)) fl=true;        }        if(fl) printf("Y\n");        else printf("N\n");    }    return 0;}