結果

問題 No.1471 Sort Queries
ユーザー 👑 Nachia
提出日時 2021-04-10 09:26:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 93 ms / 2,000 ms
コード長 2,466 bytes
コンパイル時間 1,640 ms
コンパイル使用メモリ 89,128 KB
最終ジャッジ日時 2025-01-20 15:31:15
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

template<
  class S,
  S(*op)(S a,S b),
  S(*e)()
>
struct PersistentSegtree{
  struct Node{ int l,r; S v; };
  int N, logN;
  vector<Node> V;
  void merge(int p){ V[p].v=op(V[V[p].l].v,V[V[p].r].v); }
  PersistentSegtree(int z=0){
    N=1; logN=0; while(N<z){ N*=2; logN++; }
    V.assign(N*2-1,{-1,-1,e()});
    for(int i=N-2; i>=0; i--){ V[i].l=i*2+1; V[i].r=i*2+2; }
  }
  PersistentSegtree(const vector<S>& v)
    : PersistentSegtree(v.size()){
    for(int i; i<v.size(); i++) V[N-1+i].v=v[i];
    for(int i=N-2; i>=0; i--) merge(i);
  }
  int copy_node(int p){ V.push_back(V[p]); return V.size()-1;}
  int set(int t,int p,S v){
    vector<int> P;
    P.push_back(copy_node((t==-1)?0:t));
    for(int d=logN-1; d>=0; d--){
      int pp=P.back();
      if(p&(1<<d)){ P.push_back(copy_node(V[pp].r)); V[pp].r=P.back(); }
      else{ P.push_back(copy_node(V[pp].l)); V[pp].l=P.back(); }
      pp=P.back();
    }
    V[P.back()].v=v;
    for(int i=P.size()-2; i>=0; i--) merge(P[i]);
    return P.front();
  }
  int where(int t,int p){
    int s=(t==-1)?0:t;
    for(int d=logN-1; d>=0; d--) s=((p&(1<<d))?V[s].r:V[s].l);
    return s;
  }
  S get(int t,int p){
    int s=(t==-1)?0:t;
    for(int d=logN-1; d>=0; d--) s=((p&(1<<d))?V[s].r:V[s].l);
    return V[s].v;
  }
  S prod(int t,int l,int r){
    struct DFSV{ int l,r,i; };
    vector<DFSV> G; G.reserve(logN*2+2);
    int s=(t==-1)?0:t;
    G.push_back({0,N,s});
    S res=e();
    while(G.size()){
      DFSV g=G.back(); G.pop_back();
      int a=g.l, b=g.r, i=g.i;
      if(r<=a || b<=l) continue;
      if(l<=a && b<=r){ res=op(res,V[i].v); continue; }
      G.push_back({a,(a+b)/2,V[i].l});
      G.push_back({(a+b)/2,b,V[i].r});
    }
    return res;
  }
};

using RQS = int;
RQS RQe(){ return 0; }
RQS RQop(RQS l,RQS r){ return l+r; }
using RQ = PersistentSegtree<RQS,RQop,RQe>;

int N, Q;
string S;

vector<pair<int,int>> A;
RQ G;
vector<int> RQT;

int main() {
  cin>>N>>Q>>S;
  for(int i=0; i<N; i++) A.push_back({S[i],i});
  sort(A.begin(),A.end());
  G = RQ(N);
  RQT.push_back(-1);
  for(int i=0; i<N; i++) RQT.push_back(G.set(RQT.back(),A[i].second,1));
  for(int i=0; i<Q; i++){
    int l,r,x; cin>>l>>r>>x; l--;
    int lt=-1, rt=N+1;
    while(rt-lt>1){
      int mt=(lt+rt)/2;
      if(G.prod(RQT[mt],l,r)<x) lt=mt; else rt=mt;
    }
    cout<<(char)(A[rt-1].first)<<"\n";
  }
  return 0;
}
0