[CF407E]k-d-sequence

壹、题目描述 ¶

传送门 to Luogu

贰、题解 ¶

一般情形,如果 \(d\neq 0\),那么一段区间 \([L,R]\) 合法的基础条件是

\[\forall i,j\in [L,R],a_i\equiv a_j\pmod d\;\and\;\forall i,j\in[L,R],a_i\neq a_j \]

那么,我们得特别处理一下 \(d=0\),可以 \(\mathcal O(n)\) 扫一遍,不赘述。

对于 \(d>0\) 的情况,我们可以将一段取模 \(d\) 余数相同的区间拿出来单独处理。

不过这里还有个小问题,如何排除相同的数字反复出现?我们可以使用类似 $\rm two-pointer$ 的方法,移动 $R$ 时,看一看 $a_R$ 上一次出现的位置,与 $L$ 取 $\max$ 即可,但下文结合需要所求,使用了一种更有效的处理方法,会被提及。

现在,我们有了一段可能会出现答案的区间 \([L,R]\),并将它们拿出来单独处理,我们假设将它们放到一个新的数组 \(b\) 上,现在,我们考虑如何在这个数组上得到合法的区间。我们可以先令 \(b_i\leftarrow \left\lfloor{b_i\over d}\right\rfloor\),因为我们不用担心余数问题了。

先搞清楚限制条件,对于 \(b\) 的一段区间 \([L,R]\),合法的条件是

\[\max-\min+1-(R-L+1)\le k\Rightarrow \max-\min+L-R\le k \]

也就是我们需要得到一个区间的最大或最小值,但是还有 \(L,R\),这怎么处理?

考虑依次移动右端点,维护每个左端点对应上述的值,那么,现在右端点在我们手上,即右端点可以看做是 “固定” 的,对于每个左端点,我们需要维护 \([L,R]\) 的最大值和最小值,这个时候引入单调栈+线段树!具体来说,维护单增单减的两个栈,单增栈维护最小值,单减栈维护最大值,可以这样看:

[CF407E]k-d-sequence

对于红色的这个值,它负责的就是 \([i+1,j]\) 这个区间的最小值。

或者说我们为什么要使用单调栈,其本质原因是随着 \(L\) 的变小,它的 最小值/最大值 只会逐渐往极端走,不可能会 “回转”。

对于单减的栈原理也是一样。

当我们移动 \(R\) 时,要将 \(b_R\) 加入这两个栈,举单增的栈(维护最小值)来说:当我们要将 \(i\) 弹出栈时,设 \(i\) 后一个元素为 \(j\),我们需要将 \([j+1,i]\) 都先加上 \(b_i\),因为这原来是 \(b_i\) 负责这段区间的最小值,现在换成 \(b_R\) 后,先将 \(b_i\) 的影响去掉,当我们遇到 \(k\) 而弹不动时,退出循环,再将 \([k+1,R]\) 都整体减去 \(b_R\),因为此时 \(b_R\) 是这段区间的最小值。

而当我们移动 \(R\) 时,要注意将整个区间(不同于 \([1,R]\))都减去 \(1\),而将 \(R\) 这个单点加上 \(R\)(因为有 \(+L\) 这个项,而线段树本质是在维护每个 \(L\) 对应的上述表达式的值,而 \(R\) 同时也是一个新的左端点)。

处理完这些之后,在线段树上二分找到最小的 \(L\) 满足上述表达式小于等于 \(k\) 即可。

但是需要处理一个问题 —— 出现重复的数,假设加入 \(b_R\),发现其重复出现,上一次出现的位置在 \(p\),那么我们只需要令所有 \([1,p]\) 的线段树上的值为 \(+\infty\) 即可 —— 这样线段树二分时这段区间必然不满足其值小于等于 \(k\).

总的复杂度就是 \(\mathcal O(n\log n)\) 了。

叁、参考代码 ¶

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<map>
#include<stack>
using namespace std;

// #define NDEBUG
#include<cassert>

namespace Elaina{
    #define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
    #define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
    #define fi first
    #define se second
    #define mp(a, b) make_pair(a, b)
    #define Endl putchar('\n')
    #define mmset(a, b) memset(a, b, sizeof a)
    // #define int long long
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    template<class T>inline T fab(T x){ return x<0? -x: x; }
    template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
    template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
    template<class T>inline T readin(T x){
        x=0; int f=0; char c;
        while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
        for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
        return f? -x: x;
    }
    template<class T>inline void writc(T x, char s='\n'){
        static int fwri_sta[1005], fwri_ed=0;
        if(x<0) putchar('-'), x=-x;
        do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
        while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
        putchar(s);
    }
}
using namespace Elaina;

