题意：给定三个序列abc，问最少操作几次使得满足a<b<c
题解：将三个序列合并起来，设cnt[i][1/2/3]表示前i个数有几个是来自序列1/2/3的。
枚举第一个序列要到i，此时对于第一个序列的操作次数就是cnt[i][2]+cnt[i][3]+cnt[n][1]-cnt[i][1]
对于第二个序列，暴力枚举要到j，此时的操作次数就是cnt[j][3]-cnt[i][3]+cnt[n][2]-cnt[j][2]
将两个加起来就是答案，求出最小的那个
显然这样做是O(n^2)的，考虑优化
可以观察到，对于一个确定的i，cnt[i][3]是定值，将式子改写为cnt[j][3]+cnt[n][2]-cnt[j][2]-cnt[i][3]，设f[i]=cnt[i][3]+cnt[n][2]-cnt[i][2]，那么f[i]是一个确定的函数，式子进一步改写为f[j]-cnt[i][3]
相当于对于每个i，求一个最小的f[j]-cnt[i][3]，用一个线段树即可
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<cmath> #define ll long long using namespace std; int k1,k2,k3,a,n,ans=1e9; int cnt[200001][4]; struct node { int v,bh; }q[200001]; bool cmp(const node &T1,const node &T2){return T1.v<T2.v;} class Segtree { public: int v[200001*5],fl[200001*5]; void pushup(int fxy) { v[fxy]=min(v[fxy<<1],v[fxy<<1|1]); } void pushdown(int fxy) { if(fl[fxy]) { v[fxy<<1]+=fl[fxy]; v[fxy<<1|1]+=fl[fxy]; fl[fxy<<1]+=fl[fxy]; fl[fxy<<1|1]+=fl[fxy]; fl[fxy]=0; } } void build(int l,int r,int fxy) { if(l==r) { v[fxy]=cnt[l][3]+cnt[n][2]-cnt[r][2]; return; } int mid=l+r>>1; build(l,mid,fxy<<1); build(mid+1,r,fxy<<1|1); pushup(fxy); } void change(int l,int r,int al,int ar,int tv,int fxy) { if(l==al && r==ar) { v[fxy]+=tv; fl[fxy]+=tv; return; } pushdown(fxy); int mid=l+r>>1; if(ar<=mid)change(l,mid,al,ar,tv,fxy<<1); if(al>mid)change(mid+1,r,al,ar,tv,fxy<<1|1); if(al<=mid && ar>mid) { change(l,mid,al,mid,tv,fxy<<1); change(mid+1,r,mid+1,ar,tv,fxy<<1|1); } pushup(fxy); } int ask(int l,int r,int al,int ar,int fxy) { if(l==al && r==ar)return v[fxy]; pushdown(fxy); int mid=l+r>>1; if(ar<=mid)return ask(l,mid,al,ar,fxy<<1); if(al>mid)return ask(mid+1,r,al,ar,fxy<<1|1); return min(ask(l,mid,al,mid,fxy<<1),ask(mid+1,r,mid+1,ar,fxy<<1|1)); } }segtree; int main() { scanf("%d%d%d",&k1,&k2,&k3); for(int i=1;i<=k1;i++){scanf("%d",&a);q[i]=(node){a,1};} for(int i=1;i<=k2;i++){scanf("%d",&a);q[i+k1]=(node){a,2};} for(int i=1;i<=k3;i++){scanf("%d",&a);q[i+k1+k2]=(node){a,3};} n=k1+k2+k3; sort(q+1,q+1+n,cmp); for(int i=1;i<=n;i++) { cnt[i][1]=cnt[i-1][1]+(q[i].bh==1); cnt[i][2]=cnt[i-1][2]+(q[i].bh==2); cnt[i][3]=cnt[i-1][3]+(q[i].bh==3); } int t; segtree.build(1,n,1); for(int i=0;i<n;i++) { t=segtree.ask(1,n,i+1,n,1); t=min(t,cnt[n][2]-cnt[i][2]); ans=min(ans,t+cnt[i][2]+cnt[i][3]+cnt[n][1]-cnt[i][1]); if(q[i+1].bh==3)segtree.change(1,n,i+1,n,-1,1); } ans=min(ans,cnt[n][2]+cnt[n][3]); printf("%d ",ans); return 0; }