典型面倒データ構造。クソ。
各ステップに面倒要素が搭載されており、やる気を的確に削いでくる。というかこういう問題で何やっても通るようなサンプル置くのは何なの……
Starry Sky木の更新条件をすっかり忘れていた。
#include<stdio.h> #include<algorithm> using namespace std; int b[110000]; int z[110000]; long long bit[110000]; long long sum(int a,int b){ if(a)return sum(0,b)-sum(0,a-1); long long ret=0; for(;b>=0;b=(b&(b+1))-1)ret+=bit[b]; return ret; } void add(int a,int b){ for(;a<110000;a|=a+1)bit[a]+=b; } int segtree[262144]; int lx[110000]; int ly[110000]; int rx[110000]; int ry[110000]; void add2(int a,int b,int c,int d,int e,int f){ if(d<a||b<c)return; if(c<=a&&b<=d){ segtree[e]+=f; }else{ add2(a,(a+b)/2,c,d,e*2,f); add2((a+b)/2+1,b,c,d,e*2+1,f); } if(e>1&&((segtree[e]!=0&&segtree[e^1]!=0)||segtree[e]>0||segtree[e^1]>0)){ int t=max(segtree[e],segtree[e^1]); segtree[e/2]+=t; segtree[e^1]-=t; segtree[e]-=t; } } int query(int a,int b,int c,int d,int e,int f){ if(d<a||b<c)return -99999999; if(c<=a&&b<=d)return segtree[e]+f; return max(query(a,(a+b)/2,c,d,e*2,f+segtree[e]),query((a+b)/2+1,b,c,d,e*2+1,f+segtree[e])); } int L[110000]; int R[110000]; pair<int,int>yp[110000]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",b+i); bool chk=true; bool same=false; for(int i=0;i<a-1;i++)if(b[i]<b[i-1])chk=false; for(int i=0;i<a-1;i++)if(b[i]==b[i-1])same=true; if(chk){ if(same)printf("0\n"); else printf("1\n");return 0; } for(int i=0;i<a;i++){ z[i]=b[i]; yp[i]=make_pair(b[i],i); } std::sort(yp,yp+a); std::sort(z,z+a); long long ans=0; for(int i=0;i<a;i++){ int at=lower_bound(z,z+a,b[i])-z; if(at<a-1)ans+=sum(at+1,a-1); add(at,1); } int tmp=0; int ls=0; int rs=0; for(int i=0;i<a;i++){ if(tmp<b[i]){ L[i]=1; tmp=b[i]; lx[ls]=i; ly[ls++]=tmp; } } tmp=1000000007; for(int i=a-1;i>=0;i--){ if(tmp>b[i]&&L[i]==0){ R[i]=1; tmp=b[i]; } } for(int i=0;i<a;i++){ if(R[i]){ rx[rs]=i; ry[rs++]=b[i]; } } int ret=0; int rm=0; int ypat=0; for(int i=0;i<a;i++){ if(R[i]){ int nx=b[i]; int tmp=0; while(ypat<a&&yp[ypat].first<nx){ int ind=yp[ypat].second; if(!L[ind]&&!R[ind]){ int to=lower_bound(ly,ly+ls,b[ind])-ly; int rim=lower_bound(lx,lx+ls,ind)-lx-1; if(to<=rim)add2(0,131071,to,rim,1,-1); if(b[ind]==ly[to])to++; if(to<=rim)add2(0,131071,to,rim,1,-1); } ypat++; } int cp=ypat; while(cp<a&&yp[cp].first==nx){ int ind=yp[cp].second; if(!L[ind]&&!R[ind]){ int to=lower_bound(ly,ly+ls,b[ind])-ly; int rim=lower_bound(lx,lx+ls,ind)-lx-1; if(to<=rim)add2(0,131071,to,rim,1,-1); } cp++; } int at=lower_bound(lx,lx+ls,i)-lx-1; int at2=upper_bound(ly,ly+ls,b[i])-ly; if(at2<=at){ tmp=query(0,131071,at2,at,1,0); ret=max(ret,tmp); } while(ypat<a&&yp[ypat].first==nx){ int ind=yp[ypat].second; if(!L[ind]&&!R[ind]){ int to=lower_bound(ly,ly+ls,b[ind])-ly; int rim=lower_bound(lx,lx+ls,ind)-lx-1; if(b[ind]==ly[to])to++; if(to<=rim)add2(0,131071,to,rim,1,-1); } ypat++; } }else if(!L[i]){ int to=lower_bound(ly,ly+ls,b[i])-ly; int rim=lower_bound(lx,lx+ls,i)-lx-1; if(to<=rim)add2(0,131071,to,rim,1,1); if(b[i]==ly[to])to++; if(to<=rim)add2(0,131071,to,rim,1,1); } } // printf("%lld %d\n",ans,ret); printf("%lld\n",ans-ret-1); }
