前缀和与差分 - 牛客刷题

Posted on Edited on In , , Views: Word count in article: 2.6k Reading time ≈ 9 mins.

刷点题，应用和理论还是差蛮多的（）

  • 前缀和
  • 差分

校门外的树

写完发现做过了（）
这是暴力做法，对于 。NBUACM2024 - F

题目描述

某校大门外长度为 的马路上有一排树,每两棵相邻的树之间的间隔都是 米。我们可以把马路看成一个数轴,马路的一端在数轴 的位置,另一端在 的位置；数轴上的每个整数点,即 ,都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后,马路上还有多少棵树。

输入描述

第一行有两个整数：（）和 （）, 代表马路的长度, 代表区域的数目, 和 之间用一个空格隔开。接下来的 行每行包含两个不同的整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标。

输出描述

包括一行,这一行只包含一个整数,表示马路上剩余的树的数目。

示例 1

输入

1
2
3
4
500 3
150 300
100 200
470 471

输出

1
298

备注

对于 20%的数据,区域之间没有重合的部分；
对于其它的数据,区域之间有重合的情况。

Solution

一开始是考虑直接 区间合并

AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define mod (int)(1e9 + 7)
#define int long long
#define endl '\n'
#define pb push_back
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MAX = 0x3f3f3f3f;
const ll LLMAX = 9223372036854775807;
const double PI = acos(-1);
using namespace std;
void solve() {
  int L, M;
  cin >> L >> M;
  int sum = L + 1;
  int l, r;
  vector<PII> intervals, merged;
  for (int i = 1; i <= M; i++) {
    cin >> l >> r;
    intervals.push_back({l, r});
  }
  sort(intervals.begin(), intervals.end());
  for (auto pr : intervals) {
    if (!merged.size() || merged.back().second < pr.first)
      merged.push_back(pr);
    else
      merged.back().second = max(pr.second, merged.back().second);
  }
  for (auto pr : merged) {
    sum -= pr.second - pr.first + 1;
  }
  cout << sum << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}

后来看了题解，是差分+前缀和

注意到我们是对一系列区间内元素进行相同操作，因此可以使用差分，实现 的区间修改。

我们可以将有树的位置设为 ，而将一个区间内元素全部做 操作，随后我们只需统计为 的位置的个数，也即是未砍的树。

AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define mod (int)(1e9 + 7)
#define int long long
#define endl '\n'
#define pb push_back
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MAX = 0x3f3f3f3f;
const ll LLMAX = 9223372036854775807;
const double PI = acos(-1);
using namespace std;
int diff[(int)1e5 + 10];
void solve() {
  int L, M;
  cin >> L >> M;
  int l, r;
  for (int i = 0; i < M; i++) {
    cin >> l >> r;
    if (l > r) swap(l, r);
    diff[l]++;
    diff[r + 1]--;
  }
  // a_(-1) = 0
  // a[0] = 0 + d[0]
  // a[1] = a[0] + d[1]
  // a [n] = a[n-1] + d[n]
  int a = 0, ans = 0;
  for (int i = 0; i <= L; i++) {
    a += diff[i];
    ans += a == 0;
  }
  cout << ans << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}

[CQOI2009]中位数图

题目描述

给出 的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是 。中位数是指把所有元素从小到大排列后，位于中间的数。

输入描述

第一行为两个正整数 和 ，第二行为 的排列。

输出描述

输出一个整数，即中位数为 的连续子序列个数。

示例

示例 1

输入
1
2
7 4
5 7 2 4 3 1 6
输出
1
4

备注

对于 30%的数据中，满足 ；

对于 60%的数据中，满足 ；

对于 100%的数据中，满足 。

Solution

除了暴力没思路，遂看题解

  • 参考了 Eihuvita 的 post

应该是老题了，中位数计数 .

考虑到给的是一个排列，因此里面的数只有 种情况:

  • (这个 是唯一的)

因为要求的是 奇数长连续子序列， 因此中位数是排序后位于中间数，那么中位数两边的数的个数是相等的，换而言之 大于的数的个数 = 小于的数的个数，因此我们只需要找符合这个条件的区间即可（这个区间需要包含 ）.

那么为了处理这个问题，我们可以将大于 的数标记为 ，小于 的数标记为 ，将 标记为 .

那么一个区间，其区间上的和为 且这个区间含 就是一个符合条件的区间。我们可以考虑将这个区间分为两部分：

  • 含 且在原排列中 的左边的区间，这一区间上的和记为
  • 含 且在原排列中 的右边的区间，这一区间上的和记为

那么符合条件的区间有 ，（注意这里含 对区间的和没有影响，但是 也算一个符合条件的连续子序列，因此这样处理更加方便）.

