Liveddd's Blog

愛にできることはまだあるかい

LOJ#3851. 「NOI2022」冒泡排序

发表于 更新于 分类于
本文字数： 7.2k 阅读时长 ≈ 16 分钟

非常好题目。

经典结论，冒泡排序交换次数等于逆序对个数。容易发现这可能出现限制中的 $m$ 个数。注意非常好特殊性质，我们从其中逐渐入手。

特殊性质 A

限制 $(l,r,1)$ 相当于钦定 $i\in[l,r],a_i=1$；限制 $(l,r,0)$ 相当于要求存在一个 $a_i=0$。考虑贪心

特殊性质 B

容易得到一个结论：最优情况下，所有未被限制的数之间都不会产生逆序对。

这个过程满足决策单调性，并且局部最优解就是全局最优解。考虑与 CF1601C Optimal Insertion 类似的做法，使用线段树维护所有 $m$ 个取值对应的贡献。时间复杂度 $\mathcal O(n\log n)$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<iostream>
#include<cstdio>
#include<algorithm>
#define fir first
#define sec second
using namespace std;
using ll=long long;
using PII=pair<int,int>;
const int N=1e6+10,INF=1e9;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int T,n,m;
int a[N];
int tot,c[N];

struct SegmentTree
{
    struct Node
    {
        int l,r;
        PII v;
        int tag;
    }tr[N<<2];
    void pushup(int x){tr[x].v=min(tr[x<<1].v,tr[x<<1|1].v);}
    void update(int x,int k){tr[x].v.fir+=k,tr[x].tag+=k;}
    void pushdown(int x)
    {
        if(!tr[x].tag)return ;
        update(x<<1,tr[x].tag),update(x<<1|1,tr[x].tag);
        tr[x].tag=0;
    }
    void build(int l,int r,int x=1)
    {
        tr[x].l=l,tr[x].r=r,tr[x].tag=0;
        if(l==r)return tr[x].v={0,l},void();
        int mid=l+r>>1;
        build(l,mid,x<<1),build(mid+1,r,x<<1|1);
        pushup(x);
    }
    void modify(int l,int r,int k,int x=1)
    {
        if(l>r)return ;
        if(l<=tr[x].l&&tr[x].r<=r)return update(x,k);
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        if(l<=mid)modify(l,r,k,x<<1);
        if(r>mid)modify(l,r,k,x<<1|1);
        pushup(x);
    }
    PII query(int l,int r,int x=1)
    {
        if(l<=tr[x].l&&tr[x].r<=r)return tr[x].v;
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        PII res={INF,INF};
        if(l<=mid)res=min(res,query(l,r,x<<1));
        if(r>mid)res=min(res,query(l,r,x<<1|1));
        return res;
    }
}seg;
inline void solve()
{
    read(n,m);
    for(int i=1;i<=n;i++)a[i]=0;
    tot=0;
    bool flag=0;
    for(int i=1,l,r,v;i<=m;i++)
    {
        read(l,r,v);
        if(a[l]&&a[l]!=v)flag=1;
        c[++tot]=a[l]=v;
    }
    if(flag)return puts("-1"),void();
    sort(c+1,c+1+tot);
    tot=unique(c+1,c+1+tot)-c-1;
    seg.build(1,tot);
    ll ans=0;
    for(int i=n;i;i--)
        if(a[i])
        {
            a[i]=lower_bound(c+1,c+1+tot,a[i])-c;
            ans+=seg.query(a[i],a[i]).fir;
            seg.modify(a[i]+1,tot,1);
        }
    for(int i=1;i<=n;i++)
    {
        if(a[i])
        {
            seg.modify(1,a[i]-1,1);
            seg.modify(a[i]+1,tot,-1);
        }
        else ans+=seg.tr[1].v.fir;
    }
    printf("%lld\n",ans);
}
int main()
{
    freopen("bubble.in","r",stdin);
    freopen("bubble.out","w",stdout);     
    read(T); 
    while(T--)solve();
    return 0;
}

