「LibreOJ Round #6」花火

转化思维的好题！

链接：here

大致题意：

有$ n$个数字，你每次可以交换相邻两个，还有一次交换任意两个元素的机会，求最少的交换次数使得这些数字升序排序(原数列两两不同)

$ solotion：$

首先有一个结论：交换任意两个元素可以选择在第一次交换，且一定不会劣

证明：假设不在第一次交换，可以通过倒推这次交换的贡献，使得这次机会平移到第一次交换，结果不变

第二个结论：交换相邻两个元素的次数等于逆序对数

证明：略

第三个结论：交换两个元素$ x,y$，所能够减少的逆序对数量等价于把每个数$ a_i$对应到坐标$ (i,a_i)$之后矩形{$(x,a_x),(y,a_y)$}中的点数$ *2+1$(不包含边界)

证明：在矩形内的每个点，原先会贡献$ 2$的逆序对，交换后将不再产生这样的贡献。$ +1$是因为交换本身会减少一个逆序对

也就是说我们实际要求的等价于找到一个矩形(两个角都在点上)，使得矩形内点尽量多

这并不容易直接处理，考虑转化题意

选择的矩形两个角$(x,a_x),(y,a_y)$有性质如下：$(x<y)$

$ 1.a_x>a_y$ 证明：否则会增加逆序对数量，肯定不优

$ 2.a_x$是前缀最大值，$ a_y$是后缀最小值

证明:如果$ a_x$不是前缀最大值,一定有一个点$ (k,a_k)$在$ (x,a_x)$的左上方，这样的矩形能够完全包含矩形{$(x,a_x),(y,a_y)$}使得$ (x,a_x)$不可能成为最优，后缀最小值同理。

这样我们获得了一个前缀最大值数组$ S$,一个后缀最小值数组$ T$，我们对于每个点，计算哪些矩形能够包含这个点

显然包含这个点的矩形左端点要在这个点的左上方，右端点在这个点的右下方，可以通过两次二分得到包含这个点的两段数组区间

我们用$ (x,y)$表示左端点是前缀最大值第$ x$个，右端点是后缀最小值第$ y$个的矩形，可以发现能包含这个点的矩形用坐标表示后也是一个矩形

然后就把题意转化成有若干个矩形，求一个被最多矩形覆盖的位置扫描线+线段树维护即可

时间复杂度:$ O(n log n)$

code:

#include<ctime>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#define file(x)freopen(x".in","r",stdin);freopen(x".out","w",stdout)

#define rt register int

#define ll long long

using namespace std;

inline ll read(){

    ll x = ; char zf = ; char ch = getchar();

    while (ch != '-' && !isdigit(ch)) ch = getchar();

    if (ch == '-') zf = -, ch = getchar();

    while (isdigit(ch)) x = x *  + ch - '', ch = getchar(); return x * zf;

}

void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}

void writeln(const ll y){write(y);putchar('\n');}

int i,j,k,m,n,x,y,z,cnt;

int a[],c[];

void up(int x){

    for(rt i=x;i<=n;i+=i&-i)c[i]++;

}

int query(int x){

    int ans=;

    for(rt i=x;i;i&=i-)ans+=c[i];

    return ans;

}

int sta[],top;

int L1[],R1[],L2[],R2[];

struct query{

    int id,x,L,R;

    bool operator <(const query s)const{

        if(x==s.x)return id<s.id;

        return x<s.x;

    }

}q[];

struct segment{

    int L,R,Max,tag;

}t[*];

void build(int x,int L,int R){

    t[x].L=L;t[x].R=R;if(L==R)return;

    const int mid=L+R>>;

    build(x<<,L,mid);build(x<<|,mid+,R);

}

void change(int x,int L,int R,int val){

    if(t[x].L>=L&&t[x].R<=R){

        t[x].tag+=val;

        t[x].Max+=val;

        return;

    }

    const int mid=t[x].L+t[x].R>>;

    if(mid>=L)change(x<<,L,R,val);

    if(mid+<=R)change(x<<|,L,R,val);

    t[x].Max=max(t[x<<].Max,t[x<<|].Max)+t[x].tag;

}

int main(){

    n=read();ll ret=(ll)n*(n-)/;

    for(rt i=;i<=n;i++)a[i]=read();

    for(rt i=;i<=n;i++){

        ret-=query(a[i]-);

        up(a[i]);

    }//ret计算初始逆序对数量

    for(rt i=;i<=n;i++){

        if(a[i]>sta[top]||!top)sta[++top]=a[i];

        int pla=lower_bound(sta+,sta+top+,a[i])-sta;

        L1[i]=pla;L2[i]=top;

    }top=;

    memset(sta,,sizeof(sta));

    for(rt i=n;i>=;i--){

        if(-a[i]>sta[top]||!top)sta[++top]=-a[i];

        int pla=lower_bound(sta+,sta+top+,-a[i])-sta;

        R1[i]=pla;R2[i]=top;

    }//L1 L2 R1 R2表示包含第i个点的合法矩形的范围

    for(rt i=;i<=n;i++){

        q[*i-]={,L1[i],R1[i],R2[i]};

        q[*i]={-,L2[i]+,R1[i],R2[i]};

    }

    sort(q+,q+*n+);int ttt=;

    build(,,top);

    for(rt i=;i<=*n;i++){

        change(,q[i].L,q[i].R,q[i].id);

        ttt=max(ttt,t[].Max);

    }

    cout<<ret-(ttt-)*;

    return ;

}

巴特西

「LibreOJ Round #6」花火

最新文章

热门文章