AtCoder Beginner Contest 463 C - Tallest at the Moment 题解

老传统了打完ABC写T3题解

solve

• 求区间最值奥，线段树
• LZYXT的线段树
• 在最后给出LZYXT的ST表
• 好的我们不使用线段树
• H，L一定要处理的，要不然你咋算答案，考虑怎么处理
• 发现时间递增，并且要求最大值
• 考虑按L递增排，然后就没思路了
• 好的我们按H递减下L递增排
• msjing写题解的时候把上面写反了
• 发现时间排序后单调，可以用类似单调队列优化dp的双端队列的写法从对头排除过时决策
• 不知道单调队列优化dp也没事，本质就是扫描
• 写！
• 爽吃一发罚时
• 我们发现仅仅是高桥君の数组是时间单增，每次查询Q不是，所以在线是&O(QN)$的，包炸
• 所以我们把查询全读了，排序并离线处理，这样时间就是单调的
• 对于输出方式不对应的问题，把每次询问是第几个存一下（pair不用写cmp，拜谢pair%%%），算出来后再把答案塞到一个数组里，遍历输出就行，实现看代码，蛮清晰的
• 时间复杂度是\(O(nlogn)\)的，查询队列均摊\(O(1)\)（貌似吧），总\(O(Q)\)，瓶颈在排序
• msjing又把时间复杂度算错了

诶为啥O(QN)能过啊
—— msjing
记录

code

#include<bits/stdc++.h>
#define Honkai ios::sync_with_stdio(0);
#define StarRail cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
constexpr int maxn=3e5+10;
long long n,Q;
pair<long long,long long> q[maxn];
struct _ {long long H,L;}gq[maxn];
bool cmp(_ a,_ b) {if (a.H == b.H) return a.L<b.L;return a.H>b.H;}
long long ans[maxn];
int main()
{Honkai StarRailcin >> n;for (long long i=1;i<=n;i++) cin >> gq[i].H >> gq[i].L;sort(gq+1,gq+1+n,cmp);cin >> Q;for (long long i=1;i<=Q;i++) cin >> q[i].first,q[i].second=i;\sort(q+1,q+1+Q);long long l=1;for (long long i=1;i<=Q;i++){while (l<=n && gq[l].L<=q[i].first) l++;ans[q[i].second]=gq[l].H;}for (long long i=1;i<=Q;i++) cout << ans[i] << endl;return 0;
}

Last：ST表

#include<bits/stdc++.h>
using namespace std;
const int NUM=3e5+10;
#define lid (id<<1)
#define rid (id<<1|1)int n;
struct node{int h,l;
}A[NUM];struct ST_Table{int Log[NUM],f[NUM][20];void init(int *a,int n){Log[1]=0;for(int i=2;i<=n;++i) Log[i]=Log[i>>1]+1;for(int i=1;i<=n;++i) f[i][0]=a[i];for(int j=1;j<=Log[n];++j){for(int i=1;i<=n-(1<<j)+1;i++){f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);}}}int Max(int x,int y){int l=Log[y-x+1];return max(f[x][l],f[y-(1<<l)+1][l]);} 
}st;int B[NUM],H[NUM];int main(){cin>>n;for(int i=1;i<=n;++i){cin>>A[i].h>>A[i].l;}sort(A+1,A+1+n,[](node a,node b){return a.l<b.l;});for(int i=1;i<=n;++i){H[i]=A[i].h,B[i]=A[i].l;}st.init(H,n);int q;cin>>q;for(int i=1,x;i<=q;++i){cin>>x;x=upper_bound(B+1,B+1+n,x)-B;cout<<st.Max(x,n)<<'\n';}return 0;
}