#C241005A. 逆序对

标签（Label）

扫描线
线段树
观察+分析

网址（Website）

题目详情 - 逆序对 - Super

题解 - 逆序对 - Super

题解（Solution）

先分析题目性质：

发现如果要交换 $i$ 和 $j$ 两个位置，令 $k\in (i,j)$ ，当 $a[k]>a[i] $ 且 $a[k]>a[j]$ 时交换 $i,j$ 对原序列没有贡献；同理，当 $a[k]<a[i] $ 且 $a[k]<a[j]$ 时也没有贡献。因此，我们发现交换与 $a[k]\not \in [a[i],a[j]]$ 的数无关。
由上述性质，发现只有逆序对交换才是优的，对于 $i<j$ 且 $a[i]<a[j]$ ，交换二者是不优的。
发现对于 $a[x]>a[y]$ 且 $x<y$ ，若二者都要交换 $a[k]$ ，交换 $a[x]$ 对答案的贡献更大。
同性质 3，若 $a[x]<a[y]$ 且 $x>y$ ，对于相同的 $a[k]$ ，交换 $a[x]$ 对答案贡献更大。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(register int i=l;i<=r;i++)
#define Rof(i,l,r) for(register int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define x first
#define y second
namespace iobuff{ 
	const int LEN=1000000;
	char in[LEN+5], out[LEN+5];
	char *pin=in, *pout=out, *ed=in, *eout=out+LEN;
	inline char gc(void){
		return pin==ed&&(ed=(pin=in)+fread(in, 1, LEN, stdin), ed==in)?EOF:*pin++;}
	inline void pc(char c){
		pout==eout&&(fwrite(out, 1, LEN, stdout), pout=out);
		(*pout++)=c;}
	inline void flush()
	{ fwrite(out, 1, pout-out, stdout), pout=out; }
	template<typename T> inline void scan(T &x){
		static int f;
		static char c;
		c=gc(), f=1, x=0;
		while(c<'0'||c>'9') f=(c=='-'?-1:1), c=gc();
		while(c>='0'&&c<='9') x=10*x+c-'0', c=gc();
		x*=f;
	}
	template<typename T> inline void write(T x, char div){
		static char s[20];
		static int top;
		top=0;
		x<0?pc('-'), x=-x:0;
		while(x) s[top++]=x%10, x/=10;
		!top?pc('0'), 0:0;
		while(top--) pc(s[top]+'0');
		pc(div);
	}
}using namespace iobuff;
const int inf = 0x3f3f3f3f;
const int N = 1012345;
bool ST;

int n,ans,p[N];

#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment_Tree{
	struct Tr{int add,max;}tr[N<<2|3];
	void pushup(Tr &T,Tr L,Tr R){T.max = max(L.max, R.max);}
	void pushtag(int p,int v){tr[p].max += v, tr[p].add += v;}
	void pushdown(int p){
		if(tr[p].add){
			int v = tr[p].add;tr[p].add = 0;
			pushtag(ls,v), pushtag(rs,v);
		}
	}
	void update(int p,int l,int r,int L,int R,int k){
		if(L<=l && r<=R) return pushtag(p,k);
		pushdown(p);
		if(L<=mid) update(ls,l,mid,L,R,k);
		if(R>mid) update(rs,mid+1,r,L,R,k);
		pushup(tr[p],tr[ls],tr[rs]);
	}
	Tr ask(int p,int l,int r,int L,int R){
		if(L<=l && r<=R) return tr[p];
		pushdown(p);
		if(R<=mid) return ask(ls,l,mid,L,R);
		if(L>mid) return ask(rs,mid+1,r,L,R);
		Tr T;return pushup(T,ask(ls,l,mid,L,R),ask(rs,mid+1,r,L,R)),T;
	}
}T;


vector<array<int,3>> g[N];
vector<int> L,R;
bitset<N> a,b;
void solve(){
	scan(n);For(i,1,n) scan(p[i]);
	if(is_sorted(p+1,p+n+1)) return printf("0"),void();
	{
		int res = 0;
		For(i,1,n) if(p[i]>res){
			res = p[i];
			a[i] = true;
			L.emplace_back(i);
		}
		res = n+1;
		Rof(i,n,1) if(p[i]<res){
			res = p[i];
			b[i] = true;
			R.emplace_back(i);
		}reverse(R.begin(),R.end());
	}
	
	For(i,1,n) if(!a[i] && !b[i]){
		auto cmp = [&](const int &x,const int &y){return p[x]<p[y];};
		int a = lower_bound(L.begin(),L.end(),i,cmp) - L.begin();
		int b = lower_bound(L.begin(),L.end(),i) - L.begin() - 1;
		int c = lower_bound(R.begin(),R.end(),i) - R.begin();
		int d = lower_bound(R.begin(),R.end(),i,cmp) - R.begin() - 1;
		if(a>b || c>d) continue;
		g[a].push_back({c,d,1});
		g[b+1].push_back({c,d,-1});
	}
	For(i,0,(int)L.size()-1){
		for(auto p:g[i]) T.update(1,0,R.size(),p[0],p[1],p[2]);
		ans = max(T.tr[1].max, ans);
	}cout<<ans*2+1<<'\n';
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	int T = 1, Tim = clock();
	while(T--) solve();
	flush();//remember to flush at the end
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}