NOI 贪心 2022 线段树并查集扫描线树状数组

冒泡排序 NOI2022

WZH2026-09-262026-09-26

[NOI2022] 冒泡排序

妙妙题 *2 。

[NOI2022] 冒泡排序。

题目描述：

有一个长度为 $n$ 的序列 $a$ 。有 $m$ 个限制，第 $i$ 个限制要求 $[l_i,r_i]$ 的最小值为 $v_i$ 。请最小化序列逆序对的数量。求出这个值。

$n,m\le 10^6,v_i\in[0,10^9]$ 。

特殊性质：

A. 保证 $v_i\in\{0,1\}$ 。
B. 保证 $l_i=r_i$ 。
C. 保证区间两两无交。

好题！性质充分！

这题一眼下去肯定是一个贪心/DP+大数据结构。经过充分观察后容易得出结论：

存在一个达到最优解的序列 $a$ ，使得 $a$ 的所有元素都为某一个 $v_i$ 。
对于任意两个 $i<j,a_i>a_j$ ，且交换 $a_i,a_j$ 后序列合法，则交换后必然更优。

然后看性质。

Part I. B

这个很简单，我们有如下贪心策略：从前往后贪心。对于每一个没有限制的点，取目前最优的选择。

想一想就能证明正确性。使用线段树可以十分容易的将复杂度做到 $\mathcal{O}(n\log n)$ 。

止步于此。

Part II. C

注意到：由于结论 $2$ ，我们得出结论，所有区间的最小值必然在端点处取到。

我怎么注意不到。

然后，类似的，限制被转化为：一些点必须满足 $a_i=v_i$ ，一些点必须满足 $a_i\ge v_i$ 。

这个就十分简单了。使用调整法可以证明（你可以不证明，因为太显然了），只需要在 B 的线段树基础上，改为求 $\ge v_i$ 的区间里的最优选择。

使用线段树可以 $\mathcal{O}(n\log n)$ 。

Part III. A

最难的部分。

由于结论 $1$ ，存在一种最优解使得序列为 $01$ 序列。

那么那些 $v_i=1$ 的限制可以认为是区间赋值。

而那些 $v_i=0$ 的限制就要求：区间里必须至少存在一个 $0$ 。

由于结论 $2$ ，一个区间内的 $0$ 越靠前越好，且越少越好。

所以下面的贪心就十分容易了：将所有区间按 $l$ 从大到小排序，然后每次只要区间里没有 $0$ ，就令区间的第一个数为 $0$ 。

之后的部分，由于结论 $2$ ，剩下没有被确定的部分必然是一段前缀 $0$ 以及后缀 $1$ 。枚举即可。

复杂度 $\mathcal{O}(n\log n)$ ，精细的实现可以做到 $\mathcal{O}(n\alpha(n))$ 。

精细实现：

首先排序可以计数排序轻松做到 $\mathcal{O}(n)$ 。

然后就是贪心的部分。我们当然可以直接使用 set 维护，然而有更加优秀的办法：家庭作业。

使用并查集维护后面第一个合法位置即可。

总结

好题目啊！

对于相交的区间，若 $v_i\ne v_j$ ，则可以让大区间蚕食小区间，变为不交的区间。

对于 $v_i=v_j$ ，仿照性质 A ，从大到小，使用并查集可以十分巧妙而简单的维护。

