Loj 535 花火

Posted on | Views:

扫描线 + 线段树.

特判序列已经有序的情况,此时不需要进行任何交换.

首先,我们可以首先进行特殊的交换,再进行一般的交换,这样显然不会使答案变劣.

特殊交换之后,还需要的次数就是当前逆序对的数目.所以特殊交换要减少尽可能多的逆序对.

考虑交换两个数 $h_x,h_y,x<y$ ,显然当 $h_x>h_y$ 时,逆序对会减少,否则会增加,于是只考虑 $h_x>h_y$ 的情况.

容易发现交换后减少的逆序对数目就是 $1+2|S|,S=\lbrace k|x<k<y,h_y<h_k<h_x \rbrace$ .

考虑左端点 $x$ 的选择,若 $h_{x_1}>h_{x_2},x_1<x_2$ , $x_2$ 就没用了.于是可以维护出有用的 $x$ .

考虑右端点 $pos_y$ 的选择,若 $h_{y_1}<h_{y_2},y_1>y_2$ , $y_2$ 就没用了.于是可以维护出有用的 $y$ .

考虑一个位置 $k$ 会存在哪些点对 $(x,y)$ 满足 $x<k<y,h_y<h_k<h_x$ .在第一个单调栈中二分找出最小的 $l$ ,使得 $h_l>h_k$ ,在第二个单调栈中二分找出最小的 $r$ ,使得 $h_r<h_x$ .

那么点对 $(x,y)$ 满足 $x<k<y,h_y<h_k<h_x$ ,即 $k$ 对 $(x,y)$ 有贡献的条件是 $x\in [l,k-1],y\in[k+1,r]$ .

这相当于是一个矩形覆盖,问题转化为给了若干个矩形,求一个点最多被覆盖了几次.

扫描线 + 线段树解决,时间复杂度 $O(n\log n)​$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
	int out=0,sgn=1;
	char jp=getchar();
	while(jp!='-' && (jp<'0' || jp>'9'))
		jp=getchar();
	if(jp=='-')
		sgn=-1,jp=getchar();
	while(jp>='0' && jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*sgn;
}
const int MAXN=3e5+10;
int n,h[MAXN],H[MAXN];
struct FenwickTree
{
	int bit[MAXN];
	FenwickTree(){memset(bit,0,sizeof bit);}
#define lowbit(x) x&(-x)
	void add(int x,int c)
	{
		for(;x<=n;x+=lowbit(x))
			bit[x]+=c;
	}
	int sum(int x)
	{
		int s=0;
		for(;x;x-=lowbit(x))
			s+=bit[x];
		return s;
	}
}FT;
ll ans=0;
int vis[MAXN],sx[MAXN],tx=0,sy[MAXN],ty=0;
int bsx(int x)
{
	int L=1,R=tx,res=0;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(h[sx[mid]]>x)
			res=mid,R=mid-1;
		else
			L=mid+1;
	}
	return sx[res];
}
int bsy(int y)
{
	int L=1,R=ty,res=0;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(h[sy[mid]]<y)
			res=mid,R=mid-1;
		else
			L=mid+1;
	}
	return sy[res];
}
struct node
{
	int x,ly,ry,tp;//1 + -1 -
	bool operator < (const node &rhs) const
	{
		return x==rhs.x?tp>rhs.tp:x<rhs.x;
	}
}p[MAXN<<2];
struct SegTree
{
	struct node
	{
		int mx,tag;
	}Tree[MAXN<<4];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]	
	void pushup(int o)
	{
		root.mx=max(lson.mx,rson.mx);
	}
	void BuildTree(int o,int l,int r)
	{
		root.mx=0;
		root.tag=0;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
	}
	void modify(int o,int c)
	{
		root.mx+=c;
		root.tag+=c;
	}
	void pushdown(int o)
	{
		if(root.tag)
		{
			modify(o<<1,root.tag);
			modify(o<<1|1,root.tag);
			root.tag=0;
		}
	}
	void upd(int o,int l,int r,int L,int R,int c)
	{
		if(L<=l && r<=R)
		{
			modify(o,c);
			return;
		}
		pushdown(o);
		int mid=(l+r)>>1;
		if(L<=mid)
			upd(o<<1,l,mid,L,R,c);
		if(R>mid)
			upd(o<<1|1,mid+1,r,L,R,c);
		pushup(o);
	}
	int query()
	{
		return Tree[1].mx;
	}
}ST;
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		h[i]=H[i]=read();
	sort(H+1,H+1+n);
	for(int i=1;i<=n;++i)
	{
		h[i]=lower_bound(H+1,H+1+n,h[i])-H;
		ans+=FT.sum(n)-FT.sum(h[i]);
		FT.add(h[i],1);
	}
	if(!ans)
		return puts("0")&0;
	++ans;
	for(int i=1;i<=n;++i)
	{
		if(tx>0 && h[i]<h[sx[tx]])
			continue;
		sx[++tx]=i;
		vis[i]=1;
	}
	for(int i=n;i>=1;--i)
	{
		if(ty>0 && h[i]>h[sy[ty]])
			continue;
		sy[++ty]=i;
		vis[i]=1;
	}
	int cnt=0;
	for(int i=1;i<=n;++i)
	{
		if(vis[i])
			continue;
		int l=bsx(h[i]),r=bsy(h[i]);
		if(l<i && i<r)
		{
			p[++cnt]=(node){l,i+1,r,1};
			p[++cnt]=(node){i-1,i+1,r,-1};
		}
	}
	sort(p+1,p+1+cnt);
	int s=0;
	for(int i=1;i<=cnt;++i)
	{
		ST.upd(1,1,n,p[i].ly,p[i].ry,p[i].tp);
		if(p[i].tp>0)
			s=max(s,ST.query());
	}
	ans-=(1+2LL*s);
	cout<<ans<<endl;
	return 0;
}