【CF573D】Bear and Cavalry
题意：有n个人和n匹马，第i个人对应第i匹马。第i个人能力值ai，第i匹马能力值bi，第i个人骑第j匹马的总能力值为ai*bj，整个军队的总能力值为$\sum a_ib_j$（一个人只能骑一匹马，一匹马只能被一个人骑）。有一个要求：每个人都不能骑自己对应的马。让你制定骑马方案，使得整个军队的总能力值最大。现在有q个操作，每次给出a,b，交换a和b对应的马。每次操作后你都需要输出最大的总能力值。
$n\le 30000,q\le 10000$
题解：如果不考虑人不能骑自己的马这个限制的话，将人和马都按能力值从大到小排序后，肯定是能力值最大的人骑能力值最大的马，以此类推。但如果考虑这个限制，就有一个很神的结论：如果排名第i的人对应排名第j的马，则|i-j|<3（不会证，可以看官方题解）。
那么就有了一个比较基础的DP解法。令f[i]表示前i个人对应前i匹马的最大值，则f[i]有这几种转移：
i对应i
i对应i-1,i-1对应i
i对应i-1,i-1对应i-2,i-2对应i
i对应i-2,i-2对应i-1,i-1对应i
如果带修改，我们用线段树来维护，令f[i][a][b]表示i这个节点，左边a个没取，右边b个没取时的最大值。合并时细节比较多。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson x<<1
#define rson x<<1|1
using namespace std;
const int maxn=30010;
typedef long long ll;
int n,m;
ll A[maxn],B[maxn],emp[3][3];
int ban[maxn],ra[maxn],rb[maxn];
struct node
{
int a,b;
}pa[maxn],pb[maxn];
struct M
{
ll v[3][3];
int l,r;
M operator + (const M &a) const
{
M b;
b.l=l,b.r=a.r;
int i,j;
for(i=0;i<3;i++) for(j=0;j<3;j++)
{
if(l+i==a.r-j+1)
{
b.v[i][j]=0;
continue;
}
if(l+i>a.r-j+1)
{
b.v[i][j]=-(1ll<<60);
continue;
}
if(r-l+1<i)
{
b.v[i][j]=a.v[i][i-(r-l+1)];
}
if(a.r-a.l+1<j)
{
b.v[i][j]=v[i][j-(a.r-a.l+1)];
continue;
}
int x=r,y=a.l;
b.v[i][j]=v[i][0]+a.v[0][j];
if(ban[x]!=y&&ban[y]!=x) b.v[i][j]=max(b.v[i][j],v[i][1]+a.v[1][j]+A[x]*B[y]+B[x]*A[y]);
if(ban[x]!=y&&ban[y]!=y+1&&ban[y+1]!=x) b.v[i][j]=max(b.v[i][j],v[i][1]+a.v[2][j]+A[x]*B[y]+A[y]*B[y+1]+A[y+1]*B[x]);
if(ban[x]!=y+1&&ban[y]!=x&&ban[y+1]!=y) b.v[i][j]=max(b.v[i][j],v[i][1]+a.v[2][j]+A[x]*B[y+1]+A[y]*B[x]+A[y+1]*B[y]);
if(ban[x-1]!=x&&ban[x]!=y&&ban[y]!=x-1) b.v[i][j]=max(b.v[i][j],v[i][2]+a.v[1][j]+A[x-1]*B[x]+A[x]*B[y]+A[y]*B[x-1]);
if(ban[x-1]!=y&&ban[x]!=x-1&&ban[y]!=x) b.v[i][j]=max(b.v[i][j],v[i][2]+a.v[1][j]+A[x-1]*B[y]+A[x]*B[x-1]+A[y]*B[x]);
}
return b;
}
}s[maxn<<2]; bool cmp(const node &a,const node &b)
{
return (a.a==b.a)?(a.b>b.b):(a.a>b.a);
}
void build(int l,int r,int x)
{
if(l==r)
{
memcpy(s[x].v,emp,sizeof(emp));
s[x].v[0][1]=s[x].v[1][0]=0,s[x].l=s[x].r=l;
if(ban[l]!=l) s[x].v[0][0]=A[l]*B[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
s[x]=s[lson]+s[rson];
}
void updata(int l,int r,int x,int a)
{
if(l==r)
{
memcpy(s[x].v,emp,sizeof(emp));
s[x].v[0][1]=s[x].v[1][0]=0,s[x].l=s[x].r=l;
if(ban[l]!=l) s[x].v[0][0]=A[l]*B[l];
return ;
}
int mid=(l+r)>>1;
if(a<=mid) updata(l,mid,lson,a);
else updata(mid+1,r,rson,a);
s[x]=s[lson]+s[rson];
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
n=rd(),m=rd();
int i,a,b;
for(i=1;i<=n;i++) pa[i].a=rd(),pa[i].b=i;
for(i=1;i<=n;i++) pb[i].a=rd(),pb[i].b=i;
sort(pa+1,pa+n+1,cmp),sort(pb+1,pb+n+1,cmp);
for(i=1;i<=n;i++)
{
ra[pa[i].b]=i,rb[pb[i].b]=i,A[i]=pa[i].a,B[i]=pb[i].a;
}
for(i=1;i<=n;i++) ban[ra[i]]=rb[i];
for(a=0;a<3;a++) for(b=0;b<3;b++) emp[a][b]=-(1ll<<60);
//A[0]=B[0]=A[n+1]=B[n+1]=-(1ll<<60);
build(1,n,1);
for(i=1;i<=m;i++)
{
a=ra[rd()],b=ra[rd()];
swap(ban[a],ban[b]);
updata(1,n,1,a),updata(1,n,1,b);
printf("%lld\n",s[1].v[0][0]);
}
return 0;
}//4 3 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 3 4 3 2 4 3