第1讲 基础算法

本讲代码模板：https://www.acwing.com/blog/content/277/

快速排序

AcWing 785. 快速排序

给定你一个长度为 $n$ 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 $n$。

第二行包含 $n$ 个整数（所有整数均在 $1 \sim 10^9$ 范围内），表示整个数列。

输出格式

输出共一行，包含 $n$ 个整数，表示排好序的数列。

数据范围

$1 \le n \le 100000$

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

题解

#include <iostream>

using namespace std;

const int kN = 1e5 + 10;
int a[kN];

void quick_sort(int l, int r) {
  if (l >= r) return;
  int i = l - 1, j = r + 1, x = a[(l + r) >> 1];
  while (i < j) {
    while (a[++i] < x) {};  // 没有 i < j
    while (a[--j] > x) {};
    if (i < j) swap(a[i], a[j]);
  }
  quick_sort(l, j);  // j, 而非i
  quick_sort(j + 1, r);
}

int main(){
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  quick_sort(0, n - 1);
  for (int i = 0; i < n; i++) printf("%d ", a[i]);
  return 0;
}	

AcWing 786. 第k个数

给定一个长度为 $n$ 的整数数列，以及一个整数 $k$，请用快速选择算法求出数列从小到大排序后的第 $k$ 个数。

输入格式

第一行包含两个整数 $n$ 和 $k$。

第二行包含 $n$ 个整数（所有整数均在 $1 \sim 10^9$ 范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第 $k$ 小数。

数据范围

$1 \le n \le 100000$,
$1 \le k \le n$

输入样例：

5 3
2 4 1 5 3

输出样例：

3

题解

#include <iostream>

using namespace std;

const int kN = 1e5 + 10;
int a[kN];

int quick_choose(int l, int r, int k) {
  if (l >= r) return a[l];
  int i = l - 1, j = r + 1, mid = (l + r) >> 1, pivot = a[mid];
  while (i < j) {
    while (a[++i] < pivot) {};
    while (a[--j] > pivot) {};
    if (i < j) swap(a[i], a[j]);
  }
  if (k <= j - l + 1) return quick_choose(l, j, k);   // j, 而非mid
  return quick_choose(j + 1, r, k - (j - l + 1));
}

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  printf("%d\n", quick_choose(0, n - 1, k));
  return 0;
}

归并排序

AcWing 787. 归并排序

给定你一个长度为 $n$ 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 $n$。

第二行包含 $n$ 个整数（所有整数均在 $1 \sim 10^9$ 范围内），表示整个数列。

输出格式

输出共一行，包含 $n$ 个整数，表示排好序的数列。

数据范围

$1 \le n \le 100000$

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

题解

#include <iostream>

using namespace std;

const int kN = 1e5 + 10;
int a[kN], tmp[kN];

void merge(int l, int r) {
  if (l >= r) return;  // 终止条件, 否则报TLE
  int mid = (l + r) >> 1;
  merge(l, mid);
  merge(mid + 1, r);
  int i = l, j = mid + 1, k = 0;
  while (i <= mid && j <= r) {
    if (a[i] <= a[j]) {
      tmp[k++] = a[i++];
    } else {
      tmp[k++] = a[j++];
    }
  }
  while (i <= mid) tmp[k++] = a[i++];
  while (j <= r) tmp[k++] = a[j++];
  for (int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];  // <=
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  merge(0, n - 1);
  for (int i = 0; i < n; i++) printf("%d ", a[i]);
  printf("\n");
  return 0;
}

AcWing 788. 逆序对的数量

给定一个长度为 $n$ 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 $i$ 个和第 $j$ 个元素，如果满足 $i < j$ 且 $a[i] > a[j]$，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 $n$，表示数列的长度。

第二行包含 $n$ 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

$1 \le n \le 100000$，
数列中的元素的取值范围 $[1,10^9]$。

输入样例：

6
2 3 4 5 6 1

输出样例：

5

题解

#include <iostream>

using namespace std;

const int kN = 1e5 + 10;
int a[kN], tmp[kN];

