时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
𝑅𝑒𝑘𝑖在课余会接受一些民间的鹰眼类委托，即远距离的狙击监视防卫。
𝑅𝑒𝑘𝑖一共接到了𝑚份委托，这些委托与𝑛个直线排布的监视点相关。 第𝑖份委托的内容为：对于区间[𝑙𝑖,
𝑟𝑖]中的监视点，至少要防卫其中的𝑘𝑖个。 𝑅𝑒𝑘𝑖必须完成全部委托，并且希望选取尽量少的监视点来防卫。
输入描述:
第一行，两个正整数𝑛，𝑚。
接下来𝑚行，每行三个整数𝑙𝑖，𝑟𝑖，𝑘𝑖。
输出描述:
一行，一个整数，即所需防卫的最少监视点数量。
示例1
输入
复制
11 5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
输出
复制
6
备注:
对于10%的数据，𝑛 ≤ 10。
对于20%的数据，𝑛 ≤ 20。
对于30%的数据，𝑛,𝑚 ≤ 30。
对于60%的数据，𝑛,𝑚 ≤ 1000。
对于100%的数据，𝑛 ≤ 500000，𝑚 ≤ 1000000，𝑙𝑖 ≤ 𝑟𝑖，𝑘𝑖 ≤ 𝑟𝑖−𝑙𝑖+1。
题解：
贪心+线段树
我们先将给的m个区间进行排序，按照右端点值从小到大排
然后对每个区间值查询监视点的数量，如果不满足要求就填充，记得要尽可能的给区间的右侧填充，因为这样更有利于后面的区间能用上
比如[1,3]和[3,6]，两个区间各需要一个监视点，我们我们给[1,3]按上一个，尽可能在右侧安装，也就是点3，这样查询[3,6]时我们发现已经有了，就不用给[3,6]再安装了
区间修改操作涉及到了线段树
那在线段树区间修改的时候，怎么能先优先更新右侧？
很简单，我们在更新是优先更新右节点
if(r>mid)
val=update(id*2+1,mid+1,R,l,r,val);
if(l<=mid)
val=update(id*2,L,mid,l,r,val);
代码中是先更新id*2+1即右节点，这样就会优先在右侧填充，如果两个语句反过来，就是优先填充左侧
有两种写法（一种用到pushdown的区间修改，另一种单纯只用到单点修改）对了，每个坐标点只能放置一个监视点。。
代码：
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
#define ll long long
#define inf 1000000000
#define mod 1000000007
#define maxn 500005
#define lowbit(x) (x&-x)
#define eps 1e-9
struct node
{
int l,r,k;
}a[maxn*2];
int n,m,sum[maxn*5],lazy[maxn*5];
bool comp(node a,node b)
{
return a.r<b.r;
}
void pushdown(int l,int r,int id)
{
if(lazy[id])
{
int mid=(l+r)/2;
lazy[id*2]=1;
sum[id*2]=mid-l+1;
lazy[id*2+1]=1;
sum[id*2+1]=r-mid;
lazy[id]=0;
}
}
int update(int id,int L,int R,int l,int r,int val)
{
if(val<=0)
return 0;
if(L>=l && R<=r)
{
if(R-L+1-sum[id]<=val)//需要布置监视点 （即便当前全部布满也不能达到要求）
{
val-=R-L+1-sum[id];//还需要的监视点
lazy[id]=1;
sum[id]=R-L+1;//全部布满
return val;//还需要布满的数量
}
}
pushdown(L,R,id);
int mid=(L+R)/2;
if(r>mid)
val=update(id*2+1,mid+1,R,l,r,val);
if(l<=mid)
val=update(id*2,L,mid,l,r,val);
sum[id]=sum[id*2]+sum[id*2+1];
return val;
}
int query(int id,int L,int R,int l,int r)
{
if(L>=l && R<=r)
return sum[id];
pushdown(L,R,id);
int mid=(L+R)/2,res=0;
if(l<=mid)
res+=query(id*2,L,mid,l,r);
if(r>mid)
res+=query(id*2+1,mid+1,R,l,r);
return res;
}
int main(void)
{
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].k);
sort(a+1,a+m+1,comp);
for(i=1;i<=m;i++)
{
int w=query(1,1,n,a[i].l,a[i].r);
int w1=query(1,1,n,6,6);
printf("%d~%d w=%d\n",a[i].l,a[i].r,w);
//printf("%d~%d w=%d\n",6,6,w1);
update(1,1,n,a[i].l,a[i].r,a[i].k-w);
}
printf("%d\n",query(1,1,n,1,n));
return 0;
}
// 监视任务 运行/限制：898ms/2000ms
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct node {
int l, r, k;
bool operator<(const node& b)const {
return r < b.r;
}
}a[1000005];
int sum[500005 << 2];
int book[500005];
void pushUp(int root) {
sum[root] = sum[root << 1] + sum[root << 1 | 1];
}
void build(int le, int rig, int root) {
if (le == rig) {
sum[root] = 0;
return;
}
int mid = (le + rig) >> 1;
build(le,mid,root<<1);
build(mid+1,rig,root<<1|1);
pushUp(root);
}
int query(int l, int r, int le, int rig, int root) {
if (l <= le && r >= rig) {
return sum[root];
}
int re = 0;
int mid = (le + rig) >> 1;
if (l <= mid) {
re += query(l, r, le,mid,root<<1);
}
if (r > mid) {
re += query(l, r, mid+1,rig,root<<1|1);
}
return re;
}
void update(int pos, int le, int rig, int root) {
if (le == rig) {
sum[root] = 1;
return;
}
int mid = (le + rig) >> 1;
if (pos <= mid) {
update(pos, le,mid,root<<1);
}
else {
update(pos, mid+1,rig,root<<1|1);
}
pushUp(root);
}
int main(){
int n, m, ans;
while (scanf("%d%d", &n, &m) != EOF) {
ans = 0;
memset(book, 0, sizeof(book));
for (int i = 0; i < m; i++) {
scanf("%d%d%d",&a[i].l, &a[i].r, &a[i].k);
}
build(1, n, 1);
sort(a, a + m);
for (int i = 0; i < m; i++) {
int pos = a[i].r;//区间右边界
int cnt = query(a[i].l,a[i].r, 1, n, 1);//查询该区间已经被防卫的点的数量
while (cnt < a[i].k) {
while (book[pos]) pos--;//从右向左找位置加防卫
book[pos] = 1;
update(pos, 1, n, 1);
ans++;
cnt++;
}
}
printf("%d\n", ans);
}
return 0;
}
京公网安备 11010502036488号