Luogu P4155 [SCOI2015]国旗计划 题解

题目链接：Luogu P4155 [SCOI2015]国旗计划

---

T5 - Luogu 4155 [SCOI2015] 国旗计划 题解

第7组

题目大意

选出尽量少的区间完全覆盖一个环，输出每个区间强制选的答案，\(n\leq 2\times10^5,M\leq 10^9\).

题解

1. 把所有战士从 \([1,m]\) 复制到 \([1,2m]\)，对应端点加 \(m\)，把 \(n\) 个节点都复制一遍.
2. 由于区间不包含，则我们可以把所有区间按左端点排序，则右端点也会同时有序增加，此时可以利用双指针 \(O(n)\) 得到每个区间 \(i\) 的范围 \([l_i,r_i]\) 内，之后的区间中左端点 \(\leq r_i\) 的最靠右的区间 \(j\)，利用该区间贪心取尽量长的覆盖长度，设为 \(\text{nxt}[i] =j\).
3. 倍增法：构造数组 \(f[i][j]\) 表示从 \(i\) 开始，利用刚才的 \(\text{nxt}\) 关系向后跳 \(2^j\) 步，所达到的区间编号.
4. 利用数组 \(f[i][j]\) 倍增快速跳到刚好不能覆盖环长 \(m\) 的最右编号，之后再跳一次即可将环完全覆盖. 记录倍增时跳过的 \(2^k\) 累加为答案，并加上该区间自己.

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2 * (2e5 + 5);

template <typename _Tp>
void read(_Tp &a, char c = 0) {
	for (c = getchar(); !isdigit(c); c = getchar());
	for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int n, m, _n, _m;

class seg {
  public:
	int l, r, nxt, id;
	seg() {}
	seg(int _l, int _r, int _id) {
		l = _l;
		r = _r;
		nxt = -1;
		id = _id;
	}
	void print() {
		printf("[%d, %d] -> %d\n", l, r, nxt);
	}
	bool operator < (const seg &o) const {
		return l < o.l;
	}
	~seg() {}
};

seg a[N];

int f[N][20], pz[N];

void print() {
	for (int i = 1; i <= n; i++) {
		a[i].print();
	}
}

#define DEBUG

int main() {
	// freopen("t5.in", "r", stdin);
	read(n), read(m);
	_n = n * 2;
	_m = m * 2;
	for (int i = 1; i <= n; i++) {
		int l, r;
		read(l), read(r);
		if (r < l) r += m;
		a[i] = seg(l, r, i);
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		a[i + n] = a[i];
		a[i + n].l = a[i].l + m;
		a[i + n].r = a[i].r + m;
	}
	int p1 = 1, p2 = 1;
	while (p1 <= _n) {
		int cr = a[p1].r;
		while (a[p2].l <= cr && p2 <= _n) {
			p2++;
		}
		a[p1].nxt = p2 - 1;
		f[p1][0] = p2 - 1;
		p1++;
	}
	for (int j = 1; j < 20; j++) {
		for (int i = 1; i <= _n; i++) {
			f[i][j] = f[f[i][j - 1]][j - 1];
		}
	}
	for (int i = 1; i <= n; i++) {
		seg &u = a[i], v = a[i];
		int p = i;
		int ans = 1;
		for (int j = 19; j >= 0; j--) {
			int to = f[p][j];
			if (to) {
				v = a[to];
				if (v.r < u.l + m) {
					p = to;
					ans += 1 << j;
				}
			}
		}
		pz[a[i].id] = ans + 1;
	}
	for (int i = 1; i <= n; i++) {
		printf("%d ", pz[i]);
	}
	puts("");
	return 0;
}