监视任务
來源：牛客網(wǎng)
：
時間限制：C/C++ 2秒，其他語言4秒
空間限制：C/C++ 131072K，其他語言262144K
64bit IO Format: %lld
題目描述
𝑅𝑒𝑘𝑖在課余會接受一些民間的鷹眼類委托，即遠(yuǎn)距離的狙擊監(jiān)視防衛(wèi)。
𝑅𝑒𝑘𝑖一共接到了𝑚份委托，這些委托與𝑛個直線排布的監(jiān)視點相關(guān)。 第𝑖份委托的內(nèi)容為：對于區(qū)間[𝑙𝑖,
𝑟𝑖]中的監(jiān)視點，至少要防衛(wèi)其中的𝑘𝑖個。 𝑅𝑒𝑘𝑖必須完成全部委托，并且希望選取盡量少的監(jiān)視點來防衛(wèi)。
輸入描述:
第一行，兩個正整數(shù)𝑛，𝑚。
接下來𝑚行，每行三個整數(shù)𝑙𝑖，𝑟𝑖，𝑘𝑖。
輸出描述:
一行，一個整數(shù)，即所需防衛(wèi)的最少監(jiān)視點數(shù)量。
示例1
輸入
復(fù)制
輸出
復(fù)制
備注:
對于10%的數(shù)據(jù)，𝑛 ≤ 10。 對于20%的數(shù)據(jù)，𝑛 ≤ 20。 對于30%的數(shù)據(jù)，𝑛,𝑚 ≤ 30。 對于60%的數(shù)據(jù)，𝑛,𝑚 ≤ 1000。 對于100%的數(shù)據(jù)，𝑛 ≤ 500000，𝑚 ≤ 1000000，𝑙𝑖 ≤ 𝑟𝑖，𝑘𝑖 ≤ 𝑟𝑖?𝑙𝑖+1。題解：
貪心+線段樹
我們先將給的m個區(qū)間進(jìn)行排序，按照右端點值從小到大排
然后對每個區(qū)間值查詢監(jiān)視點的數(shù)量，如果不滿足要求就填充，記得要盡可能的給區(qū)間的右側(cè)填充，因為這樣更有利于后面的區(qū)間能用上
比如[1,3]和[3,6]，兩個區(qū)間各需要一個監(jiān)視點，我們我們給[1,3]按上一個，盡可能在右側(cè)安裝，也就是點3，這樣查詢[3,6]時我們發(fā)現(xiàn)已經(jīng)有了，就不用給[3,6]再安裝了
區(qū)間修改操作涉及到了線段樹
那在線段樹區(qū)間修改的時候，怎么能先優(yōu)先更新右側(cè)？
很簡單，我們在更新是優(yōu)先更新右節(jié)點
代碼中是先更新id*2+1即右節(jié)點，這樣就會優(yōu)先在右側(cè)填充，如果兩個語句反過來，就是優(yōu)先填充左側(cè)
有兩種寫法（一種用到pushdown的區(qū)間修改，另一種單純只用到單點修改）對了，每個坐標(biāo)點只能放置一個監(jiān)視點。。
代碼：
#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)//需要布置監(jiān)視點 （即便當(dāng)前全部布滿也不能達(dá)到要求）{val-=R-L+1-sum[id];//還需要的監(jiān)視點 lazy[id]=1;sum[id]=R-L+1;//全部布滿return val;//還需要布滿的數(shù)量 }}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; } // 監(jiān)視任務(wù) 運行/限制：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;//區(qū)間右邊界int cnt = query(a[i].l,a[i].r, 1, n, 1);//查詢該區(qū)間已經(jīng)被防衛(wèi)的點的數(shù)量while (cnt < a[i].k) {while (book[pos]) pos--;//從右向左找位置加防衛(wèi)book[pos] = 1;update(pos, 1, n, 1);ans++;cnt++;}}printf("%d\n", ans);}return 0; }總結(jié)
