とりあえず,クエリは無視して考える.
まず \(a_{[i,i+k)}\) の区間全体に \(-x\) を足す.
次に \(a_{[i+1,i+1+k)}\) の区間全体に \(x\) を足す.
すると,真ん中は変化せず, \(a_{i}\)と \(a_{i+k}\)だけ変化する.
とくに, \(x = a_{i}\) として計算すれば, \(a_{i}\) を \(0\) にして, \(a_{i+k}\) に追加した形になる.
よって, index が\(+k\)毎に, \(a\) の値をまとめることができる. \(c in k\) に対してまとまった値達が全て等しいことが, 良い数列であることの必要十分条件.
実装
判定すべき数列は, \(a\) の部分列のみ. よって,累積和で高速化できる.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m, k, q;
cin >> n >> k;
vll a(n); rep(i,n) { cin >> a[i]; }
vvll s(k);
rep(i,k) s[i].push_back(0);
rep(j,k){
for(int i = j; i < n; i += k){
s[j].push_back(s[j].back() + a[i]);
}
}
cin >> q;
rep(qi,q){
ll l,r; cin >> l >> r;
--l, --r;
++r;
vll v;
rep(i,k){
ll L = l + i;
ll ind = (L/k); // rem : L
if(L >= r) continue;
ll x = (r-L+(k-1))/k; // 個数
v.push_back(s[L%k][ind+x]-s[L%k][ind]);
}
ll fr = v.front();
bool any = true;
rep(i,v.size()-1){
if(fr != v[i+1]) any = false;
}
yesno(any);
}
return 0;
}