近日状态并不是很好， 很不稳， 思路也不是很清晰
希望自己能走出来
题意：有序列1~n 现给出两种区间
区间0：序号在[x, y]的节点不能有忍者
区间1：序号在[x, y]的节点区间里至少有一个忍者
如果有一个区间1和区间0矛盾了 保留那个区间0
已知共有k个忍者 求问一定有忍者的位置有哪些 没有的话 输出-1
A
是不是想到了一个经典问题？
——对于所有区间的最小点覆盖
【悄咪咪：解决方法
以左端点为第一关键字 右端点为第二关键字不下降排序区间
贪心每次不能覆盖的区间的最右端点】
B
但是有区间0啊 不能用这种方法了qvq
然鹅 把区间0覆盖的区间踢掉就可以了（以下“序列”都是指处理完的
差分就可以统计
C
去掉不能有忍者的区间后
我们需要找必须有忍者的区间
先考虑特殊情况
对于该序列 如果不删掉任何忍者 跑一遍最小点覆盖
如果答案大于k 那么必然无解
如果该序列长度为k 那么都要取了
D
一个点必须取 == 不取该点就是无解
蒟蒻认为这是这道题的思维精髓
现在可以很轻松地打出50分暴力了
E
考虑数据结构优化
可以使用线段树或差分
当然我这么懒用的是差分
在代码注释中体现了
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <bitset>
#include <queue>
using namespace std;
const int N = (int)1e5 + 5;
int n, k, m;
struct Q{
int x, y, z;
}q[N];
int qsize;
int dif[N];
int lef[N], rig[N], cnt, ref[N];
//lef[i]记录的是去掉区间0编号后 离散化
//不小于位置i的最小的可以放忍者的位置
//用于把原区间1转换为处理后序列中的区间
//rig[i]反之
int lline[N], rline[N], top;
//处理后序列中各区间左右端点位置
int lf[N], rf[N];
//lf[i]从左边开始覆盖到第i个区间需要的最小节点数
inline bool rule(Q x, Q y){
return x.x == y.x ? x.y < y.y : x.x < y.x;
}
int main(){
scanf("%d%d%d", &n, &k, &m);
for(int i = 1; i <= m; ++i){
scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].z);
if(!q[i].z){++dif[q[i].x]; --dif[q[i].y + 1];}
}
for(int i = 1, cur = 0; i <= n; ++i){
cur += dif[i];
if(!cur){
lef[i] = rig[i] = ++cnt;
ref[cnt] = i;
}
}
if(cnt == k){
for(int i = 1; i <= cnt; ++i) printf("%d\n", ref[i]);
return 0;
}
lef[n + 1] = n + 1;
for(int i = 1; i <= n; ++i) if(!rig[i]) rig[i] = rig[i - 1];
for(int i = n; i >= 1; --i) if(!lef[i]) lef[i] = lef[i + 1];
//处理序列 去掉区间0
qsize = 0;
for(int i = 1, x, y; i <= m; ++i){
if(!q[i].z) continue;
x = lef[q[i].x], y = rig[q[i].y];
if(x <= y) q[++qsize] = (Q){x, y, 1};
}
sort(q + 1, q + qsize + 1, rule);
//处理区间
m = qsize; n = cnt;
for(int i = 1; i <= m; ++i){
while(top && lline[top] <= q[i].x && rline[top] >= q[i].y) --top;
lline[++top] = q[i].x; rline[top] = q[i].y;
}
for(int i = 1, d = 0; i <= m; ++i){
if(lline[i] > d) d = rline[i], lf[i] = lf[i - 1] + 1;
else lf[i] = lf[i - 1];
}
for(int i = m, d = n + 1; i >= 1; --i){
if(rline[i] < d) d = lline[i], rf[i] = rf[i + 1] + 1;
else rf[i] = rf[i + 1];
}
//处理lf rf 注意其下标为区间编号
bool suc = 0;
lline[m + 1] = n + 1;
for(int i = 1, l, r, mid, x, y, del; i <= m; ++i){
del = rline[i];
if(lf[i] == lf[i - 1]) continue;
if(lline[i] == del) {
suc = 1; printf("%d\n", ref[del]); continue;
}
l = 0, r = i - 1;
while(l < r){
mid = l + ((r - l + 1) >> 1);
if(rline[mid] < lline[i]) l = mid;
else r = mid - 1;
}
x = l;
l = i + 1, r = m + 1;
while(l < r){
mid = l + ((r - l) >> 1);
if(lline[mid] > rline[i]) r = mid;
else l = mid + 1;
}
y = l;
if(lf[x] + rf[y] + 1 > k){
suc = 1; printf("%d\n", ref[del]); suc = 1;
}
}
if(!suc) printf("-1\n");
return 0;
}