結果

問題 No.1725 [Cherry 3rd Tune D] 無言の言葉
コンテスト
ユーザー Nachia
提出日時 2021-10-29 22:14:04
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 92 ms / 4,000 ms
コード長 3,258 bytes
コンパイル時間 3,514 ms
コンパイル使用メモリ 117,884 KB
最終ジャッジ日時 2025-01-25 08:59:24
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/fenwicktree>
using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(n); i++)



int main(){
  string str_x, str_y; cin >> str_x >> str_y;
  int num_queries; cin >> num_queries;
  const i64 max_len = 2'000'000'000;

  auto presum_x = vector<vector<int>>(26, vector<int>(str_x.size() + 1, 0));
  for(int i=0; i<str_x.size(); i++){
    for(int c=0; c<26; c++) presum_x[c][i+1] = presum_x[c][i];
    presum_x[str_x[i] - 'a'][i+1] += 1;
  }
  
  auto presum_y = vector<vector<int>>(26, vector<int>(str_y.size() + 1, 0));
  for(int i=0; i<str_y.size(); i++){
    for(int c=0; c<26; c++) presum_y[c][i+1] = presum_y[c][i];
    presum_y[str_y[i] - 'a'][i+1] += 1;
  }

  vector<i64> sizes_of_ranked;
  sizes_of_ranked.push_back(str_x.size());
  while(sizes_of_ranked.back() < max_len){
    i64 prev = sizes_of_ranked.back();
    sizes_of_ranked.push_back(prev * 2 + (i64)str_y.size());
  }

  auto fullsum_ranked = vector<vector<int>>(26, vector<int>(sizes_of_ranked.size(), 0));
  for(int c=0; c<26; c++) fullsum_ranked[c][0] = presum_x[c].back();
  for(int i=1; i<sizes_of_ranked.size(); i++){
    for(int c=0; c<26; c++){
      fullsum_ranked[c][i] = fullsum_ranked[c][i-1] * 2 + presum_y[c].back();
    }
  }

  auto presum_ranked = [&](i64 len, int target_char, auto presum, auto sufsum, int rank = -1)->i64 {
    if(rank == -1) rank = sizes_of_ranked.size() - 1;
    if(rank == 0) return presum_x[target_char][len];
    if(len < sizes_of_ranked[rank-1]){
      return presum(len, target_char, presum, sufsum, rank-1);
    }
    if(len < sizes_of_ranked[rank-1] + (i64)str_y.size()){
      return fullsum_ranked[target_char][rank-1] + presum_y[target_char][len - sizes_of_ranked[rank-1]];
    }
    return fullsum_ranked[target_char][rank-1] + presum_y[target_char].back()
          + sufsum(len - sizes_of_ranked[rank-1] - (i64)str_y.size(), target_char, presum, sufsum, rank-1);
  };

  auto sufsum_ranked = [&](i64 len, int target_char, auto presum, auto sufsum, int rank = -1)->i64 {
    if(rank == -1) rank = sizes_of_ranked.size() - 1;
    if(rank == 0) return presum_x[target_char].back() - presum_x[target_char][str_x.size() - len];
    if(len < sizes_of_ranked[rank-1]){
      return presum(len, target_char, presum, sufsum, rank-1);
    }
    if(len < sizes_of_ranked[rank-1] + (i64)str_y.size()){
      return fullsum_ranked[target_char][rank-1] + presum_y[target_char].back() - presum_y[target_char][str_y.size() - (len - sizes_of_ranked[rank-1])];
    }
    return fullsum_ranked[target_char][rank-1] + presum_y[target_char].back()
          + sufsum(len - sizes_of_ranked[rank-1] - (i64)str_y.size(), target_char, presum, sufsum, rank-1);
  };

  for(int query_idx=0; query_idx < num_queries; query_idx++){
    i64 l, r; char c; cin >> l >> r >> c;
    i64 ans
      = presum_ranked(r, c - 'a', presum_ranked, sufsum_ranked)
      - presum_ranked(l-1, c - 'a', presum_ranked, sufsum_ranked);
    cout << ans << "\n";
  }
  return 0;
}




struct ios_do_not_sync {
    ios_do_not_sync() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0