一. 快速排序
1.1 快速排序
主要思想:分治法
1)确定边界点
2)重新调整区间,使得第一区间小于等于x ,第二区间大于等于x(重点)
3)递归处理左右两端
C++
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r){
if(l >= r) {
return ;
}
int i = l - 1, j = r + 1, x = q[l+r >> 1];
//注意在<或者>情况下不停止循环
//用do-while是为了保证每次运行必然会使区间缩小,避免死循环
while(i < j) {
do{
i++;
}while(q[i] < x);
do{
j--;
}while(q[j] > x);
if(i < j) {
swap(q[i],q[j]);
}
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
int main(){
scanf("%d", &n);
for (int i = 0; i < n; i ++){
scanf("%d", &q[i]);
}
quick_sort(q, 0, n-1);
for(int i = 0; i < n; i ++){
printf("%d ", q[i]);
}
}
Python版本
def quick_sort(data,l,r):
if(l >= r):
return
i = l - 1
j = r + 1
x = data[(l+r)//2]
while i<j:
while True:
i+=1
if data[i] >= x:
break
while True:
j-=1
if data[j] <= x:
break
if(i<j):
data[i],data[j] = data[j],data[i]
quick_sort(data,l,j)
quick_sort(data,j+1,r)
n = int(input())
data = list(map(int,input().split()))
quick_sort(data,0,n-1)
print(' '.join(list(map(str,data))))
1.2 第k个数
快速选择算法时间是O(n):选择从小到大第k个数
递归思想:
1. 找到分界点x (可以选q[L],q[R],q[(L+R)/2])
2. 左边所有数<=x 右边所有数>=x
3. 递归排序左边,递归排序右边
关于本题:由x分为Sl与Sr两部分
k<=Sl,只需要递归左半边;k>=Sl,只需要递归右半边,找k-Sl个数
所以只需要选择递归一边
n+n/2+n/4+...<2*n
C++版本
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n,k;
int q[N];
int quick_sort(int l, int r, int k){
if (l == r){
return q[l];
}
int x = q[l + r >> 1];
int i = l - 1, j = r + 1;
while(i < j){
while(q[++i] < x);
while(q[--j] > x);
if (i < j){
swap(q[i],q[j]);
}
}
int s1 = j - l + 1;
if(k <= s1){
return quick_sort(l,j,k);
}else{
return quick_sort(j+1,r,k-s1);
}
}
int main(){
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++ ){
scanf("%d", &q[i]);
}
cout<<quick_sort(0,n-1,k);
}
Python3版本
n,k = map(int,input().split())
data = list(map(int,input().split()))
def quick_sort(l,r,k):
if l == r:
return data[l]
x = data[(l + r)//2]
i = l - 1
j = r + 1
while(i < j):
while True:
i += 1
if data[i] >= x:
break
while True:
j -= 1
if data[j] <= x:
break
if i < j:
data[i],data[j] = data[j],data[i]
s1 = j - l + 1
if (k <= s1):
return quick_sort(l,j,k)
else:
return quick_sort(j+1,r,k-s1)
res = quick_sort(0,n-1,k)
print(res)
二. 归并排序
2.1 归并排序
1)确定分界点
2)递归排序left right
3)归并--合二为一(重点)
(双指针算法思想)
C++版本
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int tmp[N];
void merge_sort(int l, int r){
if (l >= r){
return ;
}
int mid = (l + r) >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1;
int k = 0;
while (i <= mid && j <= r){
if (q[i] <= q[j]){
tmp[k++] = q[i++];
}else {
tmp[k++] = q[j++];
}
}
while (i <= mid){
tmp[k++] = q[i++];
}
while (j <= r){
tmp[k++] = q[j++];
}
for (int i = l, j = 0; i <= r; i++){
q[i] = tmp[j++];
}
}
int main(){
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%d", &q[i]);
}
merge_sort(0, n-1);
for (int i = 0; i < n; i++){
printf("%d ", q[i]);
}
}
Python3版本
n = int(input())
data = list(map(int,input().split()))
tmp = [0]*n
def merge_sort(l, r):
if l >= r:
return
mid = (l + r)//2
merge_sort(l, mid)
merge_sort(mid+1, r)
i = l
j = mid+1
k = 0
while(i<=mid and j<=r):
if data[i]<=data[j]:
tmp[k] = data[i]
i+=1
else:
tmp[k] = data[j]
j+=1
k+=1
while(i<=mid):
tmp[k] = data[i]
i+=1
k+=1
while(j<=r):
tmp[k] = data[j]
j+=1
k+=1
m,n = l,0
while(m <= r):
data[m] = tmp[n]
m+=1
n+=1
merge_sort(0,n-1)
print(' '.join(list(map(str,data))))
2.2 逆序对的数量
逆序对的数量分为三部分
同在左侧,同在右侧,一左一右
前两情况递归返回后相加,需要单独处理第三种情况(在合并过程中处理)
q[i] > q[j]时,下标i之后的数都大于q[j]就是mid - i + 1
C++版本
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int q[N];
int tmp[N];
LL merge_func(int l, int r){
if (l >= r){
return 0;
}
int mid = (l + r) >> 1;
LL res = merge_func(l, mid) + merge_func(mid+1, r);
int i = l, j = mid + 1;
int k = 0;
while (i <= mid && j <= r){
if (q[i] <= q[j]){
tmp[k++] = q[i++];
}else{
tmp[k++] = q[j++];
res += (mid - i + 1);
}
}
while (i <= mid){
tmp[k++] = q[i++];
}
while (j <= r){
tmp[k++] = q[j++];
}
for (int i = l, j = 0; i <= r; i++){
q[i] = tmp[j++];
}
return res;
}
int main(){
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%d", &q[i]);
}
LL res = merge_func(0, n-1);
printf("%lld", res);
}
Python3版本
三. 二分算法
笔记见Leetcode刷题数组部分:
3.1 数的范围
C++
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int main(){
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++){
scanf("%d", &q[i]);
}
while (m--){
int x;
scanf("%d", &x);
int l = 0, r = n - 1;
while (l < r){
int mid = l + r >> 1;
if (q[mid] >= x){
r = mid;
}else{
l = mid + 1;
}
}
if (q[l] != x){
printf("-1 -1\n");
}else{
printf("%d ", l);
l = 0, r = n-1;
while (l < r){
int mid = l + r + 1 >> 1;
if (q[mid] <= x){
l = mid;
}else{
r = mid - 1;
}
}
printf("%d\n", l);
}
}
}
Python3
n, m = map(int, input().split())
data = list(map(int, input().split()))
for iter in range(m):
x = int(input())
l = 0
r = n - 1
while (l < r):
mid = l + r + 1 >> 1
if (data[mid] <= x):
l = mid
else:
r = mid - 1
if data[l] != x:
print('-1 -1')
else:
tmp = l
l = 0
r = n - 1
while (l < r):
mid = l + r >> 1
if (data[mid] >= x):
r = mid
else:
l = mid + 1
print(l, tmp)
3.2 数的三次方根
实数域上的二分要注意确定精度eps
r - l > eps
一般保留k位小数时,eps = 10^-(k+2)
C++
#include <iostream>
using namespace std;
int main(){
double x;
scanf("%lf", &x);
double l = -100, r = 100;
while (r - l > 1e-8){
double mid = (l + r) / 2;
if (mid * mid * mid >= x){
r = mid;
}else {
l = mid;
}
}
printf("%.6f",l);
}
Python3
x = float(input())
l = -100
r = 100
while (r - l > 1e-8):
mid = (l + r) / 2
if (mid * mid * mid >= x):
r = mid
else :
l = mid
print('%.6f'%l)
四. 高精度
4.1 高精度加法
C++
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B){
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || i < B.size(); i++){
if (i < A.size()){
t += A[i];
}
if (i < B.size()){
t += B[i];
}
C.push_back(t % 10);
t /= 10;
}
if (t){
C.push_back(1);
}
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 = add(A, B);
for (int i = C.size()-1; i >=0; i--){
printf("%d", C[i]);
}
}
Python3
a = list(map(int, input()))[::-1]
b = list(map(int, input()))[::-1]
t = 0
res = []
for i in range(0, max(len(a), len(b))):
if i < len(a):
t += a[i]
if i < len(b):
t += b[i]
res.append(t % 10)
t //= 10
if t:
res.append(1)
print(''.join(map(str, res[::-1])))
4.2 高精度减法
C++
//2022.6.23
#include <iostream>
#include <vector>
using namespace std;
//whether A >= B
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;
int num = 0;
for (int i = 0; i < A.size(); i++){
num = A[i] - t;
if (i < B.size()){
num -= B[i];
}
C.push_back((num + 10) % 10);
if (num >= 0){
t = 0;
}else {
t = 1;
}
}
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');
}
if (cmp(A, B)){
auto C = sub(A, B);
for (int i = C.size() - 1; i >= 0; i--){
printf("%d", C[i]);
}
}else {
printf("-");
auto C = sub(B, A);
for (int i = C.size() - 1; i >= 0; i--){
printf("%d", C[i]);
}
}
}
Python3
def cmp(a, b):
if len(a) != len(b):
return len(a) > len(b)
for i in range(len(a) - 1, -1, -1):
if (a[i] != b[i]):
return a[i] > b[i]
return True
def sub(a, b):
c = []
t = 0
for i in range(len(a)):
num = a[i] - t
if (i < len(b)):
num -= b[i]
c.append((num + 10) % 10)
if num >= 0:
t = 0
else :
t = 1
while (len (c) > 1 and c[-1] == 0):
c.pop()
return c
a = list(map(int, input()))[::-1]
b = list(map(int, input()))[::-1]
if cmp(a, b):
c = sub(a, b)
print(''.join(map(str, c[::-1])))
else:
c = sub(b, a)
print('-'+''.join(map(str, c[::-1])))
AcWing 793. 高精度乘法
类似于高精度加法
核心是进位t += A[i] * b (b看为一个整体)
4.3 高精度乘法
C++
#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;
}
while (t) {
C.push_back(t % 10);
t /= 10;
}
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');//先放低位
}
auto C = mul(A, b);
for (int i = C.size() - 1; i >= 0; i--) {
printf("%d", C[i]);
}
return 0;
}
python3
a = int(input())
b = int(input())
print(a * b)
a = input()
b = int(input())
def mul(a, b):
c = []
t = 0
for ele in a:
t += ele * b
c.append(t % 10)
t //= 10
while t :
c.append(t % 10)
t //= 10
while len(c) > 1 and c[-1] == 0 :
c.pop()
return c
a = list(map(int, a[::-1]))
c = mul(a, b)
c.reverse()
print(''.join(map(str, c)))
AcWing 794. 高精度除法
核心是:r = r * 10 + A[i] (需要从高位到低位)
4.4 高精度除法
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &A, int b, int &r) {
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i--) {
r = r * 10 + 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;
vector<int> A;
int b;
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i--) {
A.push_back(a[i] - '0');
}
int r;
auto C = div(A, b, r);
for (int i = C.size() - 1; i >= 0; i--) {
printf("%d", C[i]);
}
printf("\n");
printf("%d", r);
}
Python3
a = int(input())
b = int(input())
print(a // b)
print(a % b)
a = list(map(int, input()))
b = int(input())
def div(a, b):
c = []
r = 0
for ele in a:
r = r * 10 + ele
c.append(r // b)
r %= b
c.reverse()
while len(c) > 1 and c[-1] == 0:
c.pop()
return (c, r)
c, r = div(a, b)
print(''.join(map(str, c[::-1])))
print(r)
五. 前缀和差分
5.1 前缀和
C++
#include <iostream>
using namespace std;
const int N = 100010;
int s[N], a[N];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + a[i];
}
int l, r;
while (m--) {
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l - 1]);
}
}
Python3
n, m = map(int, input().split())
N = 100010
if __name__ == "__main__":
a = [0] + list(map(int, input().split()))
s = [0] * N
for i in range(1, n + 1):
s[i] = s[i - 1] + a[i]
while (m):
m -= 1
l, r = map(int, input().split())
print(s[r] - s[l - 1])
5.2 子矩阵的和
C++
#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], s[N][N];
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]);
}
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j++ ) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
}
int x1, x2, y1, y2;
while (q --) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
}
}
Python3
N = 1010
a = [[0] * N for _ in range(N)]
s = [[0] * N for _ in range(N)]
n, m, q = map(int, input().split())
for i in range(1, n + 1):
a[i] = [0] + list(map(int, input().split())) + a[m + 1 : ]
for i in range(1, n + 1):
for j in range(1, m + 1):
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]
while q :
q -= 1
x1, y1, x2, y2 = map(int, input().split())
print(s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1])
5.3 差分
C++
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];
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]);
}
for (int i = 1; i <= n; i ++ ) {
insert(i, i, a[i]);
}
int l, r, c;
while (m -- ) {
scanf("%d%d%d", &l, &r, &c);
insert(l, r, c);
}
for (int i = 1; i <= n; i ++ ) {
b[i] += b[i - 1];
}
for (int i = 1; i <= n; i ++ ) {
printf("%d ", b[i]);
}
}
Python3
N = 100010
b = [0] * N
a = [0] * N
def insert(l, r, c) :
b[l] += c
b[r + 1] -= c
if __name__ == "__main__" :
n, m = map(int, input().split())
a = [0] + list(map(int, input().split())) + a[n + 1 : ]
for i in range(1, n + 1) :
insert(i, i, a[i])
while (m) :
m -= 1
l, r, c = map(int, input().split())
insert(l, r, c)
for i in range(1, n + 1) :
b[i] += b[i - 1]
for i in range(1, n + 1) :
print(b[i], end = ' ')
5.4 差分矩阵
C++
#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c) {
b[x1][y1] += c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y1] -= 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]);
}
}
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
insert(i, j, i, j, a[i][j]);
}
}
int x1, y1, x2, y2, c;
while (q -- ) {
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];
}
}
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
printf("%d ", b[i][j]);
}
puts("");
}
}
Python3
N = 1010
a = [[0] * N for _ in range(N)]
b = [[0] * N for _ in range(N)]
if __name__ == "__main__" :
def insert(x1, y1, x2, y2, c) :
b[x1][y1] += c
b[x1][y2 + 1] -= c
b[x2 + 1][y1] -= c
b[x2 + 1][y2 + 1] += c
n, m, q = map(int, input().split())
for i in range(1, n + 1) :
a[i] = [0] + list(map(int, input().split())) + a[m + 1 : ]
for i in range(1, n + 1) :
for j in range(1, m + 1) :
insert(i, j, i, j, a[i][j])
while q :
q -= 1
x1, y1, x2, y2, c = map(int, input().split())
insert(x1, y1, x2, y2, c)
for i in range(1, n + 1) :
for j in range(1, m + 1) :
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]
for i in range(1, n + 1) :
for j in range(1, m + 1) :
print(b[i][j], end = ' ')
print()
六. 双指针算法
6.1 最长连续不重复子序列
C++
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], s[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) {
scanf("%d", &a[i]);
}
int res = 0;
for (int i = 0, j = 0; i < n; i ++ ) {
s[a[i]] ++ ;
while (s[a[i]] > 1) {
s[a[j]] -- ;
j ++ ;
}
res = max(res, i - j + 1);
}
printf("%d", res);
}
Python3
n = int(input())
a = list(map(int, input().split()))
s = dict.fromkeys(a, 0)
res = 0
j = 0
for i in range(n) :
s[a[i]] += 1
while s[a[i]] > 1 :
s[a[j]] -= 1
j += 1
res = max(res, i - j + 1)
print(res)
6.2 数组元素的目标和
C++
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];
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 (j >= 0 && a[i] + b[j] > x) {
j -- ;
}
if (a[i] + b[j] == x) {
printf("%d %d", i, j);
break;
}
}
}
Python3
n, m, x = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
j = m - 1
for i in range(n) :
while (j >= 0 and a[i] + b[j] > x) :
j -= 1
if (a[i] + b[j] == x) :
print(i, j)
break
6.3 判断子序列
C++
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];
int main() {
int m, n;
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) {
puts("Yes");
}else {
puts("No");
}
}
Python3
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
i, j = 0, 0
while i < n and j < m :
if a[i] == b[j] :
i += 1
j += 1
if i == n :
print("Yes")
else :
print("No")
七. 位运算
考虑原码与补码在计算机内存储的性质
找到二进制表示里最后的1,1之前的原码补码相反,1之后的原码补码一致;
7.1 二进制中1的个数
C++
#include <iostream>
using namespace std;
int lowbit(int x) {
return x & (-x);
}
int main() {
int n = 10;
scanf("%d", &n);
while (n -- ) {
int x;
scanf("%d", &x);
int res = 0;
while (x) {
x -= lowbit(x);
res ++ ;
}
printf("%d ", res);
}
}
// lowbit(x) 树状数组的基本操作 统计1的个数
//(返回x的最后一位1到末尾的二进制)
// 实现 : x & (-x)
Python3
n = int(input())
a = list(map(int, input().split()))
def lowbit(x) :
return x & (-x)
for i in range(n) :
x = a[i]
res = 0
while x :
x -= lowbit(x)
res += 1
print(res, end = ' ')
八. 离散化
有时候需要把一些凌乱的数,通过大小关系放入特定数组;
8.1 区间和
C++
//去重 需要将所有值排序,然后去重复元素
//二分找出x对应的离散化的值
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;
//映射到从1开始,成为前缀和
int find(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 r + 1;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) {
int x, c;
scanf("%d%d", &x, &c);
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; i ++ ) {
int l, r;
scanf("%d%d", &l, &r);
query.push_back({l, r});
alls.push_back(l);
alls.push_back(r);
}
//去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (auto item : add) {
int x = find(item.first);
a[x] += item.second;
}
//预处理前缀和
for (int i = 1; i <= alls.size(); i ++ ) {
s[i] = s[i - 1] + a[i];
}
//处理询问
for (auto item : query) {
int l = find(item.first);
int r = find(item.second);
printf("%d\n", s[r] - s[l - 1]);
}
}。
Python3
n, m = map(int, input().split())
addNum = [] #存放+操作
query = [] #存放询问操作
alls = [] #存放离散的元素
def find(x) :
l, r = 0, len(alls) - 1
while l < r :
mid = l + r >> 1
if (alls[mid] >= x) :
r = mid
else :
l = mid + 1
return r + 1
for i in range(n) :
x, c = map(int, input().split())
addNum.append([x, c])
alls.append(x)
for i in range(m) :
l, r = map(int, input().split())
query.append([l, r])
alls.append(l)
alls.append(r)
# 去重操作
alls.sort()
alls = list(set(alls))
nums = [0] * (len(alls) + 10)
s = [0] * (len(alls) + 10)
for (x, c) in addNum :
nums[find(x)] += c
#预处理前缀和
for i in range(1, len(alls) + 1) :
s[i] = s[i - 1] + nums[i]
#处理询问
for (l, r) in query :
l, r = find(l), find(r)
print(s[r] - s[l - 1])
九. 区间合并
9.1 区间合并
需要对两个区间的端点进行讨论
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
vector<PII> part;
bool cmp(const PII &a, const PII &b) {
if (a.first != b.first) {
return a.first < b.first;
}
return a.second > b.second;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) {
int l, r;
scanf("%d%d", &l, &r);
part.push_back({l, r});
}
sort(part.begin(), part.end(), cmp);
int st = part[0].first;
int ed = part[0].second;
int num = 1;
for (int i = 1; i < part.size(); i ++ ) {
if (part[i].second <= ed) {
continue;
}
if (part[i].first <= ed && part[i].second > ed) {
ed = part[i].second;
}
if (part[i].first > ed) {
num ++ ;
st = part[i].first;
ed = part[i].second;
}
}
printf("%d", num);
}
Python3
n = int(input())
arr = []
for i in range(n) :
l, r = map(int, input().split())
arr.append([l, r])
arr.sort(key=lambda x : x[0])
st = arr[0][0]
ed = arr[0][1]
num = 1
for i in range(1, n) :
if arr[i][1] <= ed :
continue
if arr[i][0] <= ed and arr[i][1] > ed :
ed = arr[i][1]
if arr[i][0] > ed :
num += 1
st = arr[i][0]
ed = arr[i][1]
print(num)