题解：P13789 「CZOI-R6」游戏

· · 题解

题目大意

有 q 局游戏，每局游戏会给一个坐标 (x_i,y_i)，然后每个 n \times m 矩阵中的点 (a,b)，都会有一个得分 u_i + k_1 \cdot \lvert x_i - a \rvert + k_2 \cdot \lvert y_i - b\rvert，对于每个点，求其在这 q 局游戏中得分的最大值。

分析

考虑对于每个点算答案，把左上、左下、右上、右下四个方向分开算得分，然后取 \max，这样就把绝对值拆掉了，讨论正负号即可。

以左下为例，得分就是：

u_i - k_1 \cdot x_i - k_2 \cdot y_i + k_1 \cdot a + k_2 \cdot b

枚举 (a,b)，右边两项就是固定的了，只需要对每局游戏的求左边三项和再取 \max。

这就转化成了一个二位偏序问题：查找左下角的 (x,y) 的贡献的最大值。

这里我当时没多想，直接按 x 从小到大枚举，再用两个树状数组查前后缀最大值，其实直接预处理前后缀最大值就行了。

时间复杂度 O(n^2)，我用的树状数组还得多个 log。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

ll read()
{
    ll ret = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) f = (ch == '-' ? -f : f), ch = getchar();
    while (isdigit(ch)) ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

int n ,m ,t;
ll k1 ,k2;
const int N = 3e3 + 10 ,M = 1e6 + 10;
const ll inf = 1e18;
struct node{
    ll x ,y ,u;
} q[M];
ll f[N][N];

//树状数组 
ll c1[N] ,c2[N];
#define lowbit(x) x & -x
void add1(ll *c ,int x ,ll k) { while (x < N) c[x] = max(c[x] ,k) ,x += lowbit(x); }
void add2(ll *c ,int x ,ll k) { while (x) c[x] = max(c[x] ,k) ,x -= lowbit(x); }
ll qry1(ll *c ,int x)
{
    ll ret = -inf;
    while (x) ret = max(ret ,c[x]) ,x -= lowbit(x);
    return ret;
}
ll qry2(ll *c ,int x)
{
    ll ret = -inf;
    while (x < N) ret = max(ret ,c[x]) ,x += lowbit(x);
    return ret;
}

ull qpow(ull a ,ull b)
{
    ull ret = 1;
    while (b)
    {
        if (b & 1) ret *= a;
        a *= a;
        b >>= 1;
    }
    return ret;
}

int main()
{
    n = read() ,m = read() ,t = read() ,k1 = read() ,k2 = read();
    for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) f[i][j] = -inf;

    for (int i = 1;i <= t;i++) q[i] = {read() ,read() ,read()};

    //按 x 坐标排序 
    sort(q + 1 ,q + 1 + t ,[](node a ,node b){ return a.x == b.x ? a.y < b.y : a.x < b.x; });

    for (int i = 0;i < N;i++) c1[i] = c2[i] = -inf;
    int now = 1;
    for (int i = 1;i <= n;i++) //x从小到大，计算左下、左上 
    {
        while (now <= t && q[now].x == i)
        {
            add1(c1 ,q[now].y ,q[now].u - q[now].x * k1 - q[now].y * k2);
            add2(c2 ,q[now].y ,q[now].u - q[now].x * k1 + q[now].y * k2);
            now++;
        }
        for (int j = 1;j <= m;j++)
            f[i][j] = max(f[i][j] ,i * k1 + j * k2 + qry1(c1 ,j)) ,
            f[i][j] = max(f[i][j] ,i * k1 - j * k2 + qry2(c2 ,j));
    }

    for (int i = 0;i < N;i++) c1[i] = c2[i] = -inf;
    now = t;
    for (int i = n;i >= 1;i--) //x从大到小，计算右下、右上 
    {
        while (now >= 1 && q[now].x == i)
        {
            add1(c1 ,q[now].y ,q[now].u + q[now].x * k1 - q[now].y * k2);
            add2(c2 ,q[now].y ,q[now].u + q[now].x * k1 + q[now].y * k2);
            now--;
        }
        for (int j = 1;j <= m;j++)
            f[i][j] = max(f[i][j] ,-i * k1 + j * k2 + qry1(c1 ,j)) ,
            f[i][j] = max(f[i][j] ,-i * k1 - j * k2 + qry2(c2 ,j));
    }

    ull ans = 0; //用自然溢出算答案 
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
            ans += f[i][j] * qpow(131 ,1LL * (i - 1) * m + j);

    printf("%llu\n",ans);

    return 0;
}