F1. Lightsabers (easy) ～[l,r)に値vはいくつありますか？に答える構造体～ (累積和を複数)

1500 
struct AccSum{
    vector<ll> Ac;
    ll L;
    AccSum(){}
    AccSum(vector<ll> &A){
        L = A.size();
        Ac.resize(L+1);
        FOR(i, 0, L){
            Ac[i+1] = Ac[i] + A[i];
        }
    }
    // sum of [a, b)
    ll sum(ll a, ll b){
        if(a<0){
          debug("[AccSum]a<0",a);exit(0);
          return -1;
        }
        if(b>L){
          debug("[AccSum]b>L-1",b,L-1);exit(0);
          return -1;
        }
        return Ac[b] - Ac[a];
    }
};

// [l,r)に値vはいくつありますか？に答える構造体
// range counter
struct RangeCounter{
  ll N;
  vector<AccSum> Accs;
  ll ma=-1;
  // val_max : 聞かれうる最大値
  RangeCounter(VI A, ll val_max){
    N = A.size();
    ma = val_max;
    VV V(ma+1, VI(N)); // val_max+1個の累積和を作る（長さN）
    rep(i,N){
      ll v = A[i];
      V[v][i]=1;
    }
    rep(v,ma+1){
      Accs.push_back(AccSum(V[v]));
    }
  }
  // [l, r)
  // 統計で返す
  VI count(ll l, ll r){
    VI ret;
    rep(v,ma+1){
      ll cnt = Accs[v].sum(l,r);
      ret.push_back(cnt);
    }
    return ret;
  }
  // [l,r)
  // v指定で返す
  ll count(ll l, ll r, ll v){
    return Accs[v].sum(l,r);
  }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,M;
    cin>>N>>M;

    VI A(N);
    rep(i, N){
      cin >> A[i];
      A[i]--;
    }
    RangeCounter rc(A,M-1);

    // target count
    VI T(M);
    rep(i,M)cin>>T[i];
    debug(T);
    
    rep(l,N){
      FOR(r,l,N){
        VI C = rc.count(l,r+1);
        if(T==C)yes();
      }
    }
    no();
    return 0;
}

verified