TIOJ 2150：塗鴉遊戲

TIOJ 2150：塗鴉遊戲

題目大意：有 $N$ 格一開始都是白色的格子，每個格子有一個穩定度 $w_i$。另外有 $M$ 個事件，每次事件有一個發生時刻 $t_j$ 還有一個影響範圍 $[a_j, b_j]$，你會把所有穩定度介在 $[a_j, b_j]$ 的格子塗成黑色。每單位時間，如果有 $x$ 個格子是白色的就可以帶來金額 $x$ 的收益。現在你有一些顏料，一單位的顏料可以在任何時候把任何一個格子塗白。定義 $f(i)$ 是假如你使用至多 $i$ 單位的顏料的話，在時間 $[0, T)$ 內所帶來的最大收益。請輸出 $(f(1) + f(2)+\dots +f(K))\ \bmod D$，保證 $D$ 是質數。

解法：首先先把 $w$ 排序好，每次二分搜出塗黑格子的範圍，並在開始和結束的地方做上記號，每次加入或刪除時間時紀錄時間區間加入的時間，並把這個區間大小的次數加上經過的時間，然後由大到小取差不多就可以了。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define TIOJQQ ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 5e5 + 5;

int N, M, T;
ll K;
int mod, inv;
int w[SIZE], ans, sum;
map<int, ll> mp;
vector<pair<int, bool>> op[SIZE];

set<int> s;
map<pair<int, int>, int> start;

void Add (int i, int t) {
    s.insert (t);
    auto it = s.find (t);
    if (it == s.begin()) {
        auto rit = next (it);
        start[{*it, *rit}] = i;
        return;
    }
    auto lit = prev (it), rit = next (it);
    mp[*rit - *lit] += i - start[{*lit, *rit}];
    start[{*lit, *it}] = start[{*it, *rit}] = i;
}

void Del (int i, int t) {
    auto it = s.find (t);
    if (it == s.begin()) {
        auto rit = next (it);
        mp[*rit - *it] += i - start[{*it, *rit}];
        s.erase (it);
        return;
    }
    auto lit = prev (it), rit = next (it);
    mp[*it - *lit] += i - start[{*lit, *it}];
    mp[*rit - *it] += i - start[{*it, *rit}];
    start[{*lit, *rit}] = i;
    s.erase (it);
}

void solve() {
    cin >> N >> M >> K >> T >> mod;
    if (mod != 2) inv = (mod + 1) / 2;
    FOR (i, 1, N) cin >> w[i];
    sort (w + 1, w + N + 1);
    while (M--) {
        int t, a, b, l, r;
        cin >> t >> a >> b;
        l = lower_bound (w + 1, w + N + 1, a) - w;
        r = upper_bound (w + 1, w + N + 1, b) - w;
        if (l < r) {
            op[l].pb (t, 1);
            op[r].pb (t, 0);
        }
    }
    s.insert (T);
    FOR (i, 1, N + 1) {
        for (auto [t, is] : op[i]) is ? Add (i, t) : Del (i, t);
        if (i <= N) ans = (ans + K % mod * *s.begin()) % mod;
    }
    for (auto it = mp.rbegin(); it != mp.rend(); it++) {
        auto [x, c] = *it;
        if (c == 0) continue;
        if (c >= K) {
            ll a = K + 1, b = K;
            if (mod == 2) {
                ((a & 1) ? b : a) >>= 1;
                a &= 1, b &= 1;
                sum ^= a & b & (x & 1);
            } else {
                sum = (sum + (a % mod) * (b % mod) % mod * x) % mod;
            }
            break;
        } else {
            ll a = 2 * K - c + 1, b = c;
            if (mod == 2) {
                ((a & 1) ? b : a) >>= 1;
                a &= 1, b &= 1;
                sum ^= a & b & (x & 1);
            } else {
                sum = (sum + (a % mod) * (b % mod) % mod * x) % mod;
            }
            K -= c;
        }
    }
    if (mod != 2) sum = 1ll * sum * inv % mod;
    cout << (ans + sum) % mod << '\n';
}

int main() {
    TIOJQQ;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！