题目概述

给出 $\{a_n\}$ 和 $\{b_n\}$ 以及刚开始 $P_i=i$ 的排列 $\{P_n\}$ ，有 $m$ 个询问，每次询问先交换 $P_x,P_y$ ，然后询问 $max\{\sum_{i=1}^{n}a_ib_{p_i}|p_i\not=P_i\}$ 。

解题报告

首先根据排序不等式（WTF这是啥？）可以证明 $\{a_n\}$ 和 $\{b_n\}$ 排序之后一一匹配答案最大，而且可以证明如果强制不能选那么交换相邻的来使得满足条件是最优秀的。感觉挺对的反正我不会证明。

但这一看就不可做吧……找结论开始：每个 $i$ 至多只会和距离为 $2$ 的点匹配。感觉挺对的反正我不会证明。

那么也就是说我们只需要考虑最多三个之间的连边情况，可以考虑DP：$f[i]$ 表示前 $i$ 个的最优解，从 $f[i-1],f[i-2],f[i-3]$ 转移。但是多组询问，这样是 $O(nm)$ 的，还是会炸。

学习新姿势！其实这种极值DP也可以用矩阵来转移，那么我们可以改变定义便于构造矩阵：$f[i][0/1/2]$ 表示 $1\sim i-0/1/2$ 已经匹配完成的最优解，那么可以构造这么一个矩阵：

$$ \begin{bmatrix} a_ib_i&0&-\infty\\ a_ib_{i-1}+a_{i-1}b_i &-\infty&0\\ max\{a_ib_{i-1}+a_{i-1}b_{i-2}+a_{i-2}b_i,a_ib_{i-2}+a_{i-1}b_i+a_{i-2}b_{i-1}\}&-\infty&-\infty \end{bmatrix} $$

当然矩阵中的式子需要满足 $p_i\not=P_i$ ，否则为 $-\infty$ 。而 $\{P_i\}$ 是会变动的，但我们知道变动波及的范围只有 $3$ 而已，而矩阵满足结合率，所以直接用线段树暴力维护就行了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define fr first
#define sc second
typedef long long LL;
const int maxn=30000;

int n,te,P[maxn+5],pos[maxn+5];pair<int,int> a[maxn+5],b[maxn+5];
#define dif(x,y) (P[a[x].sc]!=b[y].sc)
#define val(x,y) ((LL)a[x].fr*b[y].fr)
struct Matrix{
    LL s[3][3];void Clear() {memset(s,192,sizeof(s));}
    inline void Update(int x){
        Clear();s[0][1]=s[1][2]=0;if (dif(x,x)) s[0][0]=val(x,x);
        if (x>1) if (dif(x,x-1)&&dif(x-1,x)) s[1][0]=val(x,x-1)+val(x-1,x);
        if (x>2){
            if (dif(x,x-2)&&dif(x-1,x)&&dif(x-2,x-1)) s[2][0]=val(x,x-2)+val(x-1,x)+val(x-2,x-1);
            if (dif(x,x-1)&&dif(x-1,x-2)&&dif(x-2,x)) s[2][0]=max(s[2][0],val(x,x-1)+val(x-1,x-2)+val(x-2,x));
        }
    }
    inline LL MAX() {LL MAX=0;for (int i=0;i<3;i++) MAX=max(MAX,s[i][0]);return MAX;}
}mat[(maxn<<2)+5];

inline Matrix operator * (const Matrix &a,const Matrix &b){
    static Matrix c;c.Clear();
    for (int i=0;i<3;i++)
        for (int j=0;j<3;j++)
            for (int k=0;k<3;k++)
                c.s[i][j]=max(c.s[i][j],a.s[i][k]+b.s[k][j]);return c;
}
#define Pushup(p) (mat[p]=mat[p<<1]*mat[p<<1|1])
void Update(int pos,int l=1,int r=n,int p=1){
    if (l==r) return mat[p].Update(pos);int mid=l+(r-l>>1);
    if (pos<=mid) Update(pos,l,mid,p<<1); else Update(pos,mid+1,r,p<<1|1);Pushup(p);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&te);for (int i=1;i<=n;i++) P[i]=i;
    for (int i=1;i<=n;i++) scanf("%d",&a[a[i].sc=i].fr);sort(a+1,a+1+n);
    for (int i=1;i<=n;i++) scanf("%d",&b[b[i].sc=i].fr);sort(b+1,b+1+n);
    for (int i=1;i<=n;i++) pos[a[i].sc]=i,Update(i);
    for (int x,y;te;te--){
        scanf("%d%d",&x,&y);swap(P[x],P[y]);
        for (int i=pos[x];i<pos[x]+3&&i<=n;i++) Update(i);
        for (int i=pos[y];i<pos[y]+3&&i<=n;i++) Update(i);
        printf("%lld\n",mat[1].MAX());
    }
    return 0;
}