0x03 前缀和与差分

激光炸弹

地图上有 个目标，用整数 表示目标在地图上的位置，每个目标都有一个价值 。
注意：不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式
第一行输入正整数 和 ，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。
接下来 行，每行输入一组数据，每组数据包括三个整数 ，分别代表目标的 坐标， 坐标和价值，数据用空格隔开。

输出格式
输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

,

输入样例：

2 1
0 0 1
1 1 1

输出样例：

1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10010, M = 5050;
int n, r, x, y, w;
int s[M][M];
int get(int x, int y, int x0, int y0) {
    return s[x0][y0] - s[x0][y-1] - s[x-1][y0] + s[x-1][y-1];
}
int main(){
    scanf("%d%d", &n, &r);
    int mx = 0, my = 0;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d", &x, &y, &w);
        x ++; y ++;
        mx = max(mx, x); my = max(my, y);
        s[x][y] += w;
    }
    for(int i=1;i<=mx;i++) for(int j=1;j<=my;j++) s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
    int rs = 0;
    for(int i=1;i<=mx;i++) for(int j=1;j<=my;j++){
        int x = max(1, i - r + 1), y = max(1, j - r + 1);
        rs = max(rs, get(x, y, i, j));
    }
    printf("%d\n", rs);
    return 0;
}

增减序列

给定一个长度为 的数列 ，每次可以选择一个区间 ，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
输入格式
第一行输入正整数 。
接下来 行，每行输入一个整数，第 行的整数代表 。

输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。

数据范围
,

输入样例：

4
1
1
2
2

输出样例：

1
2

此题是 铺设道路 的进阶版。
设 a 序列的差分序列为 b 序列。那么一次a区间加或者区间减对应b数组中的两个单点运算。
b[i] = a[i] - a[i-1]，那么应当有

• 区间加：
• 区间减：

所以，只要计算出 中正数的和 p 以及 负数的绝对值和 q，就可以得到答案。
当然 p 和 q 的数量可能不同，设 x = abs(p - q)，那么这 x 次区间操作，可以选择一部分修改 b[1], 也可以修改 b[n + 1]。
不难想到，最少操作数是 max(p, q)。
如果选择修改 b[1]，则相当于改变最终数组中所有数值的大小。所以共有 x + 1 种方案。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
int n;
ll a[N];
int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%lld", &a[i]);
    ll p = 0, q = 0;
    for(int i=2;i<=n;i++){
        ll c = a[i] - a[i-1];
        if(c > 0) p += c;
        else q -= c;
    }
    ll rs1 = max(p, q), rs2 = abs(p - q) + 1;
    printf("%lld\n%lld\n", rs1, rs2);
    return 0;
}

最高的牛

有 头牛站成一行，被编队为 ，每头牛的身高都为整数。
当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。
现在，我们只知道其中最高的牛是第 头，它的身高是 ，剩余牛的身高未知。
但是，我们还知道这群牛之中存在着 对关系，每对关系都指明了某两头牛 和 可以相互看见。
求每头牛的身高的最大可能值是多少。

输入格式
第一行输入整数 ，数据用空格隔开。
接下来 行，每行输出两个整数 和 ，代表牛 和牛 可以相互看见，数据用空格隔开。

输出格式
一共输出 行数据，每行输出一个整数。
第 行输出的整数代表第 头牛可能的最大身高。

数据范围
,
,
,

输入样例：

9 3 5 5
1 3
5 3
4 3
3 7
9 8

输出样例：

5
4
5
3
4
4
5
5
5

此题中给出的关系对可能存在重复
首先忽略掉第 p 头牛的身高 H，仅仅计算每头牛的身高差。
如果存在一对关系 ，那么 c[a + 1] —, c[b] ++。
最后所有的 c 应当加上 h - c[p]。
输入时，关系会重复出现，所以要去重。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 10010;
int n, p, h, m;
int c[N];
unordered_map<int, int> mp;
int main(){
    scanf("%d%d%d%d", &n, &p, &h, &m);
    rep(i,1,m) {
        int a, b;scanf("%d%d", &a, &b);
        if(a > b) swap(a, b);
        int x = a * 10000 + b;
        if(mp.count(x)) continue;
        mp[x] = 1;
        c[a + 1] --; c[b] ++;
    }
    rep(i,1,n) c[i] += c[i-1];
    int x = h - c[p];
    rep(i,1,n) c[i] += x;
    rep(i,1,n) printf("%d\n",c[i]);
    return 0;
}