HDU6701 2019多校十1011 启发式分治
HDU6701 2019多校十1011 启发式分治
Link
题意
给你 \(k\) 和一个长度为 \(n\) 的数组和，求满足
\[ max\{a_{l},a_{l+1}...a_{r}\}-(r-l+1)>=k \]且 \(a_{l}…a_{r}\) 两两不同的 \((l,r)\) 的对数。
题解
打的时候乱写了个尺取+线段树，到最后也没调出，，，
用尺取预处理出在保证区间数不重复的情况下每个位置作为左/右边界时能扩展的最大距离。
考虑分治，\(solve(l,r)\) 表示计算 \(l\) 到 \(r\) 中跨越 \(mid\) 的合法区间对数，但式子中的 \(max\) 那一项不能固定，因此考虑选择满足 \(a_{mid} = max\{a_{l}…a_{r}\}\) 的 \(mid\) 作为分治的中点，这样可以把式子中 \(max\{a_{l},a_{l+1}…a_{r}\}\) 固定为 \(a_{mid}\)，对区间长度的限制也可以变为 \((r-l+1)>=a_{mid}-k\) 。
还有一个问题，计算答案时我们有两种选择，一个是枚举左端点 \(l,l+1,…mid\) 统计右端点的可行位置，另一种是枚举右端点统计左端点的可行位置，但我们的 \(mid\) 不是 \((l+r)/2\)，所以我们每次选择长度小的一边计算答案以保证复杂度里的 \(logn\) 不会退化成 \(n\)（启发在这里）。
区间最大值的位置用 \(ST\) 表就好 ，多个 \(log\) 估计冲不过，，，
细节还蛮多的，大概要细心点调
namespace st
{
int f[MAXN][20];
int pos[MAXN][20];
void init(int a[],int n)
{
fp(i,1,n)f[i][0]=a[i];
fp(i,1,n)pos[i][0]=i;
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
if(f[i][j-1]>=f[i+(1<<(j-1))][j-1]) pos[i][j]=pos[i][j-1];
else pos[i][j]=pos[i+(1<<(j-1))][j-1];
}
}
}
int query(int l,int r)
{
int k=log2(r-l+1),ans=max(f[l][k],f[r-(1<<k)+1][k]);
return f[l][k]>=f[r-(1<<k)+1][k]?pos[l][k]:pos[r-(1<<k)+1][k];
}
}
int n,k;
int L[MAXN],R[MAXN];
int a[MAXN];
LL solve(int l,int r)
{
if(l>r ) return 0;
if(l==r) return a[l]-1<=k;
int mid=st::query(l,r),len=max(1,a[mid]-k);
LL ans=0;
if(mid-l<r-mid)
{
fp(i,l,mid)
if(max(i+len-1,mid)<=min(r,R[i]))
ans+=min(r,R[i])-max(i+len-1,mid)+1;
}
else
{
fp(i,mid,r)
if(min(i-len+1,mid)>=max(l,L[i]))
ans+=min(i-len+1,mid)-max(l,L[i])+1;
}
//cout << dbgs3(l,r,mid) << endl;
//cout << dbgs2(len,ans) << endl;
return ans+solve(l,mid-1)+solve(mid+1,r);
}
map<int,bool> m;
void init()
{
m.clear();
for(int r=1,l=1;r<=n;r++)
{
while(l<r&&m[a[r]]==1) m[a[l]]=0,l++;
m[a[r]]=1,L[r]=l;
//cout << dbgs2(r,L[r]) << endl;
}
m.clear();
for(int l=n,r=n;l>=1;l--)
{
while(l<r&&m[a[l]]==1) m[a[r]]=0,r--;
m[a[l]]=1,R[l]=r;
//cout << dbgs2(l,R[l]) << endl;
}
}
int work()
{
int T=read();
while(T--)
{
n=read(),k=read();
fp(i,1,n)a[i]=read();
init(),st::init(a,n);
write(solve(1,n)),putchar('\n');
}
return 0;
}