2019多校第十场 HDU6701 Make Rounddog Happy（启发式分治）_综合

链接：HDU6701 Make Rounddog Happy

题意：

给出长度为 $n\;(\le 300000)$ 的序列 $a_1,a_2,\cdots,a_n\;(1\le a_i\le n)$ ，求出有多少满足下列条件的连续子序列 $a_l,a_{l+1},\cdots,a_r$ ?

$1\le l\le r\le n$
$\max(a_l,a_{l+1},\cdots,ar)?(r?l+1)≤k$
$\forall l\le i\lt j\le r,\;a_i\neq a_j$

分析：

由于满足条件的子序列内不能有重复元素，先预处理得到

$L [i] ：$ 以 $a_i$ 结尾的子序列的最远开头；
$R [i] ：$ 以 $a_i$ 开头的子序列的最远结尾。

设序列长度为 $l e n = r ? l + 1$ ，则条件 $\max(a_l,a_{l+1},\cdots,ar)?(r?l+1)≤k$ 即可转化为：
$len\ge \max(a_l,a_{l+1},\cdots,ar)-k$

所以可以枚举最大值 $a_{max}$ ，找到对应的区间，然后利用 $L [i]$ 和 $R [i]$ 在区间内计算符合的子序列数量。

关于枚举，需采用启发式分治，在分治过程中每次查找区间的最大值及其位置 $p$ （时间复杂度 $O(\log n)$ )，每次分治以 $p$ 为分界遍历更短的区间，计算符合的子序列数量，这样共需要遍历： $\frac{n}{2}+\frac{n}{4}+\frac{n}{4}+\frac{n}{8}+\frac{n}{8}+\frac{n}{8}+\frac{n}{8}+...$ 个数，则时间复杂度为 $O(n\log n)$ 。

所以总的时间复杂度为 $O(n\log n)$ 。

以下代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn=3e5+10;
int n,k,a[maxn];
int pre[maxn],L[maxn],R[maxn];
int t[maxn<<2];
void push_up(int rt)
{
    if(a[t[rt<<1]]>a[t[rt<<1|1]])t[rt]=t[rt<<1];elset[rt]=t[rt<<1|1];
}
void build(int rt,int l,int r)
{
    if(l==r){
    t[rt]=l;return;}int mid=(l+r)>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);push_up(rt);
}
int query(int rt,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)return t[rt];if(l>qr||r<ql)return 0;int mid=(l+r)>>1;int x=query(rt<<1,l,mid,ql,qr),y=query(rt<<1|1,mid+1,r,ql,qr);if(a[x]>a[y])return x;elsereturn y;
};
void prework()
{
    memset(pre,0,sizeof(pre));L[0]=1;for(int i=1;i<=n;i++){
    if(pre[a[i]])L[i]=max(L[i-1],pre[a[i]]+1);elseL[i]=L[i-1];pre[a[i]]=i;}memset(pre,0,sizeof(pre));R[n+1]=n;for(int i=n;i>=1;i--){
    if(pre[a[i]])R[i]=min(R[i+1],pre[a[i]]-1);elseR[i]=R[i+1];pre[a[i]]=i;}build(1,1,n);
}
LL ans;
void solve(int l,int r)
{
    if(l>r)return;int p=query(1,1,n,l,r),mid=(l+r)>>1;   //找到区间a[l]~a[r]中最大值的位置int max_len,min_len;if(p<=mid)    //遍历更短的区间{
    for(int i=l;i<=p;i++){
    if(R[i]<p)continue;max_len=min(R[i],r)-i+1;   //以a[i]开头，a[p]为最大值，子序列可达到的最大长度min_len=max(1,max(a[p]-k,p-i+1));   //以a[i]开头，a[p]为最大值，子序列符合要求的最小长度if(max_len>=min_len)ans+=1LL*(max_len-min_len+1);}}else{
    for(int i=r;i>=p;i--){
    if(L[i]>p)continue;max_len=i-max(L[i],l)+1;   //以a[i]结尾，a[p]为最大值，子序列可达到的最大长度min_len=max(1,max(a[p]-k,i-p+1));    //以a[i]结尾，a[p]为最大值，子序列符合要求的最小长度if(max_len>=min_len)ans+=1LL*(max_len-min_len+1);}}solve(l,p-1);solve(p+1,r);
}
int main()
{
    int T;scanf("%d",&T);while(T--){
    scanf("%d %d",&n,&k);for(int i=1;i<=n;i++)scanf("%d",&a[i]);prework();ans=0;solve(1,n);printf("%lld\n",ans);}return 0;
}