LibreOJ#535. 「LibreOJ Round #6」花火
\(n\) 个烟火排成一排，从左到右高度分别为 \(h_1,h_2,\cdots,h_n\)，这些高度两两不同。
每次 Yoko 可以选择两个相邻的烟火交换，这样的交换可以进行任意多次。
每次 Yoko 还可以选择两个不相邻的烟火交换，但这样的交换至多进行一次。
你的任务是帮助 Yoko 用最少次数的交换，使这些烟火从左到右的高度递增。
对于所有数据，满足 \(1\le n\le 300,000\)，\(1\le h_i\le n\)，\(h_i\) 互不相同。
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
#define N 300010
int n,a[N];
int topA,topB,stA[N],stB[N];
int Tree[N<<2],tag[N<<2],sum[N];
int cnt,flag[N];
struct Node
{
int y,l,r,val;
bool operator < (const Node &rhs) const
{
if (y==rhs.y) return val<rhs.val;
return y<rhs.y;
}
}buc[N<<1];
int read ()
{
int k=1,s=0;char ch=getchar ();
while (!isdigit (ch)) {if (ch=='-') k=-1;ch=getchar ();}
while (isdigit (ch)) {s=s*10+ch-'0';ch=getchar ();}
return k*s;
}
int FindA (int x)
{
int L=1,R=topA,res=0;
while (L<=R)
{
int mid=(L+R)>>1;
if (a[stA[mid]]>a[x])
{
res=mid;
R=mid-1;
}
else L=mid+1;
}
return stA[res];
}
int FindB (int x)
{
int L=1,R=topB,res=0;
while (L<=R)
{
int mid=(L+R)>>1;
if (a[stB[mid]]<a[x])
{
res=mid;
R=mid-1;
}
else L=mid+1;
}
return stB[res];
}
void Modify (int i,int l,int r,int x,int y,int val)
{
if (x<=l && r<=y)
{
Tree[i]+=val,tag[i]+=val;
return;
}
int mid=(l+r)>>1;
if (x<=mid) Modify (i<<1,l,mid,x,y,val);
if (mid<y) Modify (i<<1|1,mid+1,r,x,y,val);
Tree[i]=max (Tree[i<<1],Tree[i<<1|1])+tag[i];
}
int lowbit (int x)
{
return x&(-x);
}
void Update (int x)
{
while (x<=n)
{
sum[x]++;
x+=lowbit (x);
}
}
int Getsum (int x)
{
int res=0;
while (x>0)
{
res+=sum[x];
x-=lowbit (x);
}
return res;
}
void Init ()
{
n=read ();
for (int i=1;i<=n;i++)
a[i]=read ();
}
void Work ()
{
for (int i=1;i<=n;i++)
if (i==1 || a[i]>a[stA[topA]])
{
stA[++topA]=i;
flag[i]=1;
}
for (int i=n;i>=1;i--)
if (i==n || a[i]<a[stB[topB]])
{
stB[++topB]=i;
flag[i]=1;
}
for (int i=1;i<=n;i++)
{
if (flag[i]) continue;
int L=FindA (i),R=FindB (i);
if (L<i && i<R)
{
buc[++cnt]=(Node) {i+1,L,i-1,1};
buc[++cnt]=(Node) {R+1,L,i-1,-1};
}
}
sort (buc+1,buc+1+cnt);
int ans=0;
for (int i=1;i<=cnt;i++)
{
Modify (1,1,n,buc[i].l,buc[i].r,buc[i].val);
if (buc[i].y!=buc[i+1].y) ans=max (ans,Tree[1]);
}
ans=-2*ans;
for (int i=n;i>=1;i--)
{
ans+=Getsum (a[i]-1);
Update (a[i]);
}
printf ("%lld\n",ans);
}
signed main ()
{
Init ();
Work ();
}