专栏文章

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

yyokai_ing
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minndnwy
此快照首次捕获于
2025/12/02 05:14
3 个月前
此快照最后确认于
2025/12/02 05:14
3 个月前
查看原文

ZROI#3300. 舔狗的上位

很神人的题啊。。
出题人关于这道题正解是怎么想出来的的解释：
题意是一个长度为nn的序列aa和一个可操作区间长度 d (1≤d≤n≤105,1≤ai≤109)d~(1\le d\le n\le 10^5,1\le a_i\le 10^9)，每次操作为选一个长度为dd的区间，使区间中等于此区间最大值的所有数 −1-1 ，问需要最少多少次操作。
一开始有个 Θ(nV)\Theta(nV) 的做法，就是枚举 ii，算出把 aj≥ia_j\ge i的所有 jj 用长度为 dd 的区间覆盖，最少要覆盖几次，直接贪心就行，好像可以用线段树二分优化为 Θ(n2log⁡nd)\Theta(\dfrac{n^2\log{n}}d)。
然后这个做法因为你要对每个 ii 都贪心，而这个贪心的复杂度显然无法优化了，离散化完又不能再减少枚举的 ii 的数量，没什么优化空间。
所以考虑对于所有 xx 同时进行贪心，从 11 到 nn 枚举 ii，fi, xf_{i,~x} 表示对 ≥x\ge x 的数做贪心覆盖做到ii时最右边的覆盖区间的起始位置，转移：当 x≤ai,fi−1, j<i−d+1x\le a_i, f_{i-1,~j}<i-d+1时，fi, j=if_{i,~j}=i，否则 fi, j=fi−1, jf_{i,~j}=f_{i-1,~j}，可以想到直接以 (x,fi, x)(x, f_{i,~x}) 为坐标用kdt区间修改，然后答案加上 fi, x=if_{i,~x}=i 的点的数量，但这样被卡成 80pts80pts。
然后神人做法来了，我们有一个看似很没用的性质，就是 dd 是不变的，且 fi, x<i−d+1f_{i,~x}<i-d+1 的所有都会被更新为 ii，所以我们考虑建若干棵线段树，线段树kk维护 fi, j=i−kf_{i,~j}=i-k 的所有位置 jj，即，若 fi, j=i−kf_{i,~j}=i-k，则第 kk 棵线段树上下标为 jj 的位置为 11，然后当 0≤k≤d−20\le k\le d-2 时，上一线段可以覆盖 ii，但位置由 fi−1, j=(i−1)−kf_{i-1,~j}=(i-1)-k 的位置 kk 变为了现在的 fi, j=i−k−1=i−(k+1)f_{i,~j}=i-k-1=i-(k+1) 的位置 k+1k+1，所以把 0≤k≤d−20\le k\le d-2 的线段树循环右移 11 位，而对于 k>d−2k>d-2 的树，≤ai\le a_i 的位置 jj，其 fi, jf_{i,~j} 值变为 ii，所以把这些树 ≤ai\le a_i 的位置分裂出来，作为新的线段树 00，看上去要对所有 >d−2>d-2 的线段树合并 ≤ai\le a_i 的位置，但因为dd固定，后面的所有树可以合并成一棵维护 fi, j>d−2f_{i,~j}>d-2 的所有位置的线段树，这样每次只需要把这棵树分裂出 ≤ai\le a_i 的部分作为新的线段树 00，再将剩余的和线段树 d−2d-2 合并起来就行了。操作次数就是把树上位置 jj 上的 11 换成离散化后 jj 变为 j−1j-1 所需的操作次数，维护所有位置的和，每次 ansans 加上线段树 00 的权值和就行。每次做一次分裂一次合并，复杂度 Θ(nlog⁡n)\Theta(n \log{n})。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...