[luogu5426]Balancing Inversions

由于交换是相邻交换，所以分为两类：
1.左右区间内部交换，那么一定会让逆序对数量$\pm 1$，也就是说如果没有左右区间之间交换，那么答案就是$|ansL-ansR|$（ans表示逆序对数量）
2.左右区间之间交换，考虑枚举左边最终有多少个1，不妨假设比原来多（原来少一样，但不能都异或1之后重复一遍，会错的），首先一定尽量交换左边的最右边的若干个0和右边最左边的若干个1，然后快速的去维护两边的逆序对数量
维护方式很简单，由于假如左边如果改变了一个点，说明它的右边一定都是同样的数字，所以不用线段树，只需要维护左边的前缀和即可（右边同理）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 int n,a[N],sum[N];

 5 long long s,ans1,ans2,ans;

 6 int pre(int k){

 7     k--;

 8     while ((k)&&(!a[k]))k--;

 9     return k;

10 }

11 int nex(int k){

12     k++;

13     while ((k<=2*n)&&(a[k]))k++;

14     return k;

15 }

16 void calc1(){

17     s=ans1=ans2=0;

18     for(int i=1;i<=n;i++)

19         if (!a[i])ans1+=sum[i-1];

20     for(int i=2*n;i>n;i--)

21         if (a[i])ans2+=sum[i+1];

22     ans=min(ans,abs(ans1-ans2));

23     for(int x=pre(n+1),y=nex(n);(x)&&(y<=2*n);x=pre(x),y=nex(y)){

24         s+=y-x;

25         ans1+=sum[x];

26         ans2+=sum[y];

27         ans=min(ans,s+abs(ans1-ans2));

28     }

29 }

30 void calc2(){

31     s=ans1=ans2=0;

32     for(int i=1;i<=n;i++)

33         if (a[i])ans1+=sum[i-1];

34     for(int i=2*n;i>n;i--)

35         if (!a[i])ans2+=sum[i+1];

36     for(int x=pre(n+1),y=nex(n);(x)&&(y<=2*n);x=pre(x),y=nex(y)){

37         s+=y-x;

38         ans1-=sum[x];

39         ans2-=sum[y];

40         ans=min(ans,s+abs(ans1-ans2));

41     }

42 }

43 int main(){

44     scanf("%d",&n);

45     for(int i=1;i<=2*n;i++)scanf("%d",&a[i]);

46     for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];

47     for(int i=2*n;i>n;i--)sum[i]=sum[i+1]+(a[i]^1);

48     ans=1LL*n*n;

49     calc1();

50     for(int i=1;i<=2*n;i++)a[i]^=1;

51     calc2();

52     printf("%lld",ans);

53 }

巴特西

[luogu5426]Balancing Inversions

最新文章

热门文章