B、Gaming

前置知识：线段树（区间修改+单点查询）

线段树是算法竞赛中常用的用来维护区间信息的数据结构。

线段树可以在 logn 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

问题解析

题目说，只要有一个debuff我们没有拿到，那么我们就可以战胜boss。那么我们可以去枚举每个debuff，看哪个debuff我们不要它后，得到的分数依然是最大的。（这里指的debuff是1~m中某个具体的数）

而我们不要哪个数，说明只要包含这个数的房间我们都不能进。

拿样例来说：

我们可以按照每个房间的区间，把分数加到这些数上。

还是样例：数字1~ 3都加上30，数字2~ 2都加上40，数字2~ 5都加上80，数字2~ 4都加上60.

最后这五个debuff各自代表的分数就是：30 210 140 60 80，总分数为n个房间分数之和（210）当我们不要哪个debuff后，就会从总分上扣除这些分数。

比如我们不要数字1，那么就会被扣去30分，最后得到的分数就是180分。

现在问题就是如何快速的实现区间加值和知道某个debuff的分数了，如果只是单纯的遍历区间一个个加，复杂度最大会到O(m^2),显然是不行的。

这时候我们就可以用线段树来解决这一问题，线段树的区间修改和单点查询的复杂度都是logn的。这样总复杂度就是O(mlogm).

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6+50, MOD = 1e9+7;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)res = (1LL) * res * a % MOD;
        b >>= 1;
        a = (1LL) * a * a % MOD;
    }
    return res;
}

ll a[N], f[4 * N], lz[4 * N];

void add(int k, int l, int r, int x, int y, ll c)
{
    if (l == x && y == r)
    {
        lz[k] += c;
        return;
    }
    f[k] += (y - x + 1) * c;
    int m = (l + r) / 2;
    if (y <= m)
        add(k + k, l, m, x, y, c);
    else
        if (x > m)add(k + k + 1, m + 1, r, x, y, c);
        else
        {
            add(k + k, l, m, x, m, c);
            add(k + k + 1, m + 1, r, m + 1, y, c);
        }
}

ll calc(int k, int l, int r, int x)
{
    if (l == r)
    {
        f[k] += lz[k];
        lz[k] = 0;
        return f[k];
    }
    lz[k + k] += lz[k];
    lz[k + k + 1] += lz[k];
    lz[k] = 0;
    int m = (l + r) / 2;
    if (x <= m)
        return calc(k + k, l, m, x);
    else
        return calc(k + k + 1, m + 1, r, x);
    f[k] = f[k + k] + f[k + k + 1];
}

void solve()
{
    int n, m, l, r, score, sum = 0, mx = 0;
    cin >> n >> m;
    vector<vector<int>>v(n, vector<int>(3)), res;
    for (int i = 0; i < n; i++)
    {
        cin >> l >> r >> score;
        add(1, 1, m, l, r, score);
        sum += score;
    }
    for (int i = 1; i <= m; i++)
    {
        int ans = calc(1, 1, m, i);
        mx = max(mx, sum - ans);
    }
    cout << mx << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

题解 | #B、Gaming#

B、Gaming

前置知识：线段树（区间修改+单点查询）

问题解析

AC代码