目录

Acwing算法基础课第一讲总结

快速排序

Acwing-785 快速排序

原题链接

思路
快速排序模板题。
这道题在取分界点时需要取中点,避免部分因为取左右边界点,使得快排复杂度退化为$O(n^2)$而超时的情况。
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1e6+10;
int q[maxn];
int n;

void quick_sort(int q[], int l, int r)
{
    if(l >= r) return ;
    
    int x = q[(l+r)/2], i = l - 1, j = r + 1;
    
    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(void)
{
    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]);

    return 0;
}

Acwing-786 第k个数

原题链接

思路
快速选择模板题。
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1e6+10;
int q[maxn];

int quick_sort(int q[], int l, int r, int k)
{
    if(l == r) return q[l];	//第k大的数所在的区间只有一个数,那么这个数就是整个区间第k大的数

    int x = q[(l+r) / 2], i = l - 1, j = r + 1;

    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }

    //如果在左半区间,由于子区间已经有序,那么整个区间第k大的数就在这个区间的前k个元素中
	//反之,在右半区间的位次就是整个区间第k大的数的位置减去左半区间的元素个数
	if(j-l+1 >= k) quick_sort(q, l, j, k);
    else quick_sort(q, j+1, r, k - (j-l+1));
}

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

归并排序

Acwing-787 归并排序

原题链接

思路
归并排序模板题。
参考代码
#include <cstdio>

const int maxn = 1e6 + 10;
int m[maxn], tmp[maxn];

void merge_sort(int m[], int l, int r)
{
    if(l == r) return ;

    int mid = (l + r) / 2;

    merge_sort(m, l, mid);
    merge_sort(m, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(m[i] < m[j]) tmp[k++] = m[i++];
        else tmp[k++] = m[j++];
    }

    while(i <= mid) tmp[k++] = m[i++];
    while(j <= r) tmp[k++] = m[j++];

    for(i = l, j = 0; i <= r; i++, j++) m[i] = tmp[j];

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

Acwing-788 逆序对的数量

原题链接

思路
利用归并排序中的比较过程来统计逆序对。代码中 res += mid - i + 1 是计算逆序对的,由于归并排序是合并两有序的子区间,这里是升序排列,所以一旦左子区间下标为i的数大于了右子区间下标为j的数,那么左子区间下标imid的数都大于右子区间坐标为j的数,即有mid-i+1个数都能与右子区间下标为j的数构成逆序对。

参考代码
#include <cstdio>

const int maxn = 100010;
int a[maxn];
long long res;

void merge_sort(int m[], int l, int r)
{
    if(l >= r) return ;

    int mid = (l + r) / 2;
    merge_sort(m, l, mid);
    merge_sort(m, mid + 1, r);

    int k = 0, i = l, j = mid + 1, tmp[r-l+1];
    while(i <= mid && j <= r)
    {
        if(m[i] <= m[j]) tmp[k++] = m[i++];
        else
        {
            tmp[k++] = m[j++];
            res += mid - i + 1;
        }
    }
    while(i <= mid) tmp[k++] = m[i++];
    while(j <= r) tmp[k++] = m[j++];

    for(i = l, k = 0; i <= r; i++, k++)
        m[i] = tmp[k];

}
int main(void)
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    merge_sort(a, 0, n - 1);
    printf("%lld\n", res);
    return 0;
}

二分

Acwing-789 数的范围

原题链接

思路
整数二分的两种写法,在升序情况下,右逼近答案的写法是返回不小于该数的第一个位置,左逼近答案的情况下是返回不大于该数的最后一个位置。

参考代码
#include <iostream>
using namespace std;

const int maxn = 1e5+10;
int n, q, k, a[maxn];

int binary_search_st(int k)
{
	int l = 0, r = n - 1;
	while(l < r)
	{
		int mid = (l+r)/2;
		if(a[mid] >= k) r = mid;
		else l = mid + 1;
	}

	return l;
}

int binary_search_ed(int k)
{
	int l = 0, r = n - 1;
	while(l < r)
	{
		int mid = (l+r+1)/2;
		if(a[mid] <= k) l = mid;
		else r = mid - 1;
	}
	
	return l;
}

int main(void)
{
	cin >> n >> q;
	for(int i = 0; i < n; i++) cin >> a[i];

	while(q--)
	{
		cin >> k;
		int st = binary_search_st(k), ed = binary_search_ed(k);
		if(a[st] != k)
		{
			cout << "-1 -1" << endl;
		}
		else
		{
			cout << st << ' ' << ed << endl;
		}
	}

	return 0;
}