细节不多说，看代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1000100;
using ll=long long;
using pii=pair<int,int>;
int n,m;
struct node{int l,r;};
bool operator<(node x,node y){return x.l<y.l;}
namespace SEG{
    pii num[N<<2];
    int tag[N<<2];
    void pls(int p,int x){num[p].first+=x,tag[p]+=x;}
    void build(int p,int l,int r){
        tag[p]=0;
        num[p]={0,l};
        if(l==r)return ;
        int mid=(l+r)>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
    }
    void down(int p){
        if(!tag[p])return ;
        pls(p<<1,tag[p]);
        pls(p<<1|1,tag[p]);
        tag[p]=0;
    }
    void add(int p,int l,int r,int ql,int qr,int x){
        if(ql>qr)return ;
        if(ql<=l&&r<=qr)return pls(p,x);
        int mid=(l+r)>>1;
        down(p);
        if(mid>=ql)add(p<<1,l,mid,ql,qr,x);
        if(mid<qr)add(p<<1|1,mid+1,r,ql,qr,x);
        num[p]=min(num[p<<1],num[p<<1|1]);
    }
    pii query(int p,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return num[p];
        int mid=(l+r)>>1;
        down(p);
        if(mid>=ql&&mid<qr) 
            return min(query(p<<1,l,mid,ql,qr),query(p<<1|1,mid+1,r,ql,qr));
        if(mid>=ql)
            return query(p<<1,l,mid,ql,qr);
        return query(p<<1|1,mid+1,r,ql,qr);
    }
}using namespace SEG;
vector<node>v[N];
int am[N],ss,v1[N],v2[N];
int get(int x){return lower_bound(am+1,am+1+ss,x)-am;}
namespace BIT{
    int c[N];
    void add(int x){for(;x>=1;x-=(x&-x))c[x]++;}
    int query(int x,int cnt=0){for(;x<=ss;x+=(x&-x))cnt+=c[x];return cnt;}
}using namespace BIT;
int f[N];
int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
int L[N],R[N],V[N];
void WZH(){
    ss=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",L+i,R+i,V+i);
        am[++ss]=V[i];
    }
    sort(am+1,am+1+ss);ss=unique(am+1,am+1+ss)-am-1;
    for(int i=1;i<=ss;i++)v[i].clear();
    for(int i=1;i<=n+1;i++)f[i]=i,v1[i]=v2[i]=0;
    for(int i=1;i<=m;i++)V[i]=get(V[i]),v[V[i]].push_back({L[i],R[i]});
    int flag=1;
    for(int i=ss;i>=1&&flag;i--)if(v[i].size()){
        int lst=n+1;
        sort(v[i].begin(),v[i].end());
        for(int j=(int)(v[i].size())-1;~j&&flag;j--){
            node u=v[i][j];
            if(u.r<lst){
                int pos=getf(u.l);
                v1[pos]=i;
                flag&=(pos<=u.r);
                lst=pos;
            }
        }
        for(node u:v[i])for(int j=getf(u.l);j<=u.r;j=getf(j))  
            v2[j]=i,f[j]=j+1;
    }
    if(!flag){puts("-1");return ;}
    for(int i=1;i<=ss;i++)c[i]=0;
    ll ans=0;
    build(1,0,ss+1);
    for(int i=1;i<=n;i++){
        if(v1[i])
            ans+=query(v1[i]+1),add(v1[i]),add(1,0,ss+1,v1[i]+1,ss+1,1);
    }
    for(int i=1;i<=n;i++){
        if(v1[i]){
            add(1,0,ss+1,0,v1[i]-1,1);
            add(1,0,ss+1,v1[i]+1,ss+1,-1);
        }
        else{
            pii t=query(1,0,ss+1,v2[i],ss+1);
            ans+=t.first;
            add(1,0,ss+1,0,t.second-1,1);
        }
    }
    printf("%lld\n",ans);
}
int main(){
    int T;scanf("%d",&T);
    while(T--)WZH();
    return 0;
}

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
using ll=long long;
int n,m,T,c[N],a[N];
struct node{int l,r,v;}q[N];
set<int>s,S;
void WZH(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+2;i++)c[i]=0,a[i]=-1;
    int tot=0;
    for(int i=1;i<=m;i++){
        int l,r,v;
        scanf("%d%d%d",&l,&r,&v);
        if(v==1)c[l]++,c[r+1]--;
        else q[++tot]={l,r,v};
    }
    sort(q+1,q+1+tot,[](node x,node y){return x.l<y.l;});
    s.clear();S.clear();
    for(int i=1;i<=n;i++)c[i]+=c[i-1];
    for(int i=1;i<=n;i++)if(c[i]==0)s.insert(i);else a[i]=1;
    for(int i=tot;i>=1;i--){
        set<int>::iterator it=S.lower_bound(q[i].l);
        if(it!=S.end()&&*it<=q[i].r)continue;
        set<int>::iterator it2=s.lower_bound(q[i].l);
        if(it2==s.end()||*it2>q[i].r){return puts("-1"),void();}
        a[*it2]=0;
        S.insert(*it2);
        s.erase(*it2);
    }
    int cnt0=0,cnt1=0;
    ll ans=0,res=0;
    for(int i=1;i<=n;i++){
        if(a[i]==1||a[i]==-1)
            cnt1++;
        else ans+=cnt1;
    }
    res=ans;
    cnt0=cnt1=0;
    for(int i=n;i>=1;i--)cnt0+=(a[i]==0);
    for(int i=1;i<=n;i++){
        if(a[i]==1)cnt1++;
        if(a[i]==0)cnt0--;
        if(a[i]==-1)ans+=cnt1-cnt0;
        res=min(res,ans);
    }
    printf("%lld\n",res);
}
int main(){
    scanf("%d",&T);
    while(T--)WZH();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
using ll=long long;
int n,m,T,a[N],am[N],ss,num[N],tag[N],pos[N];
void pls(int p,int x){num[p]+=x,tag[p]+=x;}
void build(int p,int l,int r){
    num[p]=tag[p]=0;pos[p]=l;
    if(l==r)return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void down(int p){
    if(!tag[p])return ;
    pls(p<<1,tag[p]);
    pls(p<<1|1,tag[p]);
    tag[p]=0;
}
void add(int p,int l,int r,int ql,int qr,int x){
    if(ql>qr)return ;
    if(ql<=l&&r<=qr)return pls(p,x);
    int mid=(l+r)>>1;
    down(p);
    if(mid>=ql)add(p<<1,l,mid,ql,qr,x);
    if(mid<qr)add(p<<1|1,mid+1,r,ql,qr,x);
    if(num[p<<1]<num[p<<1|1]){
        num[p]=num[p<<1];
        pos[p]=pos[p<<1];
    }
    else{
        num[p]=num[p<<1|1];
        pos[p]=pos[p<<1|1];
    }
}
int query(int p,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return num[p];
    int mid=(l+r)>>1;
    down(p);
    if(mid>=ql&&mid<qr) 
        return min(query(p<<1,l,mid,ql,qr),query(p<<1|1,mid+1,r,ql,qr));
    if(mid>=ql)
        return query(p<<1,l,mid,ql,qr);
    return query(p<<1|1,mid+1,r,ql,qr);
}
int get(int x){return lower_bound(am+1,am+1+ss,x)-am;}
void WZH(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)a[i]=-1;
    ss=0;
    int flag=0;
    for(int i=1,l,r,v;i<=m;i++){
        scanf("%d%d%d",&l,&r,&v);
        am[++ss]=v;
        if(a[l]==-1)a[l]=v;
        else if(a[l]!=v)flag=1;
    }
    if(flag)return puts("-1"),void();
    sort(am+1,am+1+ss);ss=unique(am+1,am+1+ss)-am-1;
    build(1,1,ss);
    for(int i=1;i<=n;i++){
        if(~a[i])
            add(1,1,ss,get(a[i])+1,ss,1);
    }
    for(int i=1;i<=n;i++){
        if(~a[i]){
            int t=get(a[i]);
            add(1,1,ss,1,t-1,1);
            add(1,1,ss,t+1,ss,-1);
        }
        else{
            a[i]=am[pos[1]];
        }
    }
    ll ans=0;
    build(1,1,ss);
    for(int i=1;i<=n;i++){
        int t=get(a[i]);
        ans+=query(1,1,ss,t,t);
        add(1,1,ss,1,t-1,1);
    }
    printf("%lld\n",ans);
}
int main(){
    scanf("%d",&T);
    while(T--)WZH();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
using ll=long long;
int n,m,T,a[N],am[N],ss;
using pii=pair<int,int>;
pii num[N<<2];
int tag[N<<2];
void pls(int p,int x){num[p].first+=x,tag[p]+=x;}
void build(int p,int l,int r){
    tag[p]=0;
    num[p]={0,l};
    if(l==r)return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void down(int p){
    if(!tag[p])return ;
    pls(p<<1,tag[p]);
    pls(p<<1|1,tag[p]);
    tag[p]=0;
}
void add(int p,int l,int r,int ql,int qr,int x){
    if(ql>qr)return ;
    if(ql<=l&&r<=qr)return pls(p,x);
    int mid=(l+r)>>1;
    down(p);
    if(mid>=ql)add(p<<1,l,mid,ql,qr,x);
    if(mid<qr)add(p<<1|1,mid+1,r,ql,qr,x);
    num[p]=min(num[p<<1],num[p<<1|1]);
}
pii query(int p,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return num[p];
    int mid=(l+r)>>1;
    down(p);
    if(mid>=ql&&mid<qr) 
        return min(query(p<<1,l,mid,ql,qr),query(p<<1|1,mid+1,r,ql,qr));
    if(mid>=ql)
        return query(p<<1,l,mid,ql,qr);
    return query(p<<1|1,mid+1,r,ql,qr);
}
int get(int x){return lower_bound(am+1,am+1+ss,x)-am;}
int b[N];
void WZH(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)a[i]=-1,b[i]=0;
    ss=0;
    for(int i=1,l,r,v;i<=m;i++){
        scanf("%d%d%d",&l,&r,&v);
        am[++ss]=v;
        a[l]=v;
        for(int j=l+1;j<=r;j++)
            b[j]=v;
    }
    sort(am+1,am+1+ss);ss=unique(am+1,am+1+ss)-am-1;
    for(int i=1;i<=n;i++)b[i]=get(b[i]);
    build(1,1,ss);
    for(int i=1;i<=n;i++)if(~a[i])a[i]=get(a[i]);
    for(int i=1;i<=n;i++){
        if(~a[i])
            add(1,1,ss,a[i]+1,ss,1);
    }
    for(int i=1;i<=n;i++){
        if(~a[i]){
            add(1,1,ss,1,a[i]-1,1);
            add(1,1,ss,a[i]+1,ss,-1);
        }
        else{
            a[i]=query(1,1,ss,b[i],ss).second;
            add(1,1,ss,1,a[i]-1,1);
        }
    }
    ll ans=0;
    build(1,1,ss);
    for(int i=1;i<=n;i++){
        ans+=query(1,1,ss,a[i],a[i]).first;
        add(1,1,ss,1,a[i]-1,1);
    }
    printf("%lld\n",ans);
}
int main(){
    scanf("%d",&T);
    while(T--)WZH();
    return 0;
}