lojround6

花团

线段树分治裸题

给出了结束时间跟离线没区别

「LibreOJ Round #6」花火

首先在第一次使用交换是显然的

然后统计逆序对暴力是n^2的（前缀和优化）

因为交换两个点改变的只有x<i  y>i

刚开始想了决策是不是单调的

然后发现不是的

我们可以将它放在图上

然后我们会发现只有左上角没有东西，右下角没有东西的点才有用

然后我们会发现这个东西满足决策单调性（很容易证明分别取两个点看一看矩形的变化就行了）

然后就是比较套路的我们要用分治算法来解决

题解用的是树状数组，也就是每层跑一次（就是bfs）

因为理论复杂度差不多然后主席树没细节就写了主席树，跑的好像挺快的啊？

时间复杂度nlog^2

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (rint i=h;i<=t;i++)

#define dep(i,t,h) for (rint i=t;i>=h;i--)

#define me(x) memset(x,0,sizeof(x))

#define lowbit(x) (x&(-x))

#define ll long long

const int N=4e5;

const int N2=N*;

int a[N],sum,ans,root[N],cnt,n;

#define mid ((h+t)>>1)

struct sgt{

  int data[N2],ls[N2],rs[N2];

  void insert(rint &x,rint lst,rint h,rint t,rint pos)

  {

    x=++cnt; ls[x]=ls[lst]; rs[x]=rs[lst];

    data[x]=data[lst]+;

    if (h==t) return;

    if (pos<=mid) insert(ls[x],ls[lst],h,mid,pos);

    if (pos>mid) insert(rs[x],rs[lst],mid+,t,pos);

  }

  int find(rint x,rint h,rint t,rint h1,rint t1)

  {

    if (!x) return ;

    if (h1<=h&&t<=t1) return(data[x]);

    rint ans=;

    if (h1<=mid) ans+=find(ls[x],h,mid,h1,t1);

    if (mid<t1) ans+=find(rs[x],mid+,t,h1,t1);

    return ans;

  }

  IL int query(int x,int y,int h,int t)

  {

    if (x>y) return();

    return(find(root[y],,n,h,t)-find(root[x-],,n,h,t));

  }

}B;

int s1[N],s2[N];

void fz(int h,int t,int h1,int t1)

{

  int num=-1e9,num2=;

  rep(i,h1,t1)

  if (s2[i]>=s1[mid])

  {

    rint t1=s1[mid],t2=s2[i];

    rint ans2=;

     if (a[t2]<a[t1])

    {

//      ans1=B.query(t1,t2,a[t2]+1)+t2-t1-B.query(t1,t2,a[t1]);

      ans2=*B.query(t1,t2,a[t2]+,a[t1]-)+;

 //     ans2=t2-t1;

 //     ans2=2*(ans1-ans2)+1;

      if (ans2>=num) num=ans2,num2=i;

    }

  }

  sum=max(sum,num);

  if (!num2) num2=h1;

  if (h<=mid-) fz(h,mid-,h1,num2);

  if (mid+<=t) fz(mid+,t,num2,t1);

}

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  ios::sync_with_stdio(false);

  cin>>n;

  rep(i,,n) cin>>a[i];

  ll ans=;

  rep(i,,n)

  {

    ans+=B.query(,i-,a[i]+,n);

    B.insert(root[i],root[i-],,n,a[i]);

  }

  int cnt1=,cnt2=;

  rep(i,,n) if (a[i]>=a[s1[cnt1]]) s1[++cnt1]=i;

  a[]=1e9;

  dep(i,n,) if (a[i]<=a[s2[cnt2]]) s2[++cnt2]=i;

  reverse(s2+,s2+cnt2+);

  fz(,cnt1,,cnt2);

  cout<<min(ans,ans-sum+)<<endl;

  return ;

}