Acwing-790 数的三次方根

原题链接

思路
浮点数二分,注意精度一要般比题目要求的再多精确两位,减小误差。

参考代码
#include <cstdio>
#include <cmath>
using namespace std;

const double eps = 1e-8;
double n;

bool check(double mid)
{
	mid = pow(mid, 3);

	return mid < n;
}

int main(void)
{
	scanf("%lf", &n);

	double l = -1e4, r = 1e4;
	while(r - l > eps)
	{
		double mid = (l+r)/2;
		if(check(mid)) l = mid;
		else r = mid;
	}

	printf("%f\n", l);

	return 0;
}

高精度

Acwing-791 高精度加法

原题链接

思路
首先注意,大整数的储存是逆序储存在数组中的(即最低位个位储存在最前,最高位储存在最后)。这么做的原因是,在进行加法减法时,方便在进位时添加数字,若顺序储存,就会在每次在进位时都要移动后面的数字,比较麻烦。

参考代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
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++)
    {
        //加完A和B各位上的数字
        if(i < A.size()) t += A[i];
        if(i < B.size()) t += B[i];

        C.push_back(t % 10);    //加上t%10的结果
        t /= 10;    //若有进位,则加到下一位中
    }
    
    //若进位到了最高位,增添一位数字,同时也避免了前导0
    if(t) C.push_back(t);   
    
    return C;
}

int main(void)
{
	string a, b;
	vector<int> A, B;
	cin >> 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]);
	return 0;
}

Acwing-792 高精度减法

原题链接

思路
这里的做法针对非负数的高精度减法,且满足A>=B。所以需要单独写一个比较函数来保证A>=B
参考代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
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;
    //t用于储存借位
    for(int i = 0, t = 0; i < A.size(); i++)
    {
        //第0位没有借位,初始化为0,然后每一位先判断是否有借位,再相减
        t = A[i] - t;
        if(i < B.size()) t -= B[i];

        /*此处判断包含了两种情况:
        若t为负数,则该位加进去的数字是两位数字借位并相减后的结果
        反之,则加进去的是两位数字相减后的结果
        */        
        C.push_back((t+10) % 10);

        //判断是否借位,t小于0即发生借位
        if(t < 0) t = 1;
        else t = 0;
    }

    //消除前导0
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main(void)
{
	string a, b;
	vector<int> A, B;
	cin >> 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 
	{
		auto C = sub(B, A);
		printf("-");
		for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);	
	}		
	
	return 0;
}

Acwing-793 高精度乘法

原题链接

思路
这里的写法针对于,高精度乘以低精度,且满足大整数A>=0小整数b>0
参考代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;  //和加法的t类似的作用

    //循环条件这么写,是包括了到了最高位还有进位的情况
    for(int i = 0; i < A.size() || t; i++)
    {
        //再判断一次i是否越界,防止只有t成立时,循环中的i<A.size()条件会失效
        if(i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    //同减法的消除前导0的方式
    while(C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

int main(void)
{
	vector<int> A;
	string a;
	int b;
	cin >> a >> b;
	
	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;
}

Acwing-794 高精度除法

原题链接

思路
该写法针对于高精度除以低精度,且满足大整数A>=0小整数b>0

参考代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

//r存储余数,可以定义为全局变量。也可以在主函数中定义,在这里使用引用
vector<int> divi(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;  //r用来存储每次商的时候的余数
    for(int i = A.size() - 1; i >= 0; i--)
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    //由于push_back函数是存数存到末尾,商是反着存的,为了便于输出,先反转一下
    reverse(C.begin(), C.end());

    //消除前导0,同减法
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

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

前缀和与差分

Acwing-795 前缀和

原题链接

思路
一维前缀和,记住公式即可。记 $s[]$ 为前缀和数组,需要求前缀和的数组为 $a[]$ ,那么有公式 $s[i] = a[i] + s[i-1]$ 为了计算方便,避免边界问题,$s[]$ 和 $a[]$ 都以下标1开始。
参考代码
#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 1e6+10;
int a[maxn], s[maxn];	

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

Acwing-796 子矩阵的和

原题链接

思路

二维前缀和。记住公式即可:

  1. (类比一维前缀和)得到坐标为(i,j)为右下角的点矩阵的前缀和 $s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]$
  2. 求某子矩阵 左上角点的坐标(x1,y1)右下角点的坐标(x2,y2) 的前缀和 $s[x_2][y_2] - s[x_1-1][y_2] - s[x_2][y_1-1] + s[x_1 - 1][y_1 -1]$
    若记不清楚公式了可以手工模拟,画一个4×4的矩阵即可,注意数据是离散的,点的下标是从(1,1)开始,并且注意二维数组中一维是行,二维是列。为了计算方便,下标从1开始。
参考代码
#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 1010;
int a[maxn][maxn], s[maxn][maxn];	

int main(void)
{
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			scanf("%d", &a[i][j]) ;
			s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
		}
	}
	
	int x1, y1, x2, y2;
	for(int i = 0; i < q; i++)
	{
		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]);
	}
	
	return 0;
}

