【Loj#535】花火（线段树，扫描线）

题面

题解

首先如果不考虑交换任意两个数这个操作，答案就是逆序对的个数。

那么暴力就是枚举交换哪个两个数，然后用数据结构之类的东西动态维护逆序对。

但是这样还不够。

仔细观察哪些点交换了才有意义。

假设交换的位置是\(l,r\)

首先必须有\(h[l]\gt h[r]\)，这个很显然，如果把一个更大的数换到了前面显然不优。

其次，\(l\)必须是前缀的最大值。

如果\(l\)不是前缀最大值，那么存在一个位置\(i\)满足\(h[i]\gt h[l]\gt h[r]\)

那么直接交换\(i,r\)显然更优。

同理，\(r\)必须是后缀的最小值。

那么，首先把所有的前缀最大值和后缀最小值预处理出来。

每次交换的时候，我们发现减少的逆序对数量就是

\(l<i<r,h[l]>h[i]>h[r]\)的所有\(i\)的个数。

发现这就是一个二维数点，用扫描线解决即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 333333

#define lson (now<<1)

#define rson (now<<1|1)

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

ll ans,now;

int n,a[MAX],cnt;

int st1[MAX],st2[MAX],top1,top2;

bool ins[MAX];

struct Node{int y,l,r,opt;}p[MAX<<1];

bool operator<(Node a,Node b)

{

	if(a.y!=b.y)return a.y<b.y;

	return a.opt<b.opt;

}

int binary1(int x)

{

	int l=1,r=top1,ret=0;

	while(l<=r)

	{

		int mid=(l+r)>>1;

		if(a[st1[mid]]>a[x])ret=mid,r=mid-1;

		else l=mid+1;

	}

	return st1[ret];

}

int binary2(int x)

{

	int l=1,r=top2,ret=0;

	while(l<=r)

	{

		int mid=(l+r)>>1;

		if(a[st2[mid]]<a[x])ret=mid,r=mid-1;

		else l=mid+1;

	}

	return st2[ret];

}

struct SegNode{int mx,tag;}t[MAX<<2];

void Modify(int now,int l,int r,int L,int R,int w)

{

	if(L<=l&&r<=R){t[now].mx+=w;t[now].tag+=w;return;}

	int mid=(l+r)>>1;

	if(L<=mid)Modify(lson,l,mid,L,R,w);

	if(R>mid)Modify(rson,mid+1,r,L,R,w);

	t[now].mx=max(t[lson].mx,t[rson].mx)+t[now].tag;

}

int c[MAX];

int lb(int x){return x&(-x);}

void add(int x){while(x<=n)++c[x],x+=lb(x);}

int getsum(int x){int ret=0;while(x)ret+=c[x],x-=lb(x);return ret;}

int main()

{

	//freopen("hanabi.in","r",stdin);

	//freopen("hanabi.out","w",stdout);

	n=read();

	for(int i=1;i<=n;++i)a[i]=read();

	for(int i=1;i<=n;++i)if(i==1||a[i]>a[st1[top1]])st1[++top1]=i,ins[i]=true;

	for(int i=n;i>=1;--i)if(i==n||a[i]<a[st2[top2]])st2[++top2]=i,ins[i]=true;

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

		if(!ins[i])

		{

			int l=binary1(i),r=binary2(i);

			if(l<i&&i<r)

			{

				p[++cnt]=(Node){i+1,l,i-1,+1};

				p[++cnt]=(Node){r+1,l,i-1,-1};

			}

		}

	sort(&p[1],&p[cnt+1]);

	for(int i=1;i<=cnt;++i)

	{

		Modify(1,1,n,p[i].l,p[i].r,p[i].opt);

		if(p[i].y!=p[i+1].y)ans=max(ans,1ll*t[1].mx);

	}

	ans<<=1;ans*=-1;

	for(int i=1;i<=n;++i)add(a[i]),ans+=i-getsum(a[i]);

	printf("%lld\n",ans);

	return 0;

}

巴特西

【Loj#535】花火（线段树，扫描线）

【Loj#535】花火（线段树，扫描线）

题面

题解

最新文章

热门文章