我在做最后一道题的时候，这道题因为本身是非常难的吗

· · 题解

ZROI#3300. 舔狗的上位

很神人的题啊。。

出题人关于这道题正解是怎么想出来的的解释：

题意是一个长度为n的序列a和一个可操作区间长度 d~(1\le d\le n\le 10^5,1\le a_i\le 10^9)，每次操作为选一个长度为d的区间，使区间中等于此区间最大值的所有数 -1 ，问需要最少多少次操作。

一开始有个 \Theta(nV) 的做法，就是枚举 i，算出把 a_j\ge i的所有 j 用长度为 d 的区间覆盖，最少要覆盖几次，直接贪心就行，好像可以用线段树二分优化为 \Theta(\dfrac{n^2\log{n}}d)。

然后这个做法因为你要对每个 i 都贪心，而这个贪心的复杂度显然无法优化了，离散化完又不能再减少枚举的 i 的数量，没什么优化空间。

所以考虑对于所有 x 同时进行贪心，从 1 到 n 枚举 i，f_{i,~x} 表示对 \ge x 的数做贪心覆盖做到i时最右边的覆盖区间的起始位置，转移：当 x\le a_i, f_{i-1,~j}<i-d+1时，f_{i,~j}=i，否则 f_{i,~j}=f_{i-1,~j}，可以想到直接以 (x, f_{i,~x}) 为坐标用kdt区间修改，然后答案加上 f_{i,~x}=i 的点的数量，但这样被卡成 80pts。

然后神人做法来了，我们有一个看似很没用的性质，就是 d 是不变的，且 f_{i,~x}<i-d+1 的所有都会被更新为 i，所以我们考虑建若干棵线段树，线段树k维护 f_{i,~j}=i-k 的所有位置 j，即，若 f_{i,~j}=i-k，则第 k 棵线段树上下标为 j 的位置为 1，然后当 0\le k\le d-2 时，上一线段可以覆盖 i，但位置由 f_{i-1,~j}=(i-1)-k 的位置 k 变为了现在的 f_{i,~j}=i-k-1=i-(k+1) 的位置 k+1，所以把 0\le k\le d-2 的线段树循环右移 1 位，而对于 k>d-2 的树，\le a_i 的位置 j，其 f_{i,~j} 值变为 i，所以把这些树 \le a_i 的位置分裂出来，作为新的线段树 0，看上去要对所有 >d-2 的线段树合并 \le a_i 的位置，但因为d固定，后面的所有树可以合并成一棵维护 f_{i,~j}>d-2 的所有位置的线段树，这样每次只需要把这棵树分裂出 \le a_i 的部分作为新的线段树 0，再将剩余的和线段树 d-2 合并起来就行了。操作次数就是把树上位置 j 上的 1 换成离散化后 j 变为 j-1 所需的操作次数，维护所有位置的和，每次 ans 加上线段树 0 的权值和就行。每次做一次分裂一次合并，复杂度 \Theta(n \log{n})。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010
#define ll long long
struct node{
    int ls,rs,sum;
    void clear(){
        ls=rs=sum=0;
    }
}tree[MAXN*30];
int rt[MAXN],n,d,t;
int a[MAXN],st[MAXN*30];
int top,cnt,b[MAXN];
int New(){return top?st[top--]:++cnt;}
void del(int x){
    tree[x].clear();
    st[++top]=x;
}
void pushup(int u){
    int ls=tree[u].ls,rs=tree[u].rs;
    tree[u].sum=tree[ls].sum+tree[rs].sum;
}
int merge(int u,int v,int l,int r){
    if(!u||!v)return u+v;
    if(l==r){
        tree[u].sum+=tree[v].sum;
        del(v);
        return u;
    }
    int mid=(l+r)/2;
    tree[u].ls=merge(tree[u].ls,tree[v].ls,l,mid);
    tree[u].rs=merge(tree[u].rs,tree[v].rs,mid+1,r);
    pushup(u),del(v);
    return u;
}
void split(int &u,int &v,int l,int r,int L,int R){
    if(L>r||R<l||!u)return;
    if(L<=l&&r<=R){
        v=u,u=0;
        return;
    }
    if(!v)v=New();
    int mid=(l+r)/2;
    split(tree[u].ls,tree[v].ls,l,mid,L,R);
    split(tree[u].rs,tree[v].rs,mid+1,r,L,R);
    pushup(u),pushup(v);
}
void update(int &u,int l,int r,int x,int y){
    if(!u)u=New();
    if(l==r){
        tree[u].sum+=y;
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid)update(tree[u].ls,l,mid,x,y);
    else update(tree[u].rs,mid+1,r,x,y);
    pushup(u);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>d;
        for(int i=1;i<=n;i++)
            cin>>a[i],b[i]=a[i];
        sort(b+1,b+1+n);
        int m=unique(b+1,b+1+n)-b-1;
        for(int i=1;i<=n;i++)
            a[i]=lower_bound(b+1,b+1+m,a[i])-b;
        for(int i=1;i<=n;i++)
            update(rt[0],1,m,i,b[i]-b[i-1]);
        ll ans=0;
        for(int i=1;i<=n;i++){
            split(rt[0],rt[i],1,m,1,a[i]);
            ans+=tree[rt[i]].sum;
            if(i>=d)
                rt[0]=merge(rt[0],rt[i-d+1],1,m);
        }
        cout<<ans<<"\n";
        for(int i=0;i<=n;i++)
            rt[i]=0;
        for(int i=1;i<=cnt;i++)
            tree[i].clear();
        cnt=top=0;
    }
    return 0;
}