Acwing-797 差分

原题链接

思路
一维差分。不需要记住如何构造的,核心是insert函数。记住公式(记 $b[]$ 为差分数组): $b[l] += c; b[r+1] -= c$ (给区间[l, r]的每个数加上c)
参考代码
#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 1e6 + 10;
int a[maxn], b[maxn];

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

int main(void)
{
	int n, m;
	cin >> n >> m;

	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		insert(i, i, a[i]);
	}

	int l, r, c;
	
	for(int i = 1; i <= m; i++)
	{
		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 差分矩阵

原题链接

思路
记住公式即可,(类比一维差分)得到(i,j)为右下角坐标的矩阵的差(详见下列代码中的insert函数)。
参考代码
#include <iostream>
#include <cstdio>
using namespace std;

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

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(void)
{
	int n, m, q;
	cin >> 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]);
		}
	}
	
	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] + b[i][j];
			printf("%d ", b[i][j]);
		}
		puts("");
	}

	return 0;
}

双指针

Acwing-799 最长连续不重复子序列

原题链接

思路
指针j在前,指针i在后,通过cnt数组来统计每个数字是否有重复出现。
每次移动i时,相当于序列中新加入了一个数字,此时cnt数组中下标为该数字的元素加一,若序列这个位置的元素大于1,则说明出现了重复元素,此时开始移动指针j,这个操作相当于把序列中一个已有的数字移出去,那么cnt数组中下标对应的元素会减一,不断移动指针j,使得序列中每个数字对应的cnt数组中的元素的值都为1,即为没有重复的元素。
参考代码
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;
const int maxn = 1e6+10;
int a[maxn], cnt[maxn];

int main(void)
{
	int n;
	cin >> n;
	
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	
	int res = 0;
	for(int i = 0, j = 0; i < n; i++)
	{
		cnt[a[i]]++;
		
		while(cnt[a[i]] > 1)
		{
			cnt[a[j]]--;
			j++;
		}
		
		res = max(res, i - j + 1);
	}
	
	cout << res << endl;
	return 0;
}

Acwing-800 数组元素的目标和

原题链接

思路
这道题根据题意灵活处理了指针的起始位置,这道题两个数组都为升序,所以两指针分别指向两数组的头元素和尾元素。设指针i指向数组A[]的第一个元素,指针j指向数组B[]的最后一个元素,只要有A[i]+B[j] > x就往前移动指针j,否则往后移动指针i,直到有A[i]+b[j]=x为止。这里利用了A[i]+B[j]>x的单调性。

参考代码
#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 1e6+10;
int a[maxn], b[maxn];

int main(void)
{
	int n, m, x;
	cin >> 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]);
	
	int i, j;	//i和j只要指向的分别是头元素和尾元素都可以
	for(i = 0, j = m - 1; i < n; i++)
	{
		while(j >= 0 && a[i] + b[j] > x) j--;
		if(a[i] + b[j] == x) break;
	}
	
	cout << i << ' ' << j << endl;
	
	return 0;
}

Acwing-2816 判断子序列

原题链接

思路
这道题也是双指针的思路,重要的是搞清楚这道题具体的问题逻辑。指针i遍历较长序列b,j遍历较短序列a,当a[j]=b[i]时,j向右移动一位,若最后有j==n,则说明b是a的子序列。
j只能和i同方向移动,这就是这道题的“单调性”。
参考代码
#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 1e6+10;
int a[maxn], b[maxn];

