1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
| #include <bits/stdc++.h> #define MAXN 300005 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } int rt[MAXN]; namespace SegmentTree{ struct node{ int l,r; int cnt; }tree[MAXN*200]; #define lc tree[i].l #define rc tree[i].r int tot; inline void pushup(int i,int x,int y){ tree[i].cnt=tree[x].cnt+tree[y].cnt; } void Update(int &i,int l,int r,int pos){ if (!i) i=++tot; if (l==r){ tree[i].cnt++; return ; } int mid=(l+r)>>1; if (pos<=mid) Update(lc,l,mid,pos); else Update(rc,mid+1,r,pos); pushup(i,lc,rc); } int Query(int rt1,int rt2,int l,int r,int k){ if (l==r) return l; int mid=(l+r)>>1,cnt=tree[tree[rt2].l].cnt-tree[tree[rt1].l].cnt; if (k<=cnt) return Query(tree[rt1].l,tree[rt2].l,l,mid,k); else return Query(tree[rt1].r,tree[rt2].r,mid+1,r,k-cnt); } void Merge(int &x,int y){ if (!x||!y){ x=x+y; return ; } pushup(x,x,y); Merge(tree[x].l,tree[y].l); Merge(tree[x].r,tree[y].r); } } using namespace SegmentTree; struct Board{ int l,r,s; }b[MAXN]; int Ans[MAXN]; int main(){ int n=read(),m=read(); int maxn=0; for (register int i=1;i<=n;++i){ b[i].l=read(),b[i].r=read(),b[i].s=read(); maxn=max(maxn,b[i].l); maxn=max(maxn,b[i].r); } for (register int i=1;i<=m;++i){ int pos=read(); maxn=max(maxn,pos); Update(rt[pos],1,MAXN,i); } for (register int i=1;i<=maxn;++i){ Merge(rt[i],rt[i-1]); } for (register int i=1;i<=n;++i){ int l=b[i].l,r=b[i].r,s=b[i].s; if (tree[rt[r]].cnt-tree[rt[l-1]].cnt<s) { continue; } else { Ans[Query(rt[l-1],rt[r],1,MAXN,s)]++; } } for (register int i=1;i<=m;++i){ printf("%d\n",Ans[i]); } }
|