P4155 [SCOI2015] 国旗计划

P4155 [SCOI2015] 国旗计划

---

思路： 

一开始，我对这题一点思路都没有，只知道这是环，要拆环成链。

然后看了题解，才发现要先排序（要记录此人的位置），我才发现这句话：

每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含。这句话包含两个信息：

1.战士与战士左边和右边的站点一定不相同（l1!=l2）&&(r1!=r2)（如果相同，必有一个战士被包含，错误❌）

2.排完序之后他的区间只能为以下三种：

   

第三种因为 数据保证整个边境线都是可被覆盖的。pass❌

然后我就发现他每选一人的最优解，是距此站点右端点最近的左站点人。

到这里就应该有纯暴力的思路了：每个战士从自己的位置开始遍历，直到右站点的值>此战士左端点的值+m(总站点)结束，但这种情况的时间复杂度为O(n^2)。超限

从这我才想到用刚学的ST表。这个ST表我还是看题解才知道怎么写（还是太拉了）。

这个题解的精妙之处在于，它a[][0]记录的是最优操作的坐标，这样它在查询时，k个人之后的右站点的值<此战士左端点的值+m,他的点可以持续跟进。（不理解的可以先看代码，我表达的不是很清楚）

查询的思路就是从最大的区间遍历，满足它在查询时，满足右站点的值<此战士左端点的值+m，ans+=倍增的人数，右站点的值>此战士左端点的值+m时，ans不变，继续遍历。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
# define MAX0 18+1
int a[400006][MAX0];//ST表
//int Log[400006];
int n, m,nn;
struct ss {int i;//起始人，方便最后打印int l, r;//l不可能相等，否则必有一个被包围，不符合条件
}b[400005];//n的2倍（化环成链）
int c[200006];
int max0 = 0;//最多有多少行//ST表初始化
void ChuST() {int post = 1;//post战士左端点的值递增，右站点的值也递增，所以post可以持续递增for (int i = 1; i <= 2 * n; i++) {while (post<=2*n&&b[post].l <= b[i].r) {//post战士左端点的值>直到右站点的值结束post++;}a[i][0] = post - 1; //a[][0]记录的是最优操作的坐标}for (int i = 1; (1<<i) <=n; i++) {max0++;                         //计算最多有多少行for (int j = 1; j  <= 2*n; j++) {a[j][i] = a[a[j][i-1]][i - 1];//（不太会解释）此站点的(1<<i-1)个战士的最优解的战士(1<<i-1)的解}}
}
//查询操作（我没能力表达不太好表达原因，看不懂的用笔画出一个例子的如下遍历过程理解理解）
void FuZhi(int w) {int r = b[w].r+m;int ans = 0; int jj = w;for (int j = max0; j >= 0; j--) {if (b[a[jj][j]].r < r) {jj = a[jj][j];ans += 1 << j;}}c[b[w].i] = ans + 1;//保证位置正确
}
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定int j = 0;int p = 1;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> b[i].l >> b[i].r;if (b[i].r < b[i].l) {b[i].r += m;//小于时+m}b[i].i = i;}sort(b + 1, b + n + 1, [](const ss aa, const ss bb) {return aa.l < bb.l;});//排序//化环成链，保证超过m(及b[i].r < b[i].l可以向后遍历)nn = n;for (int i = 1; i <= n; i++) {nn++;b[nn].i = b[i].i;b[nn].l = b[i].l + m;b[nn].r = b[i].r + m;}ChuST();for (int i = 1; i <= n; i++) {FuZhi(i);}for (int i = 1; i <= n; i++) {cout << c[i] << " ";}cout<<endl;return 0;
}