轉化思維的好題！

鏈接：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 = 0; char zf = 1; char ch = getchar();while (ch != '-' && !isdigit(ch)) ch = getchar();if (ch == '-') zf = -1, ch = getchar();while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf; } void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);} void writeln(const ll y){write(y);putchar('\n');} int i,j,k,m,n,x,y,z,cnt; int a[300010],c[300010]; void up(int x){for(rt i=x;i<=n;i+=i&-i)c[i]++; } int query(int x){int ans=0;for(rt i=x;i;i&=i-1)ans+=c[i];return ans; } int sta[300010],top; int L1[300010],R1[300010],L2[300010],R2[300010]; 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[600010]; struct segment{int L,R,Max,tag; }t[300010*4]; 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>>1;build(x<<1,L,mid);build(x<<1|1,mid+1,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>>1;if(mid>=L)change(x<<1,L,R,val);if(mid+1<=R)change(x<<1|1,L,R,val);t[x].Max=max(t[x<<1].Max,t[x<<1|1].Max)+t[x].tag; } int main(){n=read();ll ret=(ll)n*(n-1)/2;for(rt i=1;i<=n;i++)a[i]=read();for(rt i=1;i<=n;i++){ret-=query(a[i]-1);up(a[i]);}//ret計算初始逆序對數量 for(rt i=1;i<=n;i++){if(a[i]>sta[top]||!top)sta[++top]=a[i]; int pla=lower_bound(sta+1,sta+top+1,a[i])-sta;L1[i]=pla;L2[i]=top;}top=0;memset(sta,0,sizeof(sta));for(rt i=n;i>=1;i--){if(-a[i]>sta[top]||!top)sta[++top]=-a[i];int pla=lower_bound(sta+1,sta+top+1,-a[i])-sta;R1[i]=pla;R2[i]=top;}//L1 L2 R1 R2表示包含第i個點的合法矩形的范圍 for(rt i=1;i<=n;i++){q[2*i-1]={1,L1[i],R1[i],R2[i]};q[2*i]={-1,L2[i]+1,R1[i],R2[i]};}sort(q+1,q+2*n+1);int ttt=2;build(1,1,top);for(rt i=1;i<=2*n;i++){change(1,q[i].L,q[i].R,q[i].id);ttt=max(ttt,t[1].Max);}cout<<ret-(ttt-2)*2;return 0; }

?

轉載于:https://www.cnblogs.com/DreamlessDreams/p/9846105.html

總結

以上是生活随笔為你收集整理的「LibreOJ Round #6」花火的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。