[CF514D] R2D2 and Droid Army

[CF514D] R2D2 and Droid Army - 双指针,ST表

Description

一共有N个人，每个人有M ((M le 5)) 个属性值，当一个人的所有属性值都小于等于0的时候，这个人就算被销毁了。我们每次操作可以选一种属性值进行攻击，使得所有人的这个属性的值都-1.我们最多可以进行K次操作，问我们最多可以干掉多少个连续的人。问这种时候的具体操作。

Solution

考虑二分答案长度加验证，过程中 RMQ 可以用单调队列维护，也可以直接 ST 表

考虑到右端点关于左端点的单调性，可用用双指针处理

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 200005;
const int M = 20;

int lg2[N];

struct RMQ
{
    int a[N][M];

    void build(int n, int *src)
    {
        for (int i = 1; i <= n; i++)
            a[i][0] = src[i];
        for (int j = 1; j < M; j++)
            for (int i = 1; i + (1 << (j - 1)) <= n; i++)
            {
                a[i][j] = max(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
            }
    }

    int query(int l, int r)
    {
        int k = lg2[r - l + 1];
        return max(a[l][k], a[r - (1 << k) + 1][k]);
    }
} rmq[6];

int n, m, k, a[7][N];

int check(int l, int r)
{
    int sum = 0;
    for (int i = 1; i <= m; i++)
    {
        sum += rmq[i].query(l, r);
    }
    return sum <= k;
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++)
        lg2[i] = log2(i);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[j][i];
        }
    }

    for (int i = 1; i <= m; i++)
    {
        rmq[i].build(n, a[i]);
    }

    int ans = 0;
    int ansx[7] = {};
    int r = 1;

    for (int l = 1; l <= n; l++)
    {
        r = max(r, l);
        while (r < n && check(l, r + 1))
            ++r;
        if (check(l, r) && r - l + 1 > ans)
        {
            ans = r - l + 1;
            for (int i = 1; i <= m; i++)
            {
                ansx[i] = rmq[i].query(l, r);
            }
        }
    }

    for (int i = 1; i <= m; i++)
        cout << ansx[i] << " ";
    cout << endl;
}