2023-07-19 20:07:13
(双倍经验:CF452F Permutation)
前言
这篇题解的代码与大部分代码用的正反做哈希不太一样，是倒数组做哈希的，希望可以给跟我方法相似但是代码挂了的同学一点启发。
自己的想法
由等差数列基本性质，我们只要找到任意三个数满足 \(a[l]+a[r]=2\times a[mid]\) 即可 \((1\le l<mid<r\le n)\)。
也就是我们遍历每一个数，然后从数值上向外扩(不断 +1 和 -1 )，找是否有一对这样的数使得其在位置上分别位于该数的两侧即可。
于是我们可以先打一个简单的暴力,复杂度 \(O(n^2)\) ,然后发现在洛谷上测出来96分.....
\(Violent\ Code\)
bool violent(){
int loc[500005];
memset(loc,0,sizeof(loc));
for(int i=1;i<=n;i++)
loc[a[i]]=i;
for(int i=2;i<n;i++)
for(int j=1;a[i]-j>=1&&a[i]+j<=n;j++){
int s=a[i]-j,b=a[i]+j;
if((loc[s]<i&&i<loc[b])||(loc[s]>i&&i>loc[b]))return 1;
}
return 0;
}
参考题解思路后
还是思考一下正解吧，同样从左往右枚举 \(i\)，然后枚举 \(k\)，如果 \(a[i]+k\) 和 \(a[i]-k\) 这两个数有一个之前出现过但是一个没出现过，说明没出现过的在i的右侧而出现过的在i的左侧，那么就满足条件了吧。
那么我们从左往右一个一个扫过去，开一个空数组 \(p\)，每次扫到i就在 \(p[a[i]]=1\) ,说明这个值已经有了（另外一种形式的桶）。
那么在 \(p\) 数轴中，当我们遍历到 \(i\) 的时候，\(a[i]+k\) 和 \(a[i]-k\) 在 \(p\) 数轴就是关于 \(a[i]\) 标对称的，上面说到如果扫到 \(i\) 时 \(a[i]+k\) 和 \(a[i]-k\) 的出现关系不同，则满足条件，那么出现关系相同就不满足条件，所以此时在数轴上看他们要么都是1，要么都是0，因为这两个值在 \(p\) 数轴上本就关于 \(a[i]\) 对称，所以整个 \(p\) 数轴在遍历到i时都是关于 \(a[i]\) 对称的，所以我们只需要判断整个数轴是否关于 \(a[i]\) 对称即可。
判断对称很快就想到了对数组正序和逆序做两个哈希表，单点哈希值修改，区间哈希值查询，想到用两个线段树维护哈希表，复杂度 \(O(n\log n)\)。
具体哈希值怎么维护？
将两个子串合并时，由于我们是从左到右，所以合并时是先将左串的哈希值乘以右串的长度次的质数的幂，然后再加上右串，具体可以表示为：\(hash[root]=hash[root<<1]\times P[rlen]+hash[root<<1|1]\)。
特别要注意所合并的右串的长度，否则容易像我一样，因为 \(query\) 中的右串长度写错调了一个半小时并且因为没有与大部分题解中正反做哈希的方法相同怀疑直接倒转数组做哈希的正确性。
下面是我觉得码风很正常的代码~
\(Code\)
typedef unsigned long long ll;
#define mid (l+r>>1)
const ll p=3;
int T,n;
int a[500005];
ll P[500005];
inline void pushup(int root,int t,ll tr[]){
tr[root]=tr[root<<1]*P[t>>1]+tr[root<<1|1];//P[t>>1]取右区间长度为值的原因是左边乘上右边的长度才能加右边
}
void update(int root,int l,int r,int x,ll tr[]){
if(l==r){
tr[root]=1;
return;
}
if(mid>=x)update(root<<1,l,mid,x,tr);
else update(root<<1|1,mid+1,r,x,tr);
pushup(root,r-l+1,tr);
}
ll query(int root,int l,int r,int x,int y,ll tr[]){
if(x>y)return 0;
if(x<=l&&r<=y){
return tr[root];
}
ll ans=0;
if(mid>=x)ans=query(root<<1,l,mid,x,y,tr);
if(mid<y)ans=ans*P[min(y,r)-mid]+query(root<<1|1,mid+1,r,x,y,tr);//万恶之源（1个半小时的调试）：P[]里面既不是r也不是y，是r和y里面偏小的那个。因为里面是有效右区间的长度！！！
return ans;
}
ll tr1[2000006],tr2[2000006];
int main(){
T=read();
P[0]=1;
for(int i=1;i<=500000;i++){
P[i]=P[i-1]*p;
}
while(T--){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=(n<<2)+3;i++){
tr1[i]=tr2[i]=0;
}
bool flag=0;
for(int i=1;i<=n;i++){
update(1,1,n,a[i],tr1);
update(1,1,n,n-a[i]+1,tr2);
int l=max(1,a[i]*2-n),r=min(n,2*a[i]-1);
ll l1=query(1,1,n,l,r,tr1);
l=n-l+1,r=n-r+1;
swap(l,r);
ll l2=query(1,1,n,l,r,tr2);
if(l1!=l2){
flag=1;
break;
}
}
if(flag)puts("Y");
else puts("N");
}
}
感言：
要相信自己证明出的东西啊，不要一直想着模仿题解的代码而不思考为什么他们可以这么写，你直接用到你的代码里却错了。比如我一开始在query里的P[]是直接看题解写的r-mid，只有16分。改成y-mid也只有16分。后来自己感觉不太对跟着自己的直觉改成了取min，看到洛谷上最后显示的 \(\color{lightGreen}{Accepted}\) 的时候真的很惊讶很兴奋，感觉这2个半多小时值得，酸了一晚上的眼睛值得！后面我仔细思考了一下，题解中是先用了两个if判断的，最后才返回r-mid，应该是之前的判断已经解决了部分问题，而我自以为是以为直接写两个if都一样，所以就直接按着上面的来。
至于为什么我代码要看题解，其实我一开始是打了一个奇奇怪怪的哈希表的，结果是显然WA飞起。所以我就稍微重新学了一遍哈希，然后再根据题解学一学，然后有个小细节就没有注意到。