AT_abc288_d [ABC288D] Range Add Query

思路

首先你可以发现,如果一个区间 [l,r][l,r] 是一个好的序列,那么一定 ii 能从 ll 开始 一直到 rk+1r - k + 1,将 ai(i+k1)a_{i \sim (i + k - 1)} 减掉 aia_i

那么,当 l=1l = 1 时,对于每一个 ii,我们可以 Θ(n)\Theta(n) 算出减到 ai1a_{i - 1} 时,aia_i 的值,记作 cic_i

例如,样例 1 的 cc 数组为:

1
3 -4 2 0 0 0 5

在区间 [l,r][l,r] 中,a(rk+2)ra_{(r - k + 2) \sim r} 在减掉 ark+1a_{r - k + 1} 之后就不会修改了。那么这个 cc 数组的作用就可以体现了,如果 [l,r][l,r] 区间是好的序列,当且仅当 c(rk+2)rc_{(r - k + 2) \sim r} 全都为 00,因为满足上述条件意味着无需操作 a(rk+2)ra_{(r - k + 2) \sim r} 就可以满足题意。

考虑动态维护 cc 数组。显然的是 l=i+1l = i + 1cc 数组可以由 l=il = icc 数组转移。再观察一下,转移的时候,是将 imodk=ti \bmod k = t 的减去 Δ\Deltaimodk=(t+1)modki \bmod k = (t + 1) \bmod k 的加上 Δ\Delta,其中 t=imodkt = i \bmod k

那么,你用按照下标模 kk 的元素分别用一个树状数组维护其 cc 数组的值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
#define re register
#define int long long

using namespace std;

const int N = 2e5 + 10;
int n,k,q;
int arr[N],c[N];
bool ans[N];

struct Query{
int r,id;
};
vector<Query> Q[N];

inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}

struct BIT{
#define lowbit(x) (x & -x)

int tr[N];

inline void modify(int x,int k){
for (re int i = x;i <= n;i += lowbit(i)) tr[i] += k;
}

inline int query(int x){
int res = 0;
for (re int i = x;i;i -= lowbit(i)) res += tr[i];
return res;
}

#undef lowbit
}T[11];

signed main(){
n = read(),k = read();
for (re int i = 1;i <= n;i++) arr[i] = read();
for (re int i = 1;i <= n;i++){
c[i] = arr[i];
for (re int j = i;j <= i + k - 1;j++) arr[j] -= c[i];
}
for (re int ty = 0;ty < k;ty++){
int be = ty;
if (!be) be = k;
for (re int i = be;i <= n;i += k){
T[ty].modify(i,c[i]); T[ty].modify(i + 1,-c[i]);
}
}
q = read();
for (re int i = 1;i <= q;i++){
int l,r;
l = read(),r = read(); Q[l].push_back({r,i});
}
for (re int i = 1;i <= n;i++){
int be = i % k;
for (auto p:Q[i]){
bool falg = true;
int x = p.r - k + 2;
for (re int j = x;j <= p.r;j++){
int val = T[j % k].query(j);
if (val){
falg = false; break;
}
}
ans[p.id] = falg;
}
int del = T[be].query(i);
T[be].modify(1,-del); T[(be + 1) % k].modify(1,del);
}
for (re int i = 1;i <= q;i++){
if (ans[i]) puts("Yes");
else puts("No");
}
return 0;
}

AT_abc288_d [ABC288D] Range Add Query
http://watersun.top/[题解]AT_abc288_d [ABC288D] Range Add Query/
作者
WaterSun
发布于
2024年3月16日
许可协议