佳佳有一个n*m的带权矩阵，她想从(1,1)出发走到(n,m)且只能往右往下移动，她能得到的娱乐值为所经过的位置的权的总和。
有一天，她被下了恶毒的诅咒，这个诅咒的作用是将她的娱乐值变为对p取模后的值，这让佳佳十分的不开心，因为她无法找到一条能使她得到最大娱乐值的路径了！
她发现这个问题实在是太困难了，既然这样，那就只在3*n的矩阵内进行游戏吧！
现在的问题是，在一个3*n的带权矩阵中，从(1,1)走到(3,n)，只能往右往下移动，问在模p意义下的移动过程中的权总和最大是多少。
样例解释：
移动的方案为“下下右”。
输入
单组测试数据
第一行两个数n(1<=n<=100000),p(1<=p<=1000000000)。
接下来3行，每行n个数，第i行第j列表示a[i][j]表示该点的权(0<=a[i][j]<p)。
输出
一个整数表示答案。
输入样例
2 3
2 2
2 2
0 1
输出样例
2
很容易看出来 整条路径分成三行 只有两个拐点
路径中是有三条线段的 我们可以统计每一行的前缀和
所以我们有下面的计算公式 sum[1][x]+sum[2][y]-sum[2][x-1]+sum[3][n]-sum[3][y-1]
把上述式子换一下位置 sum[1][x]-sum[2][x-1] + sum[2][y]+sum[3][n]-sum[3][y-1]
所以 我们可以想到来枚举 x 和 y 寻找最长路径 从图中可以看出 两个拐点的关系 x<=y 这个很重要
考虑枚举x，那么问题转化为询问在一堆数中求一个数k使得v(=a[x]+S[3][n])+k mod p最大
分两种情况考虑，第一种v+k∈[v,mod−1]，那么k∈[0,mod−k−1]，并且k越大越好
第二种不如第一种好，但有可能不得不选，v+k∈[1,v−1]，同样时k越大越好
也就是说，需要一种支持插入，查询前驱和最大值的数据结构，set就可以
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; int a[maxn], b[maxn]; int sum[4][maxn]; int n, mod, x; set<int> st; set<int> ::iterator it; int main() { scanf("%d%d", &n, &mod); for (int i = 1; i <= 3; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &x); sum[i][j] = (sum[i][j - 1] + x) % mod; } } for (int i = 1; i <= n; i++) { a[i] = ((sum[1][i] - sum[2][i - 1]) % mod + mod) % mod; b[i] = ((sum[2][i] - sum[3][i - 1]) % mod + mod) % mod; } int res = sum[3][n]; int ans = 0; st.insert(-1); for (int i = n; i >= 1; i--) { st.insert(b[i]); int tmp = (res + a[i]) % mod; x = ((mod - tmp - 1) % mod + mod) % mod; it = st.lower_bound(x); ans = max(ans, (tmp + *(--st.end())) % mod); ans = max(ans, (tmp + *it) % mod); it--; if (*it != -1) { ans = max(ans, (tmp + *it) % mod); } } printf("%d\n", ans); return 0; }
