首先可以证明把两个数列从小到大排列再对应匹配是最优的。 画画图可以发现，在有限制的情况下一个点，离它匹配的点的距离不超过2 这样就可以DP了 fi 表示前i个点匹配的答案。 那么
fi=max⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪fi−1+ai∗bifi−2+ai∗bi−1+ai−1∗bifi−3+ai∗bi−1+ai−1∗bi−2+ai−2∗bifi−3+ai∗bi−2+ai−1∗bi+ai−2∗bi−1 这个转移画画图就可以得到。 这样就可以 O(n2) 了但是有更高效的做法 令 fi,j 表示前i个,前i-j个已经被匹配了的答案
那么
fi,0=max⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪fi−1,0+ai∗bifi−1,1+ai∗bi−1+ai−1∗bifi−1,2+ai∗bi−1+ai−1∗bi−2+ai−2∗bifi−1,2+ai∗bi−2+ai−1∗bi+ai−2∗bi−1 fi,1=fi−1,0 fi,2=fi−1,1 这个转移可以被描述成矩阵⎡⎣⎢⎢⎢ai∗biai∗bi−1+ai−1∗bimax{ai∗bi−1+ai−1∗bi−2+ai−2∗biai∗bi−2+ai−1∗bi+ai−2∗bi−1}0−inf−inf−inf0−inf⎤⎦⎥⎥⎥ 因为矩乘满足结合律，所以可以用线段树维护 #include <cstdio> #include <iostream> #include <algorithm> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> par; const int N=30010; const ll inf=1LL<<58; inline void fix(ll &x,ll y){ if(x<y) x=y; } struct Mat{ ll a[3][3]; ll *operator [](int x){ return a[x]; } void clear(){ for(int i=0;i<3;i++) for(int j=0;j<3;j++) a[i][j]=-inf; } friend Mat operator *(Mat a,Mat b){ Mat c; c.clear(); for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) fix(c.a[i][j],a.a[i][k]+b.a[k][j]); return c; } }mat[N<<2]; int n,m,l[N],p[N]; par a[N],b[N]; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void rea(int &x){ char c=nc(); x=0; for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc()); } inline bool match(int x,int y){ return l[a[x].se]!=b[y].se; } void Up(int g){ mat[g]=mat[g<<1]*mat[g<<1|1]; } void Modify(int g,int x,int L,int R){ if(L==R){ Mat &mat=::mat[g]; mat.clear(); mat[0][1]=mat[1][2]=0; if(match(x,x)) mat[0][0]=1LL*a[x].fi*b[x].fi; if(x>1 && match(x,x-1) && match(x-1,x)) mat[1][0]=1LL*a[x].fi*b[x-1].fi+1LL*a[x-1].fi*b[x].fi; if(x>2){ if(match(x,x-1) && match(x-1,x-2) && match(x-2,x)) mat[2][0]=1LL*a[x].fi*b[x-1].fi+1LL*a[x-1].fi*b[x-2].fi+1LL*a[x-2].fi*b[x].fi; if(match(x,x-2) && match(x-1,x) && match(x-2,x-1)) fix(mat[2][0],1LL*a[x].fi*b[x-2].fi+1LL*a[x-1].fi*b[x].fi+1LL*a[x-2].fi*b[x-1].fi); } return ; }int mid=L+R>>1; if(x<=mid) Modify(g<<1,x,L,mid); else Modify(g<<1|1,x,mid+1,R); Up(g); } void Build(int g,int l,int r){ mat[g].clear(); if(l==r) return ; int mid=l+r>>1; Build(g<<1,l,mid); Build(g<<1|1,mid+1,r); } int x,y; int main(){ rea(n); rea(m); Build(1,1,n); for(int i=1;i<=n;i++) rea(a[i].fi),a[i].se=i; for(int i=1;i<=n;i++) rea(b[i].fi),b[i].se=i; sort(a+1,a+1+n,greater<par>()); sort(b+1,b+1+n,greater<par>()); for(int i=1;i<=n;i++) p[a[i].se]=i; for(int i=1;i<=n;i++) l[i]=i; for(int i=1;i<=n;i++) Modify(1,i,1,n); while(m--){ rea(x); rea(y); swap(l[x],l[y]); for(int i=p[x];i<p[x]+3 && i<=n;i++) Modify(1,i,1,n); for(int i=p[y];i<p[y]+3 && i<=n;i++) Modify(1,i,1,n); printf("%lld\n",mat[1][0][0]); } return 0; }