int main(void)
{
	int n, m;
	cin >> 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, j;
	for(i = 0, j = 0; i < m; i++)
	{
		while(j < n && a[j] == b[i]) 
		{
		    j++;
		    i++;
		}
		if(j == n) break;		
	}
	
	if(j == n) cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
}

位运算

Acwing-801 二进制中1的个数

原题链接

思路
常用的两个模板: 求n的二进制表示的第k位数字:n >> k & 1
返回n的最后一位1:lowbit(n) = n & - n
参考代码
#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 1e6 + 10;
int a[maxn];

int lowbit(int x)
{
	return x & -x;
}

int main(void)
{
	int n;
	cin >> n;

	for(int i = 0; i < n; i++) scanf("%d", &a[i]);

	for(int i = 0; i < n; i++)
	{
		int res = 0;
		while(a[i])
		{
			a[i] -= lowbit(a[i]);
			res++;
		}
		cout << res << ' ';
	}

	return 0;
}

离散化

Acwing-802 区间和

原题链接

思路
离散化主要用来处理数据范围跨度很大,但数据分布比较稀疏的情况。 离散化中,用二分法来把数据映射到一个数组中。映射之前,需要先排序,去重。其中,排序是必要的,去重可以不用有这一步操作,但是有这一步可以提高离散化的效率。
参考代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*数组大小为3e5的原因
需要离散化的数据个数不超过1e5个,而且中,不仅需要操作的位置需要映射
询问时的区间边界也需要映射,所以x,l,r共有3种需要映射的数据,即为3*1e5 
*/
const int maxn = 3e5+10;
typedef pair<int,int> PII;
int a[maxn], s[maxn];
vector<int> alls;   //存储所有待离散化的值
vector<PII> add, query;

//二分求出x对应的离散化的值,找第一个大于等于x的位置
int find(int x) 
{
	int l = 0, r = alls.size() - 1;
	
	while(l < r)
	{
		int mid = (l+r)/2;
		if(alls[mid] >= x) r = mid;
		else l = mid + 1;
	}
	
    // 映射到1, 2, ...n。这里可以根据题目需要映射到0, 1, ...n,映射下标从1开始是为了方便前缀和等操作的处理 
	return l + 1;	
    
}

int main(void)
{
	int n, m;
	cin >> n >> m;
	
	//读入数据,并把需要离散化的数据加入到容器alls中 
	int x, c;
	for(int i = 0; i < n; i++)
	{
		cin >> x >> c;
		add.push_back({x, c});
		
		alls.push_back(x);
	}
	
	int l, r;
	for(int i = 0; i < m; i++)
	{
		cin >> 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());
	
	//对去重后的数据进行离散化操作,注意映射的下标从1开始,方便后面前缀和的预处理 
	for(auto item : add)
	{
		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), r = find(item.second);
		cout << s[r] - s[l-1] << endl;
	}
	
	return 0;
}

区间合并

Acwing-803 区间合并

原题链接

思路

通过手工模拟即可知道,区间合并有三种情况,包含,有交集或者没交集。对归并排序稍加修改即可处理这三种操作。

  1. 包含则继续遍历,无需合并,保留更宽的区间即可。
  2. 有交集则取并集合并。
  3. 没有交集则不需要合并,直接加入合并后的数组即可。
参考代码
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
void merge(vector<PII> &segs)
{
    vector<PII> res; //存放合并结果
    
    sort(segs.begin(), segs.end()); //先排序再进行遍历合并

    int st = -2e9, ed = -2e9;   //视具体题目数据范围而定
    for(auto seg : segs)
    {
        if(ed < seg.first)
        {
            //若前面已经有区间的左端点,则该区间已经合并完毕
            if(st != -2e9) res.push_back({st, ed}); 
            //存储当前区间端点信息,继续遍历合并
            st = seg.first;
            ed = seg.second;
        }
        else
        {
            //若ed大于或等于seg.first,则说明有交集,此时取合并并集
            ed = max(ed, seg.second);
        }
    }

    //特判segs里面没有需要合并的区间的情况
    if(st != -2e9)  res.push_back({st, ed});

    segs = res;
}

int main(void)
{
    int n;
    scanf("%d", &n);

    int l, r;
    vector<PII> segs;

    for(int i = 0; i < n; i++) 
    {
        scanf("%d %d", &l, &r);
        segs.push_back({l,r});
    }

    merge(segs);
    printf("%d\n", segs.size());

    return 0;
}