HDU6701 2019多校十1011 启发式分治

Link

Make Rounddog Happy

题意

给你 $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;
}