SS241007B. 逆序对（inverse）
SS241007B. 逆序对（inverse）
题意
给你一个长度为 \(n\) 的排列，你可以选择一对 \((i,j)\)，交换 \(p_i,p_j\)，或者不操作，使减少的逆序对个数最多，求最多减少几个逆序对。
思路
首先考虑交换 \(i,j\) 会对哪些部分的逆序对数量产生影响。不难发现，如果我们画一个二维平面，上面有 \(n\) 个点 \((i,p_i)\)，那么交换 \((p_i,p_j)\) 减少的逆序对个数就是：设以 \((i,p_i)\) 为左上角，以 \((j,p_j)\) 为右下角的矩形内部覆盖了 \(s\) 个点，减少的逆序对个数就是 \(2s+1\)。
因此问题转化为对所有 \((i,j)\)，求矩形内部覆盖的点数最多。
枚举所有左上角和右上角，然后二维前缀和计算矩形内部点数，时间复杂度是 \(O(n^2)\) 的。
通过敏锐的观察，可以发现不是所有点都有可能成为矩形的左上角或者右下角的。设点 \((k,p_k)\) 在点 \((i,p_i)\) 的右下方，那么左上角一定不会选择 \(k\)，因为选择 \(i\) 必然更优，因此只有等于前缀最大值的 \(p_i\) 可能成为矩形左上角。同理可得，只有后缀最小值可能成为矩形右下角。长成图像就是所有可能的左上角，所有可能的右上角，都是单调递增的。
那么对于部分分的随机数据，发现随机条件下可能的左上角及右上角基本上都不超过 \(100\)，因此直接枚举左上角、右上角，然后树状数组求一下矩形内部的点，就可以获得 \(70\) 分的高分了。
其实容易发现有一个很有前途的决策单调性，对于向右移动的矩形左上角，决策点（右下角）一定单调向右移动。因为左上端点向右上移动，所有决策（选择每个右下端点的矩形内点数）的变化量一定是越右边的越大。因此一个左边的决策点如果没有一个右边的决策点优，之后它会更加不优，可以直接扔掉它了。因此对于单调右上的左上角，决策点也是单调右上的。
但是题解的做法并没有利用这个决策单调性，场上我也没有想到很好地利用它的方法。
我们考虑转换思路，枚举每个点，处理这个点对哪些矩形有贡献。
发现这个点一定是对左上端点在这个点的左上方，右下端点在这个点的右下方，的矩形有贡献，也就是连续的一段左端点匹配连续的一段右端点。
一个十分巧妙的转化是，创建一个二维平面 \((左上端点编号，右下端点编号)\)，叫做平面 2，刚刚那个二维平面叫做平面 1。然后每个平面 1 的点就相当于把平面 2 的一个矩形加 \(1\)，最后问平面 2 最大的点的权值是多少。
由于我们不能把平面 2 建出来，所以我们离线所有对平面 2 的操作，然后扫描线，用线段树维护最大值即可。时间复杂度是 \(O(n \log n)\) 的。
code
#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N=1e6+7;
namespace io {
const int SIZE = (1 << 25) + 1;
char ibuf[SIZE], *iS, *iT;
char obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[64];
int f, qr;
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
template <class I> inline void read (I &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
x = f == -1 ? -x : x;
}
template <class I> inline void print (I x) {
if (! x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[ ++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr -- ]);
}
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: print;
int n,p[N];
int lvec[N],rvec[N],ls[N],rs[N];
int cntl,cntr;
typedef pair<int,int> pii;
typedef vector<pii > vpii;
#define fi first
#define se second
vpii opt[N];
int mx[N<<2],tag[N<<2];
int ans=0;
inline void maketag(int u,int val) {
tag[u]+=val;
mx[u]+=val;
}
inline void pushdown(int u) {if(tag[u]) maketag(u<<1,tag[u]),maketag(u<<1|1,tag[u]),tag[u]=0;}
inline void pushup(int u) {mx[u]=max(mx[u<<1],mx[u<<1|1]);}
void update(int u,int l,int r,int x,int val) {
if(l>=x) {
maketag(u,val);
return;
}
pushdown(u);
int mid=(l+r)>>1;
if(x<=mid) update(u<<1,l,mid,x,val);
update(u<<1|1,mid+1,r,x,val);
pushup(u);
}
bool check() {
rep(i,2,n) if(p[i]<p[i-1]) return 0;
return 1;
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#else
freopen("inverse.in","r",stdin);
freopen("inverse.out","w",stdout);
#endif
read(n);
rep(i,1,n) read(p[i]);
if(check()) {
print(0);
return 0;
}
int tmp=0;
rep(i,1,n) {
tmp=max(tmp,p[i]);
if(p[i]==tmp) lvec[++cntl]=i,ls[cntl]=p[i];
}
tmp=N;
per(i,n,1) {
tmp=min(tmp,p[i]);
if(p[i]==tmp) rvec[++cntr]=i,rs[cntr]=p[i];
}
reverse(rvec+1,rvec+cntr+1);
reverse(rs+1,rs+cntr+1);
int idl=1,idr=rvec[1]==1?1:0;
rep(i,2,n-1) {
if(i==lvec[idl+1]) idl++;
if(i==rvec[idr+1]) idr++;
int l=upper_bound(ls+1,ls+idl+1,p[i])-ls,r=lower_bound(rs+idr,rs+cntr+1,p[i])-rs-1;
if(idr+1>r) continue;
opt[idr+1].push_back({l,1}),opt[idr+1].push_back({idl+1,-1});
opt[r+1].push_back({l,-1}),opt[r+1].push_back({idl+1,1});
}
rep(i,1,cntr) {
for(pii op:opt[i]) {
if(op.fi>=1&&op.fi<=cntl)
update(1,1,cntl,op.fi,op.se);
}
ans=max(ans,mx[1]);
}
print(ans*2+1);
}