long long merge(int l, int r) {
  if (l >= r) return 0;
  
  int mid = (l + r) >> 1;
  long long res = merge(l, mid) + merge(mid + 1, r);
  int i = l, j = mid + 1, k = 0;
  while (i <= mid && j <= r) {
    if (a[i] <= a[j]) {
      tmp[k++] = a[i++];
    } else {
      tmp[k++] = a[j++];
      res += mid - i + 1;
    }
  }
  while (i <= mid) tmp[k++] = a[i++];
  while (j <= r) tmp[k++] = a[j++];
  for (int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
  return res;
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  printf("%lld\n", merge(0, n - 1));
  return 0;
}

二分

AcWing 789. 数的范围

给定一个按照升序排列的长度为 $n$ 的整数数组，以及 $q$ 个查询。

对于每个查询，返回一个元素 $k$ 的起始位置和终止位置（位置从 $0$ 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 $n$ 和 $q$，表示数组长度和询问个数。

第二行包含 $n$ 个整数（均在 $1 \sim 10000$ 范围内），表示完整数组。

接下来 $q$ 行，每行包含一个整数 $k$，表示一个询问元素。

输出格式

共 $q$ 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围

$1 \le n \le 100000$
$1 \le q \le 10000$
$1 \le k \le 10000$

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

题解

#include <iostream>

using namespace std;

const int kN = 1e5 + 10;
int a[kN];

int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  while (q--) {
    int k;
    scanf("%d", &k);
    
    int l = 0, r = n - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (a[mid] >= k) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    
    if (a[l] != k) {
      printf("-1 -1\n");
    } else {
      printf("%d ", l);
      l = 0, r = n - 1;
      while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (a[mid] <= k) {
          l = mid;
        } else {
          r = mid - 1;
        }
      }
      printf("%d\n", l);
    }
  }
  return 0;
}

AcWing 790. 数的三次方根

给定一个浮点数 $n$，求它的三次方根。

输入格式

共一行，包含一个浮点数 $n$。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 $6$ 位小数。

数据范围

$-10000 \le n \le 10000$

输入样例：

1000.00

输出样例：

10.000000

题解

#include <iostream>

using namespace std;

int main() {
  double n;
  scanf("%lf", &n);  // 必须.lf
  
  double l = -100, r = 100;  // double
  // 保留n位小数，一般区间宽度就小于1e-(n+2)
  while (r - l > 1e-8) {
    double mid = (l + r) / 2;
    if (mid * mid * mid >= n) {
      r = mid;
    } else {
      l = mid;
    }
  }
  printf("%.6lf\n", l);  // .6f或.6lf都行
  return 0;
}

高精度

AcWing 791. 高精度加法

给定两个正整数（不含前导 $0$），计算它们的和。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的和。

数据范围

$1 \le 整数长度 \le 100000$

输入样例：

12
23

输出样例：

35

高精度加法

C++中对于string不能使用 scanf("%s", a) 读取，建议使用 cin 读取或者使用C中 char [] 进行替代。

#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B) {
  if (A.size() < B.size()) return add(B, A);
  vector<int> C;
  int t = 0;
  for (int i = 0; i < A.size(); i++) {
    t += A[i];
    if (i < B.size()) t += B[i];
    C.push_back(t % 10);
    t /= 10;
  }
  if (t) C.push_back(t);
  return C;
}

int main() {
  string a, b;
  cin >> a >> b;  // a = "12345"
  
  vector<int> A, B;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');  // A = [5, 4, 3, 2, 1]
  for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
  
  vector<int> C = add(A, B);
  for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
  printf("\n");
  return 0;
}

AcWing 792. 高精度减法

给定两个正整数（不含前导 $0$），计算它们的差，计算结果可能为负数。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的差。

数据范围

$1 \le 整数长度 \le 10^5$

输入样例：

32
11

输出样例：

21

高精度减法

#include <iostream>
#include <vector>

using namespace std;

bool cmp(vector<int> &A, vector<int> &B) {
  if (A.size() != B.size()) return A.size() > B.size();
  for (int i = A.size() - 1; i >= 0; i--) {
    if (A[i] != B[i]) return A[i] > B[i];
  }
  return true;
}

vector<int> sub(vector<int> &A, vector<int> &B) {
  vector<int> C;
  int t = 0;
  for (int i = 0; i < A.size(); i++) {  // 从低到高
    t = A[i] - t;
    if (i < B.size()) t -= B[i];
    C.push_back((t + 10) % 10);
    t = (t < 0) ? 1: 0;
  }
  while (C.size() > 1 && C.back() == 0) C.pop_back();  // >1, 而非>0
  return C;
}

