题解：P10995 【MX-J3-T2】Substring

2c_s · 2024-08-26 09:09:02 · 题解

题目传送门

思路

贪心、前缀和、二分。

由于查询的是子串，那么串一定连续。这时候子串排序的结果一定是按照 1 开头，2 开头，...，n 开头这样的顺序排的。设这个数字为 a_i，则 a_i 开头的子串数量就是 n-i+1。

知道了这一点后，我们就可以先记录每个数字的位置 id_{a_i}，再把数字排序，计算出每个数开头的子串数量，最后计算前缀和。

每次查询的时候找第一个前缀和 \ge k 的位置 p，说明第 k 个子串肯定在 a_p 开头的范围内。现在我们知道左端点为 id_p，接着计算右端点。

此时 sum_p 为加上 a_p 开头的所有数之后的前缀和，所以 k-sum_{p-1} 即为要往后延长的数量。但是注意这样查的范围是右界 +1，所以最后还要 -1，即右端点为 id_p+k-sum_{p-1}-1。

• 子串数最大为 \Large\frac{n(n+1)}{2}，1\le n\le 3\times 10^5，记得开 long long。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read(){
    ll k=0;bool flag=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')flag=0;c=getchar();}
    while(isdigit(c)){k=(k<<1)+(k<<3)+(c^48);c=getchar();}
    if(flag)return k;return -k;
}
const int N=3e5+10;
ll n,q,sum[N],id[N];
struct node{
    ll x,num;//x 当前数，num 子串数量。
}a[N];
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;++i){
        a[i]={read(),n-i+1};
        id[a[i].x]=i;//记录这个数的位置。
    }
    sort(a+1,a+1+n,[](node a,node b){return a.x<b.x;});
    for(int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i].num;
    while(q--){
        ll k=read();
        int p=lower_bound(sum+1,sum+1+n,k)-sum;
        cout<<id[p]<<" "<<id[p]+k-sum[p-1]-1<<"\n";
    }
    return 0;
}

AC 记录