题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3888
先算出每个牛（羊驼）所覆盖的时间段，之后的操作都是对于时间段上的操作。
不好的习惯：查题解。查完发现都是线段树…
我又突然想起我之前做的题，都是区间覆盖，然后找最上面的（这个题）
每个区间拆成两个端点，然后按照时间从小到大排个序
每次把时间相同的点全都处理掉，这个过程用可删堆，关于y的小根堆，实现方法是一个优先队列和一个set，插入就往队列里插入，删除就往set里插入，求堆顶时，如果当前堆顶在set中发现了，那么就pop掉，直到堆空了或者堆顶在set中没找到
然后在每次之后把堆顶的id标记一下，因为我们一定能看到它
最后1~n扫一遍就好了
|
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 |
#include<bits/stdc++.h> #define maxn 50050 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int p,h,id; bool flag; node(int a=0,int b=0,int c=0,int d=0){id=a,p=b,h=c,flag=d;} friend bool operator < (node a,node b){ return a.p<b.p; } }; struct node1{ int id,h; node1(int x=0,int y=0){id=x,h=y;} friend bool operator < (node1 a,node1 b){ return a.h>b.h; } }; struct Queue{ priority_queue<node1>q; set<int>s; void push(node1 a){ q.push(a); } void del(int x){ s.insert(x); } int top(){ while(!q.empty() && (s.find(q.top().id)!=s.end()))s.erase(q.top().id),q.pop(); if(q.empty())return 0; else return q.top().id; } }; int n,ans; node a[maxn*2]; Queue q; bool see[maxn]; int main(){ n=rd(); for(int i=1; i<=n; i++){ int x=rd(),y=rd(),z=rd(); a[i*2-1]=node(i,-(x+1)*z,y,1); a[i*2]=node(i,-x*z,y,0); } sort(a+1,a+2*n+1); for(int i=1; i<=2*n; i++){ int now=a[i].p; while(i<=2*n && a[i].p==now){ if(a[i].flag)q.push(node1(a[i].id,a[i].h)); else q.del(a[i].id); i++; } i--; see[q.top()]=true; } for(int i=1; i<=n; i++)if(see[i])ans++; printf("%d\n",ans); return 0; } |
