专栏文章

ABC393F

LLovely_yhb
AT_abc393_f题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miq8rg5z
此快照首次捕获于
2025/12/04 00:48
3 个月前
此快照最后确认于
2025/12/04 00:48
3 个月前
查看原文

题意

给定一个长度为 nn 的序列 aa。
有 qq 次询问，每次询问 rr 和 xx 求前 rr 个数中每个数都小于等于 xx 的最长上升子序列的长度。

思路

把询问按 rr 从小到大排序，这样只需要逐渐向后拓展即可。
设 fif_i 表示以长度为 ii 的上升子序列结尾的最小值。答案是所有满足 fk≤xf_k\le x 的 kk 的最大值。
发现同一时刻，ff 是单调不降的，所以查询可以二分，在 ff 中查找第一个大于 xx 的位置。
向后拓展 aia_i 的时候，二分查找 ff 中第一个大于等于 aia_i 的位置，把这个位置变成 aia_i。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct node {int r,x,id,ans;} q[N];
bool cmp(node a,node b) {return a.r<b.r;}
bool cmp1(node a,node b) {return a.id<b.id;}
int n,Q,a[N],qi=1;
int main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>Q;
	for (int i=1; i<=n; i++) cin>>a[i];
	for (int i=1; i<=Q; i++) cin>>q[i].r>>q[i].x,q[i].id=i;
	sort(q+1,q+Q+1,cmp);
	vector<int> f;
	f.push_back(0);
	for(int i=1; i<=n; i++) {
		auto it=lower_bound(f.begin(),f.end(),a[i]);
		if(it==f.end()) f.push_back(a[i]);
		else *it=a[i];
		while(qi<=Q&&q[qi].r==i) {
			q[qi].ans=upper_bound(f.begin(), f.end(), q[qi].x)-f.begin()-1;
			qi++;
		}
	}
	sort(q+1,q+Q+1,cmp1);
	for(int i=1;i<=Q;i++) cout<<q[i].ans<<endl;
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...