CodeForces 228D. Zigzag

题目大意

设$S_i^z$,有

给你一个数组，进行如下操作
1.查询数组中一段区间，对于这段区间中的每一个元素a[i],计算$$\sum _{i=l}^r{S}_i^z\ast a[i]$$
2.对数组中某个元素进行单点修改
通过分析$S_i^z$可以发现它是一个有规律的数组，
即从0-2*(z-1)-1为一个循环，由于2<=z<=6,所以我们可以先求出$S_i^z$的所有可能取值
对于区间修改单点查询，很明显可以用线段树和树状数组

思路1 线段树

那么对于每个节点我们设置一个sum数组，记录每个z的取值下对应的$S_i^z$,
需要注意的是在查询的时候需要考虑到子区间的长度问题，即在取右区间的时候要把左区间的长度也给加上
在Pushup的时候同样在求父节点时右子节点要从左子节点的长度开始

// Author: zengyz
// 2025-06-11 10:43#include <bits/stdc++.h>using namespace std;
using i64 = long long;
typedef long long LL;
const int N = 100010;
int m, p;
int z[7][10];
int a[N];
struct node
{int l, r;i64 sum[7][10];
} tr[N * 4];
void pushup(int u)
{for (int i = 2; i <= 6; i++){for (int j = 0; j < 2 * (i - 1); j++){int dis = tr[u << 1].r - tr[u << 1].l + 1;tr[u].sum[i][j] = tr[u << 1].sum[i][j] + tr[u << 1 | 1].sum[i][(j + dis) % (2 * (i - 1))];}}
}
void build(int u, int l, int r)
{tr[u].l = l, tr[u].r = r;if (l == r){for (int i = 2; i <= 6; i++)for (int j = 0; j < 2 * (i - 1); j++)tr[u].sum[i][j] = (1ll) * a[l] * z[i][j];return;}int mid = (l + r) >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);pushup(u);
}
i64 query(int u, int l, int r, int zz, int pos)
{if (tr[u].l == l && tr[u].r == r)return tr[u].sum[zz][pos];i64 v = 0;int mid = (tr[u].r + tr[u].l) >> 1;if (r <= mid) // 所求区间左子区间够v = query(u << 1, l, r, zz, pos);else if (l > mid) // 所求区间右子区间够v = query(u << 1 | 1, l, r, zz, pos);elsev = query(u << 1, l, mid, zz, pos) + query(u << 1 | 1, mid + 1, r, zz, (pos + (mid - l + 1)) % (2 * (zz - 1)));return v;
}
void modify(int u, int p, int v)
{if (tr[u].l == tr[u].r && tr[u].l == p){for (int i = 2; i <= 6; i++)for (int j = 0; j < 2 * (i - 1); j++)tr[u].sum[i][j] = (1ll) * v * z[i][j];return;}int mid = (tr[u].r + tr[u].l) >> 1;if (p <= mid)modify(u << 1, p, v);else if (p > mid)modify(u << 1 | 1, p, v);pushup(u);
}
void solve()
{for (int i = 2; i <= 6; i++){for (int j = 0; j < 2 * (i - 1); j++){if (j == 0)z[i][j] = 2;else if (j <= i)z[i][j] = j;elsez[i][j] = 2 * i - j;}}int n;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];build(1, 1, n);cin >> m;while (m--){int op;cin >> op;if (op == 1){int p, v;cin >> p >> v;modify(1, p, v);}else{int li, ri, zi;cin >> li >> ri >> zi;cout << query(1, li, ri, zi, 1) << endl;}}return;
}int main()
{int _T = 1;while (_T--){solve();}return 0;
}

思路2 树状数组

由于题目要求区间修改和单点查询，其实树状数组更简单且也能符合要求
定义a[N],b[N],存储当前每个位置实际的值，为了不影响原数组的值，先用b数组读入，在执行Update(i,b[i])时将值赋给a数组，保证开始时a[i]==b[i],后面只操作a[i]
令mod=2*(z-1)
tr[i][j][k]维护了一个当 z=i 时，满足 k%mod=j 时前 k 个值的前缀和数组
add函数和sum函数都是标准的树状数组函数，用来取前缀和数组中的值

update函数是在修改数组某一个值时，遍历z=2~6的情况，对于当前位置pos
通过取模得到模值p= pos%mod，然后通过add操作将pos和 v-a[pos] (新值减旧值得到增加值）赋给tr数组

query查询操作是对于0~mod-1的每一个模值
p=((j-l%mod+1)+mod)%mod得到从l开始当前应该是第几个数，（。。。+mod）%mod是防止里面出现负数的情况
通过树状数组求出其在数组l~r之间 值的总和val
它们共享相同的模值p
所以答案加上 p的各种情况*val
也就是说对于这个数组，将它们按照mod分成了2*(z-1)个数组,彼此之间没有关系
对于每个数组(2*(z-1)个)，其实就是一个简单的树状数组，然后用求前缀和的方法求出区间就行，对于tr数组的第三维，其实有很多地方没有访问到，对于原数组b[i]，它们被模数分得很开，只有for(i-n),i%mod相同的值才会存到同一个树状数组（也就是前两维相同）

// Author: zengyz
// 2025-06-11 16:44#include <bits/stdc++.h>using namespace std;
using i64 = long long;
int n, m;
int lowbit(int x)
{return x & (-x);
}
const int N = 1e5 + 10;
i64 tr[7][10][N];
i64 a[N], b[N];
void add(i64 tr[], int pos, int v)
{for (; pos <= n; pos += lowbit(pos))tr[pos] += v;
}
i64 sum(i64 tr[], int pos)
{i64 v = 0;for (; pos>=1; pos -= lowbit(pos))v += tr[pos];return v;
}
void update(int pos, int v)
{for (int i = 2; i <= 6; i++){add(tr[i][pos % (2 * (i - 1))], pos, v - a[pos]);}a[pos] = v;
}
i64 query(int l, int r, int z)
{i64 res = 0;for (int j = 0; j < 2 * (z - 1); j++){i64 val = sum(tr[z][j], r) - sum(tr[z][j], l - 1);int mod = 2 * (z - 1);int p = (j - l % mod + 1 + mod) % mod;if(p==0)res+=2*val;else if(p<=z)res+=p*val;elseres+=(2*z-p)*val;}return res;
}
void solve()
{cin >> n;for (int i = 1; i <= n; i++)cin >> b[i];for (int i = 1; i <= n; i++)update(i, b[i]);cin >> m;while (m--){int op;cin >> op;if (op == 1){int p, v;cin >> p >> v;update(p, v);}else{int l, r, z;cin >> l >> r >> z;cout << query(l, r, z) << endl;}}return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;// cin >> _T;while (_T--){solve();}return 0;
}