练习赛D题线段树

2019-11-06 07:24:21

字体：大中小

来源：转载

供稿：网友

题意：给出n个房间m个人，每个人需要打扫[l,r]的房间。问有几个队可以偷懒不用干活代码：

#include<stdio.h>#include<stdlib.h>#include<algorithm>#include<iostream>#include<vector>#include<map>#include<math.h>#include<string.h>#define ll long longconst int N=1e5+10;int output[N];int n,t,m;inline int min(int x,int y){ if(x>=y) return y; else return x;}struct node{ int x,y;} a[N];int sum[N<<2];int add[N<<2];inline void pushup(int rt){ sum[rt]=min(sum[rt<<1],sum[rt<<1|1]);}inline void pushdown(int rt){ if(add[rt]) { add[rt<<1]+=add[rt]; add[rt<<1|1]+=add[rt]; sum[rt<<1]+=add[rt]; sum[rt<<1|1]+=add[rt]; add[rt]=0; }}inline int query(int l,int r,int L,int R,int rt){ int mi=1e9; if(L<=l&&R>=r) return sum[rt]; pushdown(rt); int mid=(r+l)>>1; if(L<=mid) mi=min(mi,query(l,mid,L,R,rt<<1)); if(R>mid) mi=min(mi,query(mid+1,r,L,R,rt<<1|1)); return mi;}inline void update(int L, int R,int c, int l, int r, int rt){ if(L<=l&&R>=r) { add[rt]+=c; sum[rt]+=c; return ; } pushdown(rt); int mid=(r+l)>>1; if(L<=mid) update(L,R,c,l,mid,rt<<1); if(R>mid) update(L,R,c,mid+1,r,rt<<1|1); pushup(rt);}int main(){ scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(sum,0,sizeof(sum)); memset(add,0,sizeof(add)); for(int i=1; i<=m; i++) { scanf("%d%d",&a[i].x,&a[i].y); update(a[i].x,a[i].y,1,1,n,1); } int ans=0; for(int i=1; i<=m; i++) { int cnt=query(1,n,a[i].x,a[i].y,1); if(cnt>=2) { output[ans++]=i; } } PRintf("%d/n",ans); for(int i=0; i<ans; i++) { if(i==0) printf("%d",output[i]); else printf(" %d",output[i]); } if(ans!=0) printf("/n"); }}

上一篇：函数的参数学习笔记

下一篇：STM32串口如何代码实现更稳定的接收消息