海亮02/19杂题
T5
题意
设一个数组 \(a_{1,2,\dots,l}\) 是平衡的，当且仅当 \(\exists k\in[1,\frac{l - 1}{2}],\forall i\in[1,l - 2\times k],a_{i} + a_{i + 2\times k} = 2\times a_{i+k}\)。
现在给你一个数组 \(a\)，你需要对 \(\forall l\in[1,n]\) 求出子序列 \(a_{1,2,\dots,l}\) 是不是平衡的。
\(n\le 2\times 10^6\)
题解
先想想最暴力的做法。
枚举 \(l,k\)，然后对于区间 \([1,l]\)，用 \(O(n)\) 的时间进行 \(check\)。总时间复杂度是 \(O(n^3)\) 的。
然后有一个神奇的 \(check\)。
你搞一下字符串 \(hash\)，然后对于刚刚的 \(check\)，你就可以直接在 \(hash\) 上进行加减。
然后你就可以 \(O(1)\) 的 \(check\) 了。（具体实现看代码）
但是还不够，怎么办？
我们发现，对于一个 \(k\)，如果 \(l\) 不满足条件，那么 \(l+1\) 也一定不满足条件，于是就可以 \(O(n\log n)\) 的二分了，如果常数小的话可以直接过了。
但是还不够怎么办？
我们发现这里的 \(k\) 是 \(\exist k\)，不是 \(\forall k\)，于是可以维护一个右端点 \(l\)（不应该设 \(r\) 吗？不管了就这样吧。），不需要将这个指针向左移动。
然后就变成 \(O(n)\) 的了。
代码
#include<bits/stdc++.h>
using namespace std;
bool stmemory;
namespace Call_me_Eric{
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
int readbase62(){
int x = 0;char ch = getchar();
while(!isdigit(ch) && !islower(ch) && !isupper(ch))ch = getchar();
while(isdigit(ch) || islower(ch) || isupper(ch)){
x = x * 62;
if(isupper(ch)){x += ch - 'A' + 36;}
if(islower(ch)){x += ch - 'a' + 10;}
if(isdigit(ch)){x += ch - '0' + 0;}
ch = getchar();
}
return x;
}
const int maxn = 2e6 + 10;
typedef unsigned long long ull;
int n, a[maxn];
ull hsh[2][maxn], pw[2][maxn], base[2] = {1145141ull,1919810ull};
ull gethash(int l,int r,int opt){return (hsh[opt][r] - hsh[opt][l - 1] * pw[opt][r - l + 1]);}
bool check(int l,int k){
if(2 * k + 1 > l)return 0;
return gethash(1,l - 2 * k,0) + gethash(2 * k + 1,l,0) == 2ull * gethash(k + 1,l - k,0)
&& gethash(1,l - 2 * k,1) + gethash(2 * k + 1,l,1) == 2ull * gethash(k + 1,l - k,1);
}
bool ans[maxn];
void main(){
n = read();for(int i = 1;i <= n;i++)a[i] = readbase62();
pw[0][0] = pw[1][0] = 1;
for(int i = 1;i <= n;i++){
pw[0][i] = pw[0][i - 1] * base[0];pw[1][i] = pw[1][i - 1] * base[1];
hsh[0][i] = hsh[0][i - 1] * base[0] + 1ull * a[i];
hsh[1][i] = hsh[1][i - 1] * base[1] + 1ull * a[i];
}
int i = 1;
for(int k = 1;k * 2 + 1 <= n;k++){
i = max(i,2 * k + 1);
while(i <= n && check(i,k)){ans[i++] = '1';}
}
for(int i = 1;i <= n;i++)putchar('0' + ans[i]);
putchar('\n');
return;
}
};
bool edmemory;
signed main(){
auto stclock = clock();
Call_me_Eric::main();
auto edclock = clock();
cerr << (&stmemory - &edmemory) / 1024.0 / 1024.0 << " Mib cost.\n";
cerr << (edclock - stclock) * 1.0 / CLOCKS_PER_SEC << " Sec cost.\n";
return 0;
}