ABC393F

Lovely_yhb · 2025-02-16 11:13:43 · 题解

题意

给定一个长度为 n 的序列 a。

有 q 次询问，每次询问 r 和 x 求前 r 个数中每个数都小于等于 x 的最长上升子序列的长度。

思路

把询问按 r 从小到大排序，这样只需要逐渐向后拓展即可。

设 f_i 表示以长度为 i 的上升子序列结尾的最小值。答案是所有满足 f_k\le x 的 k 的最大值。

发现同一时刻，f 是单调不降的，所以查询可以二分，在 f 中查找第一个大于 x 的位置。

向后拓展 a_i 的时候，二分查找 f 中第一个大于等于 a_i 的位置，把这个位置变成 a_i。

AC Code

#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;
}