贪心找性质+dp表示+矩阵表示+线段树维护：CF573D
比较套路的题目
首先肯定贪心一波，两个都排序后尽量相连。我一开始猜最多跨1，但其实最多跨2，考虑3个人的情况：
我们发现第3个人没了，所以可以出现跨2的情况
然后直接上dp，由 i − 1 , i − 2 , i − 3 i-1,i-2,i-3 i−1,i−2,i−3 转移过来。
然后这显然可以拿矩阵表示。
然后显然可以拿线段树维护。
后面三部分都是比较套路的。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//#define M
//#define mo
#define N 30010
int n, m, i, j, k, T;
int a[N], b[N], ia[N], ib[N], shu[N], pos[N], x, y, q, rt;
int Not(int x, int y) { if(shu[ia[x]]!=ib[y]) return 1; return 0; }
struct Martix {
int c[3][3];
void mem() { memset(c, 0, sizeof(c)); }
void init() { mem(); c[0][0]=c[1][1]=c[2][2]=1; }
void min() { c[0][0]=c[0][1]=c[0][2]=c[1][0]=c[1][1]=c[1][2]=c[2][1]=c[2][2]=c[2][0]=-1e15; }
Martix operator *(const Martix A) const { //max+
Martix B; B.min();
for(int i=0; i<3; ++i)
for(int j=0; j<3; ++j)
for(int k=0; k<3; ++k)
B.c[i][j]=max(B.c[i][j], c[i][k]+A.c[k][j]);
return B;
}
void make(int x) {//生成在x位置的矩阵
min(); c[1][0]=c[2][1]=0;
if(Not(x, x)) c[0][0]=a[x]*b[x];
// if(x==1) return printf("# 1 : n"), (*this).print(), void();
if(x==1) return ;
if(Not(x, x-1) && Not(x-1, x)) c[0][1]=a[x]*b[x-1]+a[x-1]*b[x];
// if(x==2) return printf("# 2: n"), (*this).print(), void();
if(x==2) return ;
if(Not(x, x-1) && Not(x-1, x-2) && Not(x-2, x)) c[0][2]=max(c[0][2], a[x]*b[x-1]+a[x-1]*b[x-2]+a[x-2]*b[x]);
if(Not(x, x-2) && Not(x-1, x) && Not(x-2, x-1)) c[0][2]=max(c[0][2], a[x]*b[x-2]+a[x-1]*b[x]+a[x-2]*b[x-1]);
if(Not(x, x-2) && Not(x-1, x-1) && Not(x-2, x)) c[0][2]=max(c[0][2], a[x]*b[x-2]+a[x-1]*b[x-1]+a[x-2]*b[x]);
// printf("# %lld : n", x); (*this).print();
}
int que() {
// printf("RT : ");
// (*this).print();
Martix B; B.min(); B.c[0][0]=0;
B=(*this)*B; return B.c[0][0];
}
void print() {
printf("---n");
for(int i=0; i<3; ++i, printf("n"))
for(int j=0; j<3; ++j) printf("%lld ", c[i][j]);
printf("n");
}
};
struct Segment_tree {
int tot, ls[N<<2], rs[N<<2];
Martix s[N<<2];
void push_up(int k) { s[k]=s[rs[k]]*s[ls[k]]; } //注意乘法顺序
void build(int &k, int l, int r) {
if(!k) k=++tot;
if(l==r) return s[k].make(l), void();
int mid=(l+r)>>1;
build(ls[k], l, mid); build(rs[k], mid+1, r);
push_up(k);
}
void modify(int k, int l, int r, int x) {
if(l==r) return s[k].make(x), void();
int mid=(l+r)>>1;
if(x<=mid) modify(ls[k], l, mid, x);
else modify(rs[k], mid+1, r, x);
push_up(k);
// printf("[%lld %lld] : n", l, r); s[k].print();
}
}Seg;
signed main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// srand(time(NULL));
// T=read();
// while(T--) {
//
// }
n=read(); q=read();
for(i=1; i<=n; ++i) a[i]=read(), ia[i]=i, shu[i]=i; //shu：第i个人马的编号
for(i=1; i<=n; ++i) b[i]=read(), ib[i]=i;
sort(ia+1, ia+n+1, [] (int x, int y) { return a[x]>a[y]; });
sort(ib+1, ib+n+1, [] (int x, int y) { return b[x]>b[y]; });
sort(a+1, a+n+1); reverse(a+1, a+n+1); //按实力排好，则原顺序已经没必要了
sort(b+1, b+n+1); reverse(b+1, b+n+1);
// cout<<"ia : "; for(i=1; i<=n; ++i) printf("%lld ", ia[i]); puts("");
// cout<<"ib : "; for(i=1; i<=n; ++i) printf("%lld ", ib[i]); puts("");
// cout<<"a : "; for(i=1; i<=n; ++i) printf("%lld ", a[i]); puts("");
// cout<<"b : "; for(i=1; i<=n; ++i) printf("%lld ", b[i]); puts("");
//ia, ib排序后排名第i对应的原编号
for(i=1; i<=n; ++i) pos[ia[i]]=i; //某编号对应的排名
// cout<<"pos : "; for(i=1; i<=n; ++i) printf("%lld ", pos[i]); puts("");
Seg.build(rt, 1, n);
while(q--) {
x=read(); y=read(); swap(shu[x], shu[y]); //交换了马
// cout<<"shu : "; for(i=1; i<=n; ++i) printf("%lld ", shu[i]); puts("");
for(i=max(1ll, pos[x]-3); i<=min(n, pos[x]+3); ++i) Seg.modify(1, 1, n, i);
for(i=max(1ll, pos[y]-3); i<=min(n, pos[y]+3); ++i) Seg.modify(1, 1, n, i);
printf("%lldn", Seg.s[1].que());
}
return 0;
}