# 算法竞赛进阶指南-0x03基本算法-前缀和与差分

Solution:

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int n, x, y, w, r;
int mx, my;
int s[5005][5005];

int main()
{
__;
cin >> n >> r;
mx = r, my = r;
for(int i = 1; i <= n; i ++){
cin >> x >> y >> w;
x ++;
y ++;
mx = max(x, mx), 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] + s[i][j];
}
}

int ans = 0;
for(int i = r; i <= mx; i ++){
for(int j = r; j <= my; j ++){
ans = max(ans, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
}
}

printf("%d\n", ans);
return 0;
}


IncDec序列

Solution:

pb 序列中正数之和，qb 序列中负数之和

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int n;
ll a[N], b[N];

int main(){
__;
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
ll p = 0, q = 0;
for(int i = 2; i <= n; i ++){
b[i] = a[i] - a[i - 1];
if(b[i] > 0)    p += b[i];
else    q -= b[i];
}
printf("%lld\n%lld\n", max(p, q), abs(p - q) + 1);
return 0;
}


N 头牛站成一行，被编队为 1、2、3…N

Solution:

D[a + 1] --, D[b] ++ \ (a<b), 然后从左到右前缀和，就可以求出矮多少。

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int n, p, h, m;
map<P, int> mp;
int c[N], d[N];

int main(){
__;
cin >> n >> p >> h >> m;
while(m --){
int a, b;
cin >> a >> b;
if(a > b)   swap(a, b);
if(mp[{a, b}])  continue;
mp[{a, b}] = 1;
d[a + 1] --, d[b] ++;
}
for(int i = 1; i <= n; i ++){
c[i] = c[i - 1] + d[i];
printf("%d\n", c[i] + h);
}

return 0;
}