Practice Link

A. run

题意：
白云每次可以移动\(1\)米或者\(k\)米，询问移动的米数在\([L, R]\)范围内的方案数有多少。

思路：
\(dp[i][2]\)表示到第\(i\)米，是通过\(1\)米的方式过来的还是\(k\)米的方式过来的，递推即可。

代码：

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

#define N 100010
const int p = 1e9 + 7;
int f[N][2], g[N];
int q, k, l, r;
void add(int &x, int y) {
    x += y;
    if (x >= p) {
        x -= p;  
    }
}

int main() {
    scanf("%d%d", &q, &k);
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int i = 0; i <= 100000; ++i) {
        add(f[i + 1][0], (f[i][0] + f[i][1]) % p);
        if (i + k <= 100000) {
            add(f[i + k][1], f[i][0]);
        }
    } 
    memset(g, 0, sizeof g);
    for (int i = 1; i <= 100000; ++i) {
        g[i] = g[i - 1];
        add(g[i], f[i][0]);
        add(g[i], f[i][1]);
    }
    while (q--) {
        scanf("%d%d", &l, &r);
        printf("%d\n", (g[r] - g[l - 1] + p) % p);  
    }
    return 0;
}

D. monrey

题意：
有\(n\)个物品，从\(1\)到\(n\)的顺序去访问，身上最多只能携带一个物品，每次可以买进或者卖出物品，身上有无限的钱，问最后获得的利润最多是多少。

思路：
考虑将买入和卖出合并成一种操作，买入就是减去收益，卖出是增加收益，维护两个堆，遍历\(i\)个物品。

• 如果当次是买入，那么去找之前收益最高的一个卖出操作，或者直接买入。
• 如果当次是卖出，那么取找之前收益最高的一个买入操作。

代码:

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

#define ll long long
#define N 100010
int n, a[N]; 
struct node {
    ll tot; int cnt;
    node() {}
    node (ll tot, int cnt) : tot(tot), cnt(cnt) {} 
    bool operator < (const node &other) const {
        if (tot == other.tot) {
            return cnt > other.cnt;
        }
        return tot < other.tot;
    }
};

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
        }
        //0表示上一次操作是买入
        //1表示上一次操作是卖出 
        priority_queue <node> pq[2];
        node res = node(0, 0);
        pq[0].push(node(-a[1], 1));
        node t1, t2;
        for (int i = 2; i <= n; ++i) {
            pq[0].push(node(-a[i], 1));
            if (!pq[0].empty()) {
                t1 = pq[0].top();
                pq[1].push(node(t1.tot + a[i], t1.cnt + 1));
            }
            if (!pq[1].empty()) {
                t2 = pq[1].top();
                pq[0].push(node(t2.tot - a[i], t2.cnt + 1));
            }
            if (!pq[1].empty()) {
                res = max(res, pq[1].top());
            }
        }
        printf("%lld %d\n", res.tot, res.cnt);
    }
    return 0;
}

J. farm

题意：
在\(n \cdot m\)的农田上，有\(n \cdot m\)棵植物，每棵植物只能施放第\(a[i][j]\)种肥料，有\(T\)次操作，每次操作时将\(x_1, y_1, x_2, y_2\)矩形内的作物都施上第\(k_i\)种肥料，
一旦作物被施上不是第\(a[i][j]\)种肥料，它就会立刻死亡。
问最后死亡的作物数目.

思路一：
考虑：
作物的施肥次数 = 第\(a[i][j]\)种肥料的施肥次数+其他种类肥料的施肥次数。
我们先二维差分求出所有作物的总的施肥次数。
然后将操作按\(k_i\)分类，用二维BIT维护二维前缀和，表示\(k_i\)操作下作物的施肥次数。
然后再枚举初始值为\(k_i\)的所有作物，判断它总的施肥次数以及第\(k_i\)种肥料的施肥次数是否相等，不相等就挂了。
时间复杂度：\(\mathcal{O}(nm + T \cdot log(n) \cdot log(m))\)

代码一：

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

#define N 1000010
#define pii pair <int, int>
#define fi first
#define se second
int n, m, q;
struct node {
    int x[2], y[2];
    node() {}
    node(int x1, int y1, int x2, int y2) {
        x[0] = x1; x[1] = x2;
        y[0] = y1; y[1] = y2;  
    }
};
vector < vector <pii> > a;
vector < vector <node> > b;

struct BIT {
    vector < vector <int> > a;
    void init() {
        a.clear();
        a.resize(n + 1);
        for (int i = 0; i < n + 1; ++i) {
            a[i].resize(m + 1);
        }
    }
    void update(int x, int y, int v) {
        for (int i = x; i <= n; i += i & -i) {
            for (int j = y; j <= m; j += j & -j) {
                a[i][j] += v;
            }
        }
    }
    void update(int x1, int y1, int x2, int y2, int v) {
        update(x1, y1, v);
        update(x2 + 1, y2 + 1, v); 
        update(x1, y2 + 1, -v);
        update(x2 + 1, y1, -v);
    }
    int query(int x, int y) {
        int res = 0;
        for (int i = x; i > 0; i -= i & -i) {
            for (int j = y; j > 0; j -= j & -j) {
                res += a[i][j]; 
            }
        }
        return res;
    }
}bit;

void read(int &x) {
    x = 0; char ch;
    while (!isdigit(ch = getchar()));
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}

int main() {
    while (scanf("%d%d%d", &n, &m, &q) != EOF) {
        a.clear(); 
        a.resize(n * m + 1);
        b.clear();
        b.resize(n * m + 1);
        bit.init();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1, x; j <= m; ++j) {
                read(x);
                a[x].emplace_back(i, j);
            }
        }
        for (int i = 1, k, x1, y1, x2, y2; i <= q; ++i) {
            read(x1); read(y1); read(x2); read(y2); read(k);
            b[k].push_back(node(x1, y1, x2, y2));
            bit.update(x1, y1, x2, y2, 1);
        }
        int res = 0;
        for (int i = 1; i <= n * m; ++i) {
            for (auto it : b[i]) {
                bit.update(it.x[0], it.y[0], it.x[1], it.y[1], -1);
            }
            for (auto it : a[i]) {
                if (bit.query(it.fi, it.se) != 0) {
                    ++res;
                }
            }
            for (auto it : b[i]) {
                bit.update(it.x[0], it.y[0], it.x[1], it.y[1], 1);
            }
        }
        printf("%d\n", res);
    }
    return 0;
}