int main() {
  string a, b;
  cin >> a >> b;
  vector<int> A, B;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
  
  vector<int> C;
  if (cmp(A, B)) {
    C = sub(A, B);
  } else {
    printf("-");
    C = sub(B, A);
  }
  for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
  return 0;
}

AcWing 793. 高精度乘法

给定两个非负整数（不含前导 $0$） $A$ 和 $B$，请你计算 $A \times B$ 的值。

输入格式

共两行，第一行包含整数 $A$，第二行包含整数 $B$。

输出格式

共一行，包含 $A \times B$ 的值。

数据范围

$1 \le A 的长度 \le 100000$,
$0 \le B \le 10000$

输入样例：

2
3

输出样例：

6

法1 高精度 * 低精度

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, int b) {
  vector<int> C;
  int t = 0;
  for (int i = 0; i < A.size(); i++) {
    t += A[i] * b;
    C.push_back(t % 10);
    t /= 10;
  }
  if (t) C.push_back(t);
  while (C.size() > 1 && C.back() == 0) C.pop_back();
  return C;
}

int main() {
  string a;
  int b;
  cin >> a >> b;
  
  vector<int> A;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  vector<int> C = mul(A, b);
  for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
  return 0;
}

法2 高精度 * 高精度

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, vector<int> &B) {
  vector<int> C(A.size() + B.size() + 1, 0);  // 初始化为0
  for (int i = 0; i < A.size(); i++) {
    for (int j = 0; j < B.size(); j++) {
      C[i + j] += A[i] * B[j];  // +=, 而非=
    }
  }
  int t = 0;
  for (int i = 0; i < C.size(); i++) {
    t += C[i];
    C[i] = t % 10;
    t /= 10;
  }
  if (t) C.push_back(t);
  while (C.size() > 1 && C.back() == 0) C.pop_back();
  return C;
}

int main() {
  string a, b;
  cin >> a >> b;
  vector<int> A, B;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
  
  auto C = mul(A, B);
  for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
  return 0;
}

AcWing 794. 高精度除法

给定两个非负整数（不含前导 $0$） $A，B$，请你计算 $A / B$ 的商和余数。

输入格式

共两行，第一行包含整数 $A$，第二行包含整数 $B$。

输出格式

共两行，第一行输出所求的商，第二行输出所求余数。

数据范围

$1 \le A的长度 \le 100000$,
$1 \le B \le 10000$,
$B$ 一定不为 $0$

输入样例：

7
2

输出样例：

3
1

高精度除法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> div(vector<int> &A, int b, int &r) {
  vector<int> C;
  for (int i = A.size() - 1; i >= 0; i--) {  // 和+ - *不一样
    r = 10 * r + A[i];
    C.push_back(r / b);
    r %= b;
  }
  reverse(C.begin(), C.end());  // 让数字低位回到数组低位
  while (C.size() > 1 && C.back() == 0) C.pop_back();
  return C;
}

int main() {
  string a;
  int b;
  cin >> a >> b;
  vector<int> A;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  int r = 0;
  auto C = div(A, b, r);
  for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
  printf("\n%d\n", r);
  return 0;
}

前缀和与差分

AcWing 795. 前缀和

输入一个长度为 $n$ 的整数序列。

接下来再输入 $m$ 个询问，每个询问输入一对 $l, r$。

对于每个询问，输出原序列中从第 $l$ 个数到第 $r$ 个数的和。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示整数数列。

接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$，表示一个询问的区间范围。

输出格式

共 $m$ 行，每行输出一个询问的结果。

数据范围

$1 \le l \le r \le n$,
$1 \le n,m \le 100000$,
$-1000 \le 数列中元素的值 \le 1000$

输入样例：

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例：

3
6
10

前缀和

#include <iostream>

using namespace std;

const int kN = 1e5 + 10;
int a[kN], s[kN];

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {  // 1到n
    scanf("%d", &s[i]);
    s[i] += s[i - 1];
  }
  
  while (m--) {
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d\n", s[r] - s[l - 1]);
  }
  return 0;
}

AcWing 796. 子矩阵的和

输入一个 $n$ 行 $m$ 列的整数矩阵，再输入 $q$ 个询问，每个询问包含四个整数 $x_1, y_1, x_2, y_2$，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数 $n，m，q$。

