企业官网建设流程全解析

贪心正确性
按右端点排序后，每次尽量满足当前请求。因为右端点越小，越早结束，对后面区间的影响越小，所以优先选择它们可以留下更多空间给后面的请求。

#include<bits/stdc++.h>usingnamespacestd;intn,m;intc[100005];// c[i] 表示第 i 个畜栏的初始容量vector<pair<int,int>>qwq;// 存储所有请求区间 (A, B)// 线段树节点structnode{node*l;// 左儿子node*r;// 右儿子intll,rr;// 当前节点维护的区间 [ll, rr]intlazy_flag;// 懒标记：表示这个区间整体被加了多少（可正可负）intw;// 当前区间的最小值node(){l=nullptr;r=nullptr;w=0;lazy_flag=0;ll=rr=0;}node(intlll,intrrr){l=nullptr;r=nullptr;w=0;lazy_flag=0;ll=lll;rr=rrr;}};node*root=nullptr;// 线段树根节点// 贪心排序：按右端点从小到大排序boolcmp(pair<int,int>a,pair<int,int>b){returna.second<b.second;}// 建树：区间 [l, r]node*build(intl,intr){node*now=newnode(l,r);if(l==r)// 叶子节点，直接赋值为 c[l]{now->w=c[l];returnnow;}intmid=(l+r)/2;now->l=build(l,mid);// 递归建左子树now->r=build(mid+1,r);// 递归建右子树now->w=min(now->l->w,now->r->w);// 当前节点最小值 = 左右儿子最小值returnnow;}// 下传懒标记voidpushdown(node*now){if(now->lazy_flag!=0)// 如果有懒标记{intv=now->lazy_flag;// 左儿子整体加 vnow->l->w+=v;now->l->lazy_flag+=v;// 右儿子整体加 vnow->r->w+=v;now->r->lazy_flag+=v;// 清空当前节点的懒标记now->lazy_flag=0;}}// 区间查询最小值：查询 [l, r] 范围内的最小值intquery(intl,intr,node*now){// 当前节点区间完全被查询区间覆盖if(l<=now->ll&&now->rr<=r){returnnow->w;}pushdown(now);// 访问儿子前先下传懒标记intmid=(now->ll+now->rr)/2;intres=INT_MAX;if(l<=mid)// 查询左儿子{res=min(res,query(l,r,now->l));}if(r>mid)// 查询右儿子{res=min(res,query(l,r,now->r));}returnres;}// 区间加法：把 [l, r] 范围内所有数加上 v（这里 v 通常是 -1）voidupdate(intl,intr,intv,node*now){// 当前节点区间完全被修改区间覆盖if(l<=now->ll&&now->rr<=r){now->w+=v;// 最小值也加 vnow->lazy_flag+=v;// 懒标记累加return;}pushdown(now);// 访问儿子前先下传懒标记intmid=(now->ll+now->rr)/2;if(l<=mid)// 修改左儿子{update(l,r,v,now->l);}if(r>mid)// 修改右儿子{update(l,r,v,now->r);}now->w=min(now->l->w,now->r->w);// 更新当前节点最小值}signedmain(){scanf("%d%d",&n,&m);for(inti=1;i<=n;i++){scanf("%d",&c[i]);// 读入每个畜栏的容量}for(inti=0;i<m;i++){intb,e;scanf("%d%d",&b,&e);// 读入每个请求区间qwq.push_back(make_pair(b,e));}// 按右端点从小到大排序，贪心选择sort(qwq.begin(),qwq.end(),cmp);root=build(1,n);// 建立线段树intans=0;// 记录能满足的请求数量for(inti=0;i<m;i++){intA=qwq[i].first;intB=qwq[i].second;// 查询区间 [A, B] 内当前最小剩余容量if(query(A,B,root)>=1)// 如果最小容量 >= 1，说明可以满足这个请求{update(A,B,-1,root);// 区间内所有容量减 1ans++;// 答案加一}}printf("%d\n",ans);return0;}