贪心找性质+dp表示+矩阵表示+线段树维护：CF573D

比较套路的题目

首先肯定贪心一波，两个都排序后尽量相连。我一开始猜最多跨1，但其实最多跨2，考虑3个人的情况：

在这里插入图片描述

我们发现第3个人没了，所以可以出现跨2的情况

然后直接上dp，由 $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("%lld\n", Seg.s[1].que()); }return 0;
}