接下来 $n$ 行，每行包含 $m$ 个整数，表示整数矩阵。

接下来 $q$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$，表示一组询问。

输出格式

共 $q$ 行，每行输出一个询问的结果。

数据范围

$1 \le n,m \le 1000$,
$1 \le q \le 200000$,
$1 \le x_1 \le x_2 \le n$,
$1 \le y_1 \le y_2 \le m$,
$-1000 \le 矩阵内元素的值 \le 1000$

输入样例：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例：

17
27
21

二维前缀和

#include <iostream>

using namespace std;

const int kN = 1010;
int s[kN][kN];

int main() {
  int n, m, q;
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      scanf("%d", &s[i][j]);
      s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    }
  }
  while (q--) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
  }
  return 0;
}

AcWing 797. 差分

输入一个长度为 $n$ 的整数序列。

接下来输入 $m$ 个操作，每个操作包含三个整数 $l, r, c$，表示将序列中 $[l, r]$ 之间的每个数加上 $c$。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示整数序列。

接下来 $m$ 行，每行包含三个整数 $l，r，c$，表示一个操作。

输出格式

共一行，包含 $n$ 个整数，表示最终序列。

数据范围

$1 \le n,m \le 100000$,
$1 \le l \le r \le n$,
$-1000 \le c \le 1000$,
$-1000 \le 整数序列中元素的值 \le 1000$

输入样例：

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例：

3 4 5 3 4 2

法1 b[i] = a[i] - a[i - 1]

#include <iostream>
#include <cstring>

using namespace std;

const int kN = 1e5 + 10;
int a[kN], b[kN];

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    b[i] = a[i] - a[i - 1];
  }
  while (m--) {
    int l, r, c;
    scanf("%d%d%d", &l, &r, &c);
    b[l] += c;
    b[r + 1] -= c;
  }
  for (int i = 1; i <= n; i++) {
    b[i] += b[i - 1];
    printf("%d ", b[i]);
  }
  return 0;
}

法2 通过insert()初始化b[i]

#include <iostream>
#include <cstring>

using namespace std;

const int kN = 1e5 + 10;
int a[kN], b[kN];

void insert(int l, int r, int c) {
  b[l] += c;
  b[r + 1] -= c;
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    insert(i, i, a[i]);  
  }
  while (m--) {
    int l, r, c;
    scanf("%d%d%d", &l, &r, &c);
    insert(l, r, c);
  }
  for (int i = 1; i <= n; i++) {
    b[i] += b[i - 1];
    printf("%d ", b[i]);
  }
  return 0;
}

AcWing 798. 差分矩阵

输入一个 $n$ 行 $m$ 列的整数矩阵，再输入 $q$ 个操作，每个操作包含五个整数 $x_1, y_1, x_2, y_2, c$，其中 $(x_1, y_1)$ 和 $(x_2, y_2)$ 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 $c$。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数 $n,m,q$。

接下来 $n$ 行，每行包含 $m$ 个整数，表示整数矩阵。

接下来 $q$ 行，每行包含 $5$ 个整数 $x_1, y_1, x_2, y_2, c$，表示一个操作。

输出格式

共 $n$ 行，每行 $m$ 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围

$1 \le n,m \le 1000$,
$1 \le q \le 100000$,
$1 \le x_1 \le x_2 \le n$,
$1 \le y_1 \le y_2 \le m$,
$-1000 \le c \le 1000$,
$-1000 \le 矩阵内元素的值 \le 1000$

输入样例：

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

输出样例：

2 3 4 1
4 3 4 1
2 2 2 2

二维差分

如果要将二维数组作为参数传递，写法为 void insert(int (*b)[N], int x1, int y1, int x2, int y2, int c)
二维数组的传法:第二维的大小必须传递。

#include <iostream>

using namespace std;

const int kN = 1010;
int a[kN][kN], b[kN][kN];

void insert(int x1, int y1, int x2, int y2, int c) {
  b[x1][y1] += c;
  b[x2 + 1][y1] -= c;
  b[x1][y2 + 1] -= c;
  b[x2 + 1][y2 + 1] += c;
}