这两部分的区间和，我们可以通过 前缀和 的解决 .

那么具体筛选符合条件的区间时，我们需要找到所有符合 一组区间。因此，我们可以先遍历 含 且在原排列中 的右边的区间 或 含 且在原排列中 的左边的区间，并记录每个不同数值的前缀和的出现次数。然后我们遍历另一个区间，计算其前缀和，尝试在我们记录的值中找到其相反数，并将其出现次数累加到答案。

为什么是计次呢？
可以这样考虑，我们已经确定了一个 ，那么 ，我们可以任意选择符合 的区间 .

AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define mod (int)(1e9 + 7)
#define int long long
#define endl '\n'
#define pb push_back
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MAX = 0x3f3f3f3f;
const ll LLMAX = 9223372036854775807;
const double PI = acos(-1);
using namespace std;
int a[(int)1e5 + 10];
map<int, int> mmp;
void solve() {
  int n, b, idx, sum, ans;
  cin >> n >> b;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] == b) idx = i;
    if (a[i] > b)
      a[i] = 1;
    else if (a[i] < b)
      a[i] = -1;
    else
      a[i] = 0;
  }
  sum = 0;
  for (int i = idx; i < n; i++) {
    sum += a[i];
    mmp[sum]++;
  }
  sum = ans = 0;
  for (int i = idx; i >= 0; i--) {
    sum += a[i];
    ans += mmp[-sum];
  }
  cout << ans << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}

二分

题目描述

我们刚刚学了二分查找——所谓二分查找就是在一堆有序数里找某个符合要求的数。在学完二分查找之后如果让你玩猜数游戏（裁判选定一个目标数字，你说一个数裁判告诉你是高了还是低了直到你猜到那个数）的话，显然你会用二分的方式去猜。
但是不是每一个玩猜数游戏的人都知道二分是最好，甚至一个健忘的玩家都有可能在得到裁判回答的下一个瞬间就忘了他之前问了什么以及裁判的回答），而现在更可怕的是，这个告诉你猜的数是高还是低的裁判他也很健忘，他总是薛定谔的记得这个目标数字，也就是说他的回答有可能出错。我们已经不关心这个不靠谱的游戏本身了，我们更关心裁判这个薛定谔的记得到底有几个是记得......
现在给出这个健忘的玩家的所有猜测和裁判的所有回答，问裁判最多能有多少次是记得目标数字的，即裁判的回复是符合情况的。

输入描述

第一行包含一个正整数 ，表示裁判的回答数（也是玩家的猜数次数）。
接下来 行，首先是猜的数，然后是一个空格，然后是一个符号。符号如果是“+”说明猜的数比答案大，“-”说明比答案小，“.”说明猜到了答案。

输出描述

包含一个正整数，为裁判最多有多少个回答是正确的。

示例

示例 1

输入
1
2
3
4
5
4
5 .
8 +
5 .
8 -
输出
1
3

说明

当目标数是 时，5 ., 5 ., 8 + 这三个回答都是正确的

备注

所有数的大小都小于 int 类型最大值。

Solution

其实是枚举，，当其中某个数符合条件时，就 +1，最后取最大的计数即可。但这个范围太大了，而且对于 大于 或 小于 的判断，我们需要一直区间两端的数进行递增递减，因此我们想到差分。而对于这么大范围的数据，可以使用离散差分，因为我们不关注具体的数值，同时我们可以使用一个 map 进行存取。

记每次猜的数字是 ，分 3 种情况：

  • 等于: 将 的计数 +1
    • map[x]++, map[x+1]--;
  • 大于: 将 的计数 +1
    • map[-INT_MAX]++, map[x]--;
  • 小于: 将 的计数 +1
    • map[x+1]++, map[INT_MAX]--;
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define mod (int)(1e9 + 7)
#define int long long
#define endl '\n'
#define pb push_back
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MAX = 0x3f3f3f3f;
const ll LLMAX = 9223372036854775807;
const double PI = acos(-1);
using namespace std;
map<int, int> mmp;
void solve() {
  int n;
  cin >> n;
  int x;
  char c;
  for (int i = 0; i < n; i++) {
    cin >> x >> c;
    if (c == '.')
      mmp[x]++, mmp[x + 1]--;
    else if (c == '+')
      mmp[-INT_MAX]++, mmp[x]--;
    else if (c == '-')
      mmp[x + 1]++, mmp[INT_MAX]--;
  }
  int ans = -INT_MAX, sum = 0;
  for (auto pr : mmp) sum += pr.second, ans = max(sum, ans);
  cout << ans << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}