hiho1460 rmq模板题

/*
给定长为n的字符串，要求在字符串中选择k个字符，
选择的子系列字典序最小
因为选择k个字符，那么就是去掉n-k个字符
那么[1,n-k+1]位中必定选择一个字符
设这个字符在t1位 
然后[t1,n-k+2]位中必定选择一个字符 
设这个字符在t2位
以此类推
那么问题就是求区间最小字符的下标
rmq即可 
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int dp[maxn][20],k,n;
char a[maxn];
void RMQ(){
    for(int i=1;i<=n;i++)dp[i][0]=i;
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            if( a[dp[i][j-1]] <= a[dp[i+(1<<(j-1))][j-1]] )
                dp[i][j]=dp[i][j-1];
            else dp[i][j]=dp[i+(1<<(j-1))][j-1];
}
int query(int l,int r){
    int k=log(r-l+1.0)/log(2.0);
    if(a[dp[l][k]] <= a[dp[r-(1<<k)+1][k]])
        return dp[l][k];
    return dp[r-(1<<k)+1][k];
}
int main(){
    cin>>k>>a+1;
    n=strlen(a+1);
    int m=n-k+1;
    RMQ();
    int t=1;
    vector<char>v;
    v.clear(); 
    for(int i=m;i<=n;i++){
        t=query(t,i);
        v.push_back(a[t]);
        t++; 
    }
    for(int i=0;i<v.size();i++)
        cout<<v[i];
}