特殊性质 C

容易发现对于限制 $(l,r,v)$，我们可以直接钦定 $a_l=v$，这样显然是最优的。现在相当于 特殊性质 B 加上一些 $a_i \ge v$ 的限制。策略就是跟 特殊性质 B 做法一样，不过在线段树上取 $\ge v$ 的值对应的最优答案，如果有相同的就取最小的。

正确性可以感性理解。因为尽可能小对后面答案产生的影响更小。考虑局部最优，如果当前选择 $x$，若存在更优的 $y<x$，那么替换为 $y$ 显然更优。并且加入

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<iostream>
#include<cstdio>
#include<algorithm>
#define fir first
#define sec second
using namespace std;
using ll=long long;
using PII=pair<int,int>;
const int N=1e6+10,INF=1e9;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int T,n,m;
struct Lim{int l,r,v;}a[N];
int v[N],low[N];
int tot,c[N];
struct SegmentTree
{
    struct Node
    {
        int l,r;
        PII v;
        int tag;
    }tr[N<<2];
    void pushup(int x){tr[x].v=min(tr[x<<1].v,tr[x<<1|1].v);}
    void update(int x,int k){tr[x].v.fir+=k,tr[x].tag+=k;}
    void pushdown(int x)
    {
        if(!tr[x].tag)return ;
        update(x<<1,tr[x].tag),update(x<<1|1,tr[x].tag);
        tr[x].tag=0;
    }
    void build(int l,int r,int x=1)
    {
        tr[x].l=l,tr[x].r=r,tr[x].tag=0;
        if(l==r)return tr[x].v={0,l},void();
        int mid=l+r>>1;
        build(l,mid,x<<1),build(mid+1,r,x<<1|1);
        pushup(x);
    }
    void modify(int l,int r,int k,int x=1)
    {
        if(l>r)return ;
        if(l<=tr[x].l&&tr[x].r<=r)return update(x,k);
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        if(l<=mid)modify(l,r,k,x<<1);
        if(r>mid)modify(l,r,k,x<<1|1);
        pushup(x);
    }
    PII query(int l,int r,int x=1)
    {
        if(l<=tr[x].l&&tr[x].r<=r)return tr[x].v;
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        PII res={INF,INF};
        if(l<=mid)res=min(res,query(l,r,x<<1));
        if(r>mid)res=min(res,query(l,r,x<<1|1));
        return res;
    }
}seg;
inline void solve()
{
    read(n,m);
    for(int i=1;i<=n;i++)v[i]=low[i]=-1;
    tot=0;
    for(int i=1;i<=m;i++)
    {
        read(a[i].l,a[i].r,a[i].v);
        c[++tot]=a[i].v;
    }
    sort(c+1,c+1+tot);
    tot=unique(c+1,c+1+tot)-c-1;
    for(int i=1;i<=m;i++)
    {
        a[i].v=lower_bound(c+1,c+1+tot,a[i].v)-c;
        v[a[i].l]=a[i].v;
        for(int j=a[i].l;j<=a[i].r;j++)low[j]=a[i].v;
    }
    seg.build(0,tot);
    for(int i=1;i<=n;i++)if(~v[i])seg.modify(v[i]+1,tot,1);
    for(int i=1;i<=n;i++)
    {
        if(~v[i])seg.modify(low[i]+1,tot,-1);
        else v[i]=seg.query(low[i],tot).sec;
        seg.modify(0,v[i]-1,1);
    }
    //calc
    seg.build(0,tot);
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=seg.query(v[i],v[i]).fir;
        seg.modify(0,v[i]-1,1);
    }
    printf("%lld\n",ans);
}
int main()
{
    freopen("bubble.in","r",stdin);
    freopen("bubble.out","w",stdout);     
    read(T);
    while(T--)solve();
    return 0;
}