[ 決策單調性 分治 ] LOJ#535 花火

題解

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
inline char nc() {
    static char buf[],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
inline void Read(int& x) {
    char c=nc();
    for(;c<'0'||c>'9';c=nc());
    for(x=;c>='0'&&c<='9';x=(x<<)+(x<<)+c-,c=nc());
}
const int N=;
const int M=;
int k,n,m,x;
int a[N];
int Rt[N],c[M],ls[M],rs[M],num;
int s[N];
int b[N],d[N],l1,l2;
int Ans;
ll sum;
void Update(int& x,int y,int l,int r,int z) {
    x=++num;
    c[x]=c[y]+;
    if(l==r)return;
    int Mid=l+r>>;
    if(z<=Mid) rs[x]=rs[y],Update(ls[x],ls[y],l,Mid,z);
        else ls[x]=ls[y],Update(rs[x],rs[y],Mid+,r,z);
}
int Query(int x,int y,int l,int r,int L,int R) {
    if(l>R||r<L) return ;
    if(l>=L&&r<=R) return c[y]-c[x];
    int Mid=l+r>>;
    return Query(ls[x],ls[y],l,Mid,L,R)+Query(rs[x],rs[y],Mid+,r,L,R);
}
int Get(int l,int r) {
    return Query(Rt[l],Rt[r-],,n,a[r],a[l])+Query(Rt[l],Rt[r-],,n,a[r],a[l])+(a[l]<a[r]?-:);
}
void Solve(int l,int r,int L,int R) {
    if(l>r)return;
    int Mid=l+r>>,pos=L,mx=-;
    for(int i=L;i<=R;i++) 
        if(b[i]<d[Mid]) {
            int t=Get(b[i],d[Mid]);
            if(t>mx)mx=t,pos=i;
        }
    Ans=max(Ans,mx);
    Solve(l,Mid-,L,pos);Solve(Mid+,r,pos,R);
}
void Update(int x) {
    for(;x<=n;x+=x&-x) ++s[x];
}
int Query(int x) {
    int Ans=;
    for(;x;x-=x&-x) Ans+=s[x];
    return Ans;
}
int main() {
    Read(n);
    for(int i=;i<=n;i++) {
        Read(x);a[i]=x;
        Update(Rt[i],Rt[i-],,n,x);
        if(x>a[b[l1]]) b[++l1]=i;
        while(l2&&a[d[l2]]>x) l2--;d[++l2]=i;
    }
    int t=;
    Solve(,l2,,l1);
    for(int i=n;i;i--) sum+=Query(a[i]),Update(a[i]);
    cout<<sum-max(Ans-,)<<endl;
    return ;
}