const int maxn=2e5;
const int inf=1e9+1;

int n, k, d;
int a[maxn+5];

inline void input(){
    n=readin(1), k=readin(1), d=readin(1);
    rep(i, 1, n) a[i]=readin(1)+inf;
}

namespace special{
    inline int launch(){
        int len=1, l=1, cur=1;
        rep(i, 2, n){
            if(a[i]==a[i-1]) ++cur;
            else cur=1;
            if(cur>len) len=cur, l=i-cur+1;
        }
        writc(l, ' '), writc(l+len-1);
        return 0;
    }
}

int len, l, s;
namespace saya{
    ll tag[maxn<<2|2], mn[maxn<<2|2];
    #define ls (i<<1)
    #define rs (i<<1|1)
    #define mid ((l+r)>>1)
    #define _lq ls, l, mid
    #define _rq rs, mid+1, r
    void build(int i, int l, int r){
        tag[i]=mn[i]=0;
        if(l==r) return;
        build(_lq), build(_rq);
    }
    inline void update(int i, ll x){ tag[i]+=x, mn[i]+=x; }
    inline void pushup(int i){ mn[i]=min(mn[ls], mn[rs]); }
    inline void pushdown(int i){
        update(ls, tag[i]), update(rs, tag[i]);
        tag[i]=0;
    }
    void modify(int i, int l, int r, int L, int R, ll x){
        if(L<=l && r<=R) return update(i, x);
        if(tag[i]) pushdown(i);
        if(L<=mid) modify(_lq, L, R, x);
        if(mid<R) modify(_rq, L, R, x);
        pushup(i);
    }
    int query(int i, int l, int r, int k){
        if(mn[i]>k) return -1;
        if(l==r) return l;
        if(tag[i]) pushdown(i);
        if(mn[ls]<=k) return query(_lq, k);
        return query(_rq, k);
    }
    void check(int i, int l, int r){
        if(l==r) return printf("val[%d] == %lld\n", l, mn[i]), void();
        if(tag[i]) pushdown(i);
        check(_lq), check(_rq);
    }
    #undef ls
    #undef rs
    #undef mid
    #undef _lq
    #undef rq
}

map<int, int>pos;
stack<int>up, down;
int b[maxn+5];
inline void solve(int L, int R){
    /** prelude */
    s=R-L+1;
    rep(i, L, R) b[i-L+1]=a[i]/d;
    
    /** some clear */
    saya::build(1, 1, s); pos.clear();
    while(!up.empty()) up.pop();
    while(!down.empty()) down.pop();
    up.push(0), down.push(0);
    /** enumerate the right endpos */
    rep(i, 1, s){
        saya::modify(1, 1, s, 1, s, -1); saya::modify(1, 1, s, i, i, i);

        /** @p inf shoule be large enough, but it shouldn't to too large */
        if(pos.count(b[i])) saya::modify(1, 1, s, 1, pos[b[i]], inf);
        pos[b[i]]=i;

        /** maintain the minimum value */
        while(up.top() && b[up.top()]>b[i]){
            int pre=up.top(); up.pop();
            saya::modify(1, 1, s, up.top()+1, pre, b[pre]);
        }
        saya::modify(1, 1, s, up.top()+1, i, -b[i]);
        up.push(i);

        /** maintain the maximum value */
        while(down.top() && b[down.top()]<b[i]){
            int pre=down.top(); down.pop();
            saya::modify(1, 1, s, down.top()+1, pre, -b[pre]);
        }
        saya::modify(1, 1, s, down.top()+1, i, b[i]);
        down.push(i);

        /** DEBUG */
        // printf("When i == %d, the segment tre:>\n", i);
        // saya::check(1, 1, s);

        /** get the legal left endpos */
        int ret=saya::query(1, 1, s, k);
        // printf("When i == %d, ret == %d\n", i, ret);
        if(ret!=-1 && i-ret+1>len) len=i-ret+1, l=L+ret-1;
        // printf("When i == %d, l == %d, len == %d\n", i, l, len);
    }
    // printf("successfully quit!\n");
}

signed main(){
    input();
    if(d==0) return special::launch();
    int lst=1;
    rep(i, 2, n+1) if(a[i]%d!=a[lst]%d || i==n+1)
        solve(lst, i-1), lst=i;
    writc(l, ' '), writc(l+len-1, '\n');
    return 0;
}

肆、关键之处 ¶

真不知道该怎么说,但是这种移动右端点,维护左端点真该学一下,同时使用单调栈维护最大最小值。

上一篇:数据库生成序列号,无论那个数据库 都有这几句话


下一篇:2019.7.13 义乌模拟赛 T4 sequence