題意：給出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; } }新聞熱點
疑難解答
