Swapping Problem

題解

很水的一道題

我們考慮交換那些數時會對答案產生貢獻，
我們可以先將所有的線段分成 a > b a>b a>b與 a < b a<b a<b的兩類，分別記作 x , y x,y x,y，很明顯，同一類中的交換，絕對是不優的，
而不同的類中的交換，若 x , y x,y x,y沒有重合部分，那么也是不優的，對于有重合部分的 x , y x,y x,y，它們所產生的貢獻就是它們重合部分的兩倍，這個手畫一下就知道了
所以，我們要做的是，從兩個集合中找出重合部分最長的兩個線段，

我們可以先將所有的 y y y按左端點排序，再去掉所有被包含的線段，即排序后右端點不大于前者右端點的，
很明顯，子線段是不會優于母線段的，
這樣，我們就可以保證無論是左端點還是右端點，都是不降的了，
對于每個 x x x，我們先二分出與其左端點相交的最近的和與右端點相交的最近的線段，這兩者明顯對于所有沒有包含于它的線段是最優的，
它們之間的線段是整段都被包含，它們的長度就是它們的貢獻，我們只需要用st表找出它們的最大長度即可，

時間復雜度 O ( n l o g ? n ) O\left(nlog\,n\right) O(nlogn)，

原始碼

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define lowbit(x) (x&-x)
#define reg register
typedef long long LL;
typedef unsigned long long uLL;
typedef unsigned int uint;
const int INF=0x7f7f7f7f;
const int jzm=233;
const int mo=998244353;
const double Pi=acos(-1.0);
typedef pair<int,int> pii;
const double PI=acos(-1.0);
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
int n,tot1,tot2,lg[MAXN],st[22][MAXN];LL num,ans;
struct ming{int a,b;}s[MAXN],up[MAXN],dn[MAXN];
bool cmp(ming x,ming y){return x.a<y.a;}
int Cover(ming x,ming y){int l=max(x.a,y.a),r=min(x.b,y.b);if(l>r)return 0;return r-l;}
int query(int l,int r){if(l>r)return 0;int len=r-l+1;return max(st[lg[len]][l],st[lg[len]][r-(1<<lg[len])+1]);}
int main(){
	read(n);
	for(int i=1;i<=n;i++)read(s[i].a);
	for(int i=1;i<=n;i++)read(s[i].b),ans+=1ll*Fabs(s[i].a-s[i].b);
	for(int i=1;i<=n;i++)(s[i].a<s[i].b?up[++tot1]:dn[++tot2])=s[i];
	for(int i=1;i<=tot2;i++)swap(dn[i].a,dn[i].b);
	sort(dn+1,dn+tot2+1,cmp);
	for(int i=1;i<=tot2;i++)dn[i].b=max(dn[i-1].b,dn[i].b);  
	for(int i=2;i<=tot2;i++)lg[i]=lg[i>>1]+1;
	for(int i=1;i<=tot2;i++)st[0][i]=dn[i].b-dn[i].a;
	for(int i=1;i<=20;i++)
		for(int j=1;j<=tot2-(1<<i)+1;j++)
			st[i][j]=max(st[i-1][j],st[i-1][j+(1<<i-1)]);
	for(int i=1;i<=tot1;i++){
		int al,ar,l=1,r=tot2;
		while(l<r){int mid=l+r+1>>1;if(dn[mid].a<=up[i].a)l=mid;else r=mid-1;}al=l;
		l=1,r=tot2;while(l<r){int mid=l+r>>1;if(dn[mid].b>=up[i].b)r=mid;else l=mid+1;}ar=l;
		num=max(num,1ll*max(max(Cover(up[i],dn[al]),Cover(up[i],dn[ar])),query(al+1,ar-1)));
		//printf("%d %d %d:%d %d %d %d\n",i,up[i].a,up[i].b,dn[al].a,dn[al].b,dn[ar].a,dn[ar].b);
	}
	printf("%lld\n",ans-2ll*num);
	return 0;
}

謝謝！！！