Submission #3017095

---

Source Code Expand

//4:11
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
using namespace std;
typedef long long ll;
#define N (1<<17)
int n,m[N];
void Zaats(){
    vector<int> v;
    lol(i,n)v.push_back(m[i]);
    sort(v.begin(),v.end());
    lol(i,n){
	m[i]=lower_bound(v.begin(),v.end(),m[i])-v.begin();
    }
}
vector<int> A,B,Y;
void SetABY(){
    int maxi=-1;
    lol(i,n){
	if(maxi<m[i]){
	    maxi=m[i];
	    A.push_back(i);
	}
    }
    int mini=mod;
    for(int i=n-1;i>=0;i--){
	if(mini>m[i]){
	    mini=m[i];
	    B.push_back(i);
	}
    }
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    vector<pair<int,int> >v;
    lol(i,n)v.push_back(make_pair(m[i],i));
    sort(v.begin(),v.end());
    lol(i,n)Y.push_back(v[i].second);
}
class RAQxRMQ{
private:
    ll dat[2*N],laz[2*N];
    void eval(int k){
	dat[k]+=laz[k];
	if(k<N-1){
	    laz[k*2+1]+=laz[k];
	    laz[k*2+2]+=laz[k];
	}
	laz[k]=0;
    }
    void ufs(int l,int r,int a,int b,int k,ll x){
	eval(k);
	if(l<=a&&b<=r){laz[k]+=x;eval(k);return;}
	if(b<=l||r<=a)return;
	ufs(l,r,a,(a+b)/2,k*2+1,x);
	ufs(l,r,(a+b)/2,b,k*2+2,x);
	dat[k]=max(dat[k*2+1],dat[k*2+2]);
    }
    ll dfs(int l,int r,int a,int b,int k){
	eval(k);
	if(l<=a&&b<=r)return dat[k];
	if(b<=l||r<=a)return 0;
	ll vl=dfs(l,r,a,(a+b)/2,k*2+1);
	ll vr=dfs(l,r,(a+b)/2,b,k*2+2);
	return max(vl,vr);
    }
public:
    void Init(){
	lol(i,2*N)dat[i]=laz[i]=0;
    }
    void Add(int l,int r,ll x){
	ufs(l,r+1,0,N,0,x);
    }
    ll Max(int l,int r){
	return dfs(l,r+1,0,N,0);
    }
};
class RSQ{
private:
    ll dat[2*N];
    ll dfs(int l,int r,int a,int b,int k){
	if(l<=a&&b<=r)return dat[k];
	if(b<=l||r<=a)return 0;
	ll vl=dfs(l,r,a,(a+b)/2,k*2+1);
	ll vr=dfs(l,r,(a+b)/2,b,k*2+2);
	return vl+vr;
    }
public:
    void Init(){
	lol(i,2*N)dat[i]=0;
    }
    void Upd(int i,int x){
	i+=N-1,dat[i]=x;
	while(i>0){
	    i=(i-1)/2;
	    dat[i]=dat[i*2+1]+dat[i*2+2];
	}
    }
    void Add(int i,int x){
	Upd(i,Sum(i,i)+x);
    }
    int Sum(int l,int r){
	return dfs(l,r+1,0,N,0);
    }
};
ll Tentou(){
    RSQ seg;seg.Init();
    ll res=0;
    lol(i,n){
	res+=seg.Sum(m[i]+1,n);
	seg.Add(m[i],1);
    }
    return res;
}
bool Topo(ll x1,ll y1,ll x2,ll y2){
    return (x1<x2&&y1>y2);
}
ll L,R;
void BNS(ll x,ll y){
    ll l,r,mid;
    l=-1,r=B.size();
    while(l<r-1){
	mid=(l+r)/2;
	if(B[mid]>x)r=mid;
	else l=mid;
    }
    L=r;
    l=-1,r=B.size();
    while(l<r-1){
	mid=(l+r)/2;
	if(m[B[mid]]<y)l=mid;
	else r=mid;
    }
    R=l;
}
int main(){
    cin>>n;
    lol(i,n)cin>>m[i];
    Zaats();
    SetABY();
    RAQxRMQ seg;seg.Init();
    ll ans=0,px=0,py1=0,py2=0,bx=-1,by=-1;
    lol(i,A.size()){
	ll ax=A[i],ay=m[A[i]];
	for(;px<n;px++){
	    ll x=px,y=m[px];
	    if(!(x<=ax))break;
	    if(Topo(bx,by,x,y)){
		BNS(x,y+1);
		seg.Add(L,R,-1);
	    }
	    if(Topo(bx,by+1,x,y)){
		BNS(x,y);
		seg.Add(L,R,-1);
	    }
	}
	for(;py1<n;py1++){
	    ll x=Y[py1],y=m[Y[py1]];
	    if(!(y<ay))break;
	    if(Topo(ax,ay,x,y)){
		BNS(x,y+1);
		seg.Add(L,R,1);
	    }
	}
	for(;py2<n;py2++){
	    ll x=Y[py2],y=m[Y[py2]];
	    if(!(y<=ay))break;
	    if(Topo(ax,ay+1,x,y)){
		BNS(x,y);
		seg.Add(L,R,1);
	    }
	}
	ans=max(ans,seg.Max(0,B.size()-1));
	bx=ax,by=ay;
    }
    ll t=Tentou();
    if(t==0){
	bool same=false;
	lol(i,n-1)if(m[Y[i]]==m[Y[i+1]])same=true;
	cout<<1-same<<endl;
    }
    else cout<<t-1-ans<<endl;
    return 0;
}

Submission Info

Judge Result