P2782 友好城市题解

题目传送门

题意：给定一些上下的线段，求出最多不相交的线段数量。

一开始看错题了，以为是给定一堆线段，求出线段最大不交数量，然后就写了一个树状数组优化\(dp\)结果样例都不过，才发现自己看错题了。

在草稿纸上画了画，发现排序后答案就是 \(LIS\) 的长度，但是不想重新去写二分了，就用树状数组写了个 \(LIS\) ，个人觉得树状数组/线段树优化的 \(LIS\) 比二分好理解些？

code

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
using namespace std;
typedef long long ll;
typedef long long ull;
const int N = 2e5 + 5, M = 1e6 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

int n, mx;
int tr[M];
int f[N];
struct seg
{
	int l, r;
}a[N];

bool cmp(seg a, seg b)
{
	if(a.r == b.r) return a.l < b.l;
	return a.r < b.r;
}

void add(int x, int val)
{
	while(x <= mx)
	{
		tr[x] = max(tr[x], val);
		x += lowbit(x);
	}
}

int query(int x)
{
	int res = 0;
	while(x > 0)
	{
		res = max(res, tr[x]);
		x -= lowbit(x);
	}
	return res;
}

int main()              //主函数
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for(int i = 1;i <= n;i ++)
		cin >> a[i].l >> a[i].r, mx = max(mx, a[i].r);
	sort(a + 1, a + 1 + n, cmp);
	int res = 0;
	for(int i = 1;i <= n;i ++)
	{
		f[i] = query(a[i].l) + 1;
		add(a[i].l, f[i]);
		res = max(res, f[i]);
	}
	cout << res << '\n';
    return 0;
}