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

比较套路的题目

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

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

然后直接上dp，由 $i-1,i-2,i-3$ 转移过来。

然后这显然可以拿矩阵表示。

然后显然可以拿线段树维护。

后面三部分都是比较套路的。

#include
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113