可以思考贪心策略 询问右端点的大小排序，然后右端点相同时，左端点较靠近右端点的在前 自己YY一下 不难想 之后来思考一下如何维护 每次对区间修改查询 维护信息就一个 果断线段树
哈哈哈 我线段树都不会打了 lazy标记竟然直接赋值
#include<cmath> #include<ctime> #include<cstdio> #include<cstdlib> #include<cstring> #include<complex> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<bitset> #include<queue> #include<set> #include<map> using namespace std; inline int read() { register int x=0,f=1;register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f*x; } inline void print(int x) {if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x+'0');} const int N=100100; int n,m,a[N]; struct Q{int l,r;}q[N]; inline bool cmp(const Q &x,const Q &y) {return x.r^y.r?x.r<y.r:x.l>y.l;} struct seg_tree{int l,r,mx,mark;}tr[N<<2]; inline void pushup(int k) {tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx);} inline void pushdown(int k) { tr[k<<1].mark+=tr[k].mark;tr[k<<1|1].mark+=tr[k].mark;//ÎÒ¾¹È»Ö±½Ó°Ñlazy±ê¼Ç¸³µÈ Ц¿Þ tr[k<<1].mx+=tr[k].mark;tr[k<<1|1].mx+=tr[k].mark; tr[k].mark=0; } void build(int k,int l,int r) { tr[k].l=l;tr[k].r=r; if(l==r){tr[k].mx=-a[l];return ;} int mid=l+r>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); pushup(k); } void modify(int k,int x,int y,int val) { int l=tr[k].l,r=tr[k].r; if(l>=x&&r<=y){tr[k].mx+=val;tr[k].mark+=val;return ;}//ÎÒ¾¹È»Ö±½Ó°Ñlazy±ê¼Ç¸³µÈ Ц¿Þ int mid=l+r>>1;if(tr[k].mark)pushdown(k); if(y<=mid)modify(k<<1,x,y,val); else if(x>mid)modify(k<<1|1,x,y,val); else modify(k<<1,x,y,val),modify(k<<1|1,x,y,val); pushup(k); } int main() { n=read();m=read(); register int ans=0,i,j; for(i=1;i<=n;++i)a[i]=read(); for(i=1;i<=m;++i)q[i].l=read(),q[i].r=read(); sort(q+1,q+1+m,cmp); build(1,1,n); for(i=1;i<=m;++i) { modify(1,q[i].l,q[i].r,1); if(tr[1].mx>0)modify(1,q[i].l,q[i].r,-1); else ans++; } print(ans);puts("");return 0; } /* 5 4 1 3 2 1 3 1 3 2 5 2 3 4 5 3 */