题目概述

ACL Contest 1D

解题报告

根本不会做，我来翻译原题解了QAQ。

如果要求的是 $[L,R]$ 中最长的good set，我们直接 从 $L$ 开始向后贪心 或者 从 $R$ 开始向前贪心 就可以得到答案。

假设最长的good set 长度为 $m$ 。如果从 $L$ 开始向后贪心，得到的下标为 $\{a_m\}$ ，从 $R$ 开始向前贪心，得到的下标为 $\{b_m\}$ ，我们可以得出以下关系：

$$ L=a_1\le b_1<a_2\le b_2<\cdots<a_m\le b_m=R $$

$a_i\le b_i$ 很显然，我们利用反证法证明 $b_i<a_{i+1}$ ：假设 $b_i\ge a_{i+1}$ ，那么就存在最长长度为 $m+1$ 的good set ，与假设矛盾。

得出这样的关系之后，我们不难发现所有下标在 $[a_i,b_i]$ 中的元素都至少在一个good set中（显然可以通过 $a$ 和 $b$ 构造），最后只需要证明下标不在 $[a_i,b_i]$ 中的元素不可能在good set中，还是利用反证法：假设 $b_i<k<a_{i+1}$ ，那么 $k$ 就可以在一个长度为 $m+1$ 的good set中，与假设矛盾。

所以答案就是 $\sum_{i=1}^{m}(b_i-a_i+1)=\sum_{i=1}^{m}b_i-\sum_{i=1}^{m}a_i+m$ ，可以用倍增维护。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=200000,LOG=18;

int n,K,te,a[maxn+5],lg[maxn+5];
int lst[maxn+5][LOG+1],nxt[maxn+5][LOG+1];
LL pre[maxn+5][LOG+1],suf[maxn+5][LOG+1];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
int main(){
    freopen("D.in","r",stdin);freopen("D.out","w",stdout);
    readi(n);readi(K);for (int i=1;i<=n;i++) readi(a[i]);
    for (int i=1,j=1;i<=n;i++){
        while (j<=n && a[j]+K<=a[i]) j++;
        lst[i][0]=j-1;pre[i][0]=j-1;
    }
    for (int i=n,j=n;i;i--){
        while (j && a[i]+K<=a[j]) j--;
        nxt[i][0]=j+1;suf[i][0]=j+1;
    }
    lst[0][0]=0;nxt[n+1][0]=n+1;
    for (int j=1;j<=LOG;j++){
        lst[0][j]=0;nxt[n+1][j]=n+1;
        for (int i=0;i<=n+1;i++)
            lst[i][j]=lst[lst[i][j-1]][j-1],nxt[i][j]=nxt[nxt[i][j-1]][j-1],
            pre[i][j]=pre[i][j-1]+pre[lst[i][j-1]][j-1],
            suf[i][j]=suf[i][j-1]+suf[nxt[i][j-1]][j-1];
    }
    for (readi(te);te;te--){
        int L,R,x,cnt=1;readi(L);readi(R);LL ans=R-L;
        x=L;for (int j=LOG;~j;j--) if (nxt[x][j]<=R) ans-=suf[x][j],x=nxt[x][j],cnt+=1<<j;
        x=R;for (int j=LOG;~j;j--) if (lst[x][j]>=L) ans+=pre[x][j],x=lst[x][j];
        printf("%lld\n",ans+cnt);
    }
    return 0;
}