int main() {
  int n, m, q;
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      scanf("%d", &a[i][j]);
      insert(i, j, i, j, a[i][j]);
    }
  }
  while (q--) {
    int x1, y1, x2, y2, c;
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
    insert(x1, y1, x2, y2, c);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
      printf("%d ", b[i][j]);
    }
    printf("\n");
  }
  return 0;
}

双指针算法

AcWing 799. 最长连续不重复子序列

给定一个长度为 $n$ 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数（均在 $0 \sim 10^5$ 范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围

$1 \le n \le 10^5$

输入样例：

5
1 2 2 3 5

输出样例：

3

双指针算法

#include <iostream>
#include <unordered_map>

using namespace std;

const int kN = 1e5 + 10;
int a[kN];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  
  unordered_map<int, int> hash;
  int res = 0;
  for (int i = 0, j = 0; j < n; j++) {
    hash[a[j]]++;
    while (i < j && hash[a[j]] > 1) {
      hash[a[i]]--;
      i++;
    }
    res = max(res, j - i + 1);
  }
  printf("%d\n", res);
  return 0;
}

队列等价

双指针算法 和 双向队列 是等价的，但是使用 双指针 能灵活高效。

queue<int> q;
for (int i = 0; i < n; i++) {  // 不能for (auto x: a)
  int x = a[i];
  q.push(x);
  hash[x]++;
  while (q.size() && hash[q.back()] > 1) {
    hash[q.front()]--;
    q.pop();
  }
  res = max(res, (int)q.size());  // 得转int
}

AcWing 800. 数组元素的目标和

给定两个升序排序的有序数组 $A$ 和 $B$，以及一个目标值 $x$。

数组下标从 $0$ 开始。

请你求出满足 $A[i] + B[j] = x$ 的数对 $(i, j)$。

数据保证有唯一解。

输入格式

第一行包含三个整数 $n,m,x$，分别表示 $A$ 的长度，$B$ 的长度以及目标值 $x$。

第二行包含 $n$ 个整数，表示数组 $A$。

第三行包含 $m$ 个整数，表示数组 $B$。

输出格式

共一行，包含两个整数 $i$ 和 $j$。

数据范围

数组长度不超过 $10^5$。
同一数组内元素各不相同。
$1 \le 数组元素 \le 10^9$

输入样例：

4 5 6
1 2 4 7
3 4 6 8 9

输出样例：

1 1

双指针

题目要求只有一对，但只要代码18行不break掉，是可以找出所有对的。

#include <iostream>

using namespace std;

const int kN = 1e5 + 10;
int a[kN], b[kN];

int main() {
  int n, m, x;
  scanf("%d%d%d", &n, &m, &x);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 0; i < m; i++) scanf("%d", &b[i]);
  
  for (int i = 0, j = m - 1; i < n; i++) {
    while (a[i] + b[j] > x) j--;
    if (a[i] + b[j] == x) {
      printf("%d %d\n", i, j);
      break;
    }
  }
  return 0;
}

AcWing 2816. 判断子序列

给定一个长度为 $n$ 的整数序列 $a_1,a_2,…,a_n$ 以及一个长度为 $m$ 的整数序列 $b_1,b_2,…,b_m$。

请你判断 $a$ 序列是否为 $b$ 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列，例如序列 ${a_1,a_3,a_5}$ 是序列 ${a_1,a_2,a_3,a_4,a_5}$ 的一个子序列。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数，表示 $a_1,a_2,…,a_n$。

第三行包含 $m$ 个整数，表示 $b_1,b_2,…,b_m$。

输出格式

如果 $a$ 序列是 $b$ 序列的子序列，输出一行 Yes。

否则，输出 No。

数据范围

$1 \le n \le m \le 10^5$,
$-10^9 \le a_i,b_i \le 10^9$

输入样例：

3 5
1 3 5
1 2 3 4 5

输出样例：

Yes

双指针

#include <iostream>

using namespace std;

const int kN = 1e5 + 10;
int a[kN], b[kN];

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 0; i < m; i++) scanf("%d", &b[i]);
  
  int i = 0, j = 0;
  while (i < n && j < m) {
    if (a[i] == b[j]) i++;
    j++;
  }
  if (i == n) {  // 看短的
    printf("Yes\n");
  } else {
    printf("No\n");
  }
  return 0;
}

位运算

AcWing 801. 二进制中1的个数

给定一个长度为 $n$ 的数列，请你求出数列中每个数的二进制表示中 $1$ 的个数。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数，表示整个数列。

输出格式

共一行，包含 $n$ 个整数，其中的第 $i$ 个数表示数列中的第 $i$ 个数的二进制表示中 $1$ 的个数。

数据范围

$1 \le n \le 100000$,
$0 \le 数列中元素的值 \le 10^9$

输入样例：

5
1 2 3 4 5

输出样例：

1 1 2 1 2

lowbit(x) = x & -x

题型: lowbit(x)返回x的最后一位1, 比如lowbit(20)=lowbit(10100_2)=100
方法: x & -x

#include <iostream>

using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    int x;
    scanf("%d", &x);
    int res = 0;
    while (x) {
      x -= x & -x;
      res++;
    }
    printf("%d ", res);
  }
  return 0;
}

离散化

AcWing 802. 区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是 $0$。

现在，我们首先进行 $n$ 次操作，每次操作将某一位置 $x$ 上的数加 $c$。

接下来，进行 $m$ 次询问，每个询问包含两个整数 $l$ 和 $r$，你需要求出在区间 $[l, r]$ 之间的所有数的和。

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $n$ 行，每行包含两个整数 $x$ 和 $c$。

再接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$。

输出格式

共 $m$ 行，每行输出一个询问中所求的区间内数字和。

数据范围

$-10^9 \le x \le 10^9$,
$1 \le n,m \le 10^5$,
$-10^9 \le l \le r \le 10^9$,
$-10000 \le c \le 10000$

输入样例：

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例：

8
0
5

离散化

排序 & 去重：

sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int kN = 3e5 + 10;  // 3e5
int a[kN], s[kN];

int find(vector<int> &alls, int x) {
  int l = 0, r = alls.size() - 1;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (alls[mid] >= x) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return l + 1;  // 离散化到[1, alls.size()], 方便求前缀和
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<int> alls;
  vector<PII> add, query;
  while (n--) {
    int x, c;
    scanf("%d%d", &x, &c);
    alls.push_back(x);
    add.push_back({x, c});
  }
  while (m--) {
    int l, r;
    scanf("%d%d", &l, &r);
    alls.push_back(l);
    alls.push_back(r);
    query.push_back({l, r});
  }
  sort(alls.begin(), alls.end());
  alls.erase(unique(alls.begin(), alls.end()), alls.end());
  for (auto x: add) {
    auto index = find(alls, x.first);
    a[index] += x.second;
  }
  for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];  // alls.size(), 而非n
  for (auto x: query) {
    auto l = find(alls, x.first), r = find(alls, x.second);
    printf("%d\n", s[r] - s[l - 1]);
  }
  return 0;
}

区间合并

AcWing 803. 区间合并

给定 $n$ 个区间 $[l_i, r_i]$，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：$[1,3]$ 和 $[2,6]$ 可以合并为一个区间 $[1,6]$。

输入格式

第一行包含整数 $n$。

接下来 $n$ 行，每行包含两个整数 $l$ 和 $r$。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

$1 \le n \le 100000$,
$-10^9 \le l_i \le r_i \le 10^9$

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

区间合并

初始守备区间在所有区间的左边, 然后遍历当各个区间, 各个区间与守备区间有3种关系：

1. 当前区间是守备区间的子集 -> 无更新
2. 当前区间左端和在守备区间左方, 而右端在守备区间右端右方 -> 守备区间右端更新为当前区间右端
3. 当前区间与守备区间无交集 -> 守备区间存入res, 并更新守备区间为当前区间

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int kN = 1e5 + 10;

vector<PII> merge(vector<PII> &segs) {
  sort(segs.begin(), segs.end());  // 排序
  vector<PII> res;
  int st = -2e9, ed = -2e9;
  for (auto x: segs) {
    if (x.first > ed) {
      if (st != -2e9) res.push_back({st, ed});
      st = x.first, ed = x.second;
    } else {
      ed = max(ed, x.second);
    }
  }
  if (st != -2e9) res.push_back({st, ed});  // 最后一个也要放
  return res;
}

int main() {
  int n;
  scanf("%d", &n);
  vector<PII> segs;
  while (n--) {
    int l, r;
    scanf("%d%d", &l, &r);
    segs.push_back({l, r});
  }
  auto res = merge(segs);
  printf("%d\n", res.size());
  return 0;
}