結果

問題 No.1725 [Cherry 3rd Tune D] 無言の言葉
コンテスト
ユーザー cureskol
提出日時 2021-10-29 23:18:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,823 bytes
コンパイル時間 2,367 ms
コンパイル使用メモリ 191,708 KB
実行使用メモリ 217,088 KB
最終ジャッジ日時 2024-10-07 12:58:05
合計ジャッジ時間 7,143 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 7 WA * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n-1);i>=0;i--)
#define ALL(v) v.begin(),v.end()

#define int long long

const int INF=4e9+7;
string x,y;
int cntx[26],cnty[26],n,m;
vector<int> T(1),TX(1),TY(1);

//BEGIN CUT HERE
template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  int n;  //セグ木の幅
  F f;  //モノイドの作用
  T ti;  //初期値
  vector<T> dat;  //セグ木で使う配列 一番上に使われるのがdat[1] 一番下の段の左端がdat[n]
  SegmentTree(){}
  SegmentTree(F f,T ti):f(f),ti(ti){}  //fがモノイドとしての作用、tiが単位元
  SegmentTree(F f,T ti,int n_):f(f),ti(ti){
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }
  SegmentTree(F f,T ti,const vector<T> &v):f(f),ti(ti){
    int n_=v.size();
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
    for(int i=0;i<n_;i++)dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  
  T operator [](int k) const{return dat[k+n];}
  
  void init(int n_){  //ただの初期化
    n=1;
    while(n<n_) n<<=1;  //nが実際にとる２べきの幅
    dat.assign(n<<1,ti);  //dat配列は幅の２倍あってその全てにtiを代入
  }
  
  void build(const vector<T> &v){  //vector vに合わせた初期化
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];  //v[i]を一番子の所に代入
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);  //iの子供は2*i、2*i+1
  }
  
  void set_val(int k,T x){  //（0-indexedで）kにxを代入
    dat[k+=n]=x;  
    while(k>>=1)  //kがどんどん自分の親になっていく、0になったらおしまい
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }
  
  T query(int a,int b){  //[a,b)の範囲のモノイドの作用を返す
    T vl=ti,vr=ti;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);  //左端を使いたくなるのはブロックが奇数の時
      if(r&1) vr=f(dat[--r],vr);  //右端〃偶数の時（開区間なのでr:奇数で反応）
    }
    return f(vl,vr);
  }
  
  template<typename C>
  int find(int st,C &check,T &acc,int k,int l,int r){  //dat[k]:[l,r)の間にいるenを返す
    //下のfind用なので先にそっち読むべき
    //accはst~lとかで確定している値
    if(l+1==r){  //答えがちゃんと存在するならこのlが答え
      acc=f(acc,dat[k]);  
      return check(acc)?k-n:-1; //入るならk-n(==l)を、入らないなら-1を返す
    }
    int m=(l+r)>>1;  //にぶたんのそれ
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);  //mがstより後ろなら明らかにl=m;
    if(st<=l&&!check(f(acc,dat[k]))){  //今見てるk全部でもダメ(mだと足りないのでl=mにする）
      acc=f(acc,dat[k]);  //kは全部accに加えた上で-1を返す
      return -1;
    }
    int vl=find(st,check,acc,(k<<1)|0,l,m);  //まず[l,m)の中にenがいるか探す
    if(~vl) return vl;  //いたならそれを返す(if(~vl)は-1以外にのみ反応する)
    return find(st,check,acc,(k<<1)|1,m,r);  //いなかったら[m,r)の中にenがいるのでそれを返す
    //acc=f(acc,dat[k]);がここで効いてる
  }
  
  template<typename C>
  int find(int st,C &check){  
    //check(f(dat[st]~dat[en-1]))=false,check(f(dat[st]~dat[en]))＝trueとなるenを返す
    T acc=ti;  
    return find(st,check,acc,1,0,n);
  }
};
//END CUT HERE

using SEG=SegmentTree<int>;

vector<SEG> segx1,segx2,segy1,segy2;

int X(int l,int r,char c,int d){
  //xの[l,r]に含まれるcの数
  //d=-1の時は xを反転したものの[l,r]
  if(d==1)return segx1[c-'a'].query(l-1,r);
  return segx2[c-'a'].query(l-1,r);
}

int Y(int l,int r,char c,int d){
  if(d==1)return segy1[c-'a'].query(l-1,r);
  return segy2[c-'a'].query(l-1,r);
}

int score(int state,int d,int a,char c){
  if(state==0)return X(1,a,c,d);
  int res=0;
  if(a<=T[state-1])return score(state-1,d,a,c);
  res+=TX[state-1]*cntx[c-'a']+TY[state-1]*cnty[c-'a'];
  if(a<=T[state-1]+m)return res+Y(1,a-T[state-1],c,d);
  res+=cnty[c-'a'];
  return res+score(state-1,d,a-T[state-1]-m,c);
}

int solve(int l,int r,char c,int d=1){
  int res=0;
  for(int k=0;;k++){
    if(T[k]>=r){
      if(k==0)return X(l,r,c,d);
      if(l<=T[k-1]){
        res+=score(k-1,-d,T[k-1]-l+1,c);
        l=T[k-1]+1;
      }
      if(l<=T[k-1]+m+1&&r>T[k-1]+m){
        res+=score(k-1,-d,r-T[k-1]-m,c);
        res+=Y(l-T[k-1],m,c,d);
        return res;
      }
      if(l>T[k-1]+m)return solve(T[k]-r+1,T[k]-l+1,c,-d);
      if(l>T[k-1]&&r<=T[k-1]+m)return Y(l-T[k-1],r-T[k-1],c,d);
      assert(false);
    }
  }
  return -1;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  segx1.resize(26);segx2.resize(26);segy1.resize(26);segy2.resize(26);
  REP(i,26){
    segx1[i].f=[](int a,int b){return a+b;};
    segx2[i].f=[](int a,int b){return a+b;};
    segy1[i].f=[](int a,int b){return a+b;};
    segy2[i].f=[](int a,int b){return a+b;};
    segx1[i].ti=0;
    segx2[i].ti=0;
    segy1[i].ti=0;
    segy2[i].ti=0;
  }
  cin>>x>>y;
  
  for(char p:x)cntx[p-'a']++;
  for(char p:y)cnty[p-'a']++;
  
  n=x.size(),m=y.size();
  REP(i,26){
    segx1[i].init(n+5);
    segx2[i].init(n+5);
    segy1[i].init(m+5);
    segy2[i].init(m+5);
  }
  REP(i,n){
    segx1[x[i]-'a'].set_val(i,1);
    segx2[x[i]-'a'].set_val(n-1-i,1);
  }
  REP(j,m){
    segy1[y[j]-'a'].set_val(j,1);
    segy2[y[j]-'a'].set_val(m-1-j,1);
  }
  T[0]=n;
  TX[0]=1,TY[0]=0;
  while(T.back()<INF){
    T.push_back(T.back()*2+m);
    TX.push_back(TX.back()*2);
    TY.push_back(TY.back()*2+1);
  }

  int q;cin>>q;
  REP(_,q){
    int l,r;char c;cin>>l>>r>>c;
    cout<<solve(l,r,c)<<"\n";
  }
}
0