数据结构杂题
给定一个长为 \(n\) 的排列 \(a_{1\sim n}\)。记区间 \([l,r]\) 中 \(a_i\) 的最小值为 \(\min_{[l,r]}\)，最大值为 \(\max_{[l,r]}\)。
对于所有 \(6\) 元组 \((l_1,r_1,l_2,r_2,l_3,r_3)\) 满足 \(1\le l_1\le r_1<l_2\le r_2<l_3\le r_3\le n\)，求 \(\max(0,\min_{[l_2,r_2]}-\max_{[l_1,r_1]})\times\max(0,\min_{[l_2,r_2]}-\max_{[l_3,r_3]})\) 之和对 \(9712176\) 取模的结果。
\(n\le 10^6\)
显然，我们只关心 \(\min_{[l_2,r_2]}>\max_{[l_1,r_1]}\wedge \min_{[l_2,r_2]}>\max_{[l_3,r_3]}\) 的情况。此时，三个区间一定不交。不定区间的最值容易想到从最值处统计区间数量，通过单调栈预处理后可以知道每个数作为区间 \(\min/\max\) 的区间数量。发现在钦定三个最值之后，三个区间相互独立，枚举量降低到 \(n^3\)。
发现不是任意钦定三个最值都对应合法的方案，因为我们要求两个最大值分布在最小值的两边。因此考虑枚举其中的最小值，这样我们可以知道最小值的位置在哪，相应能够统计前缀和后缀中两个最大值的贡献。
因此扫描值域，每次钦定当前值为 \(\min_{[l_2,r_2]}\)，然后开两个 BIT 统计前缀和后缀中 \(\max_{[l_1,r_1]}\) 和 \(\max_{[l_3,r_3]}\) 的贡献。处理之后，再把当前值作为 \(\max_{[l_1,r_1]}\) 和 \(\max_{[l_3,r_3]}\) 分别加入两个 BIT 即可。
代码
| #include<iostream>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int MOD = 9712176;
int n, ans;
int a[N], ia[N];
int gel[N], ger[N], lel[N], ler[N];
int sta[N], top;
namespace BIT {
int sum[N], cnt[N];
inline void insert(int p, int c, int v) {
v = v * c % MOD;
for(int i = p; i <= n; i += i & -i) (sum[i] += v) %= MOD;
for(int i = p; i <= n; i += i & -i) (cnt[i] += c) %= MOD;
}
inline int query(int l, int r, int v) {
int s = 0, c = 0;
for(int i = r; i > 0; i -= i & -i) (s += sum[i]) %= MOD;
for(int i = r; i > 0; i -= i & -i) (c += cnt[i]) %= MOD;
for(int i = l - 1; i > 0; i -= i & -i) (s += MOD - sum[i]) %= MOD;
for(int i = l - 1; i > 0; i -= i & -i) (c += MOD - cnt[i]) %= MOD;
return (v * c % MOD + MOD - s) % MOD;
}
}
signed main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) ia[a[i]] = i;
top = 0;
for(int i = 1; i <= n; i++) {
while(top && a[sta[top]] < a[i]) --top;
if(top) gel[i] = sta[top];
sta[++top] = i;
}
top = 0;
for(int i = n; i >= 1; i--) {
while(top && a[sta[top]] < a[i]) --top;
if(top) ger[i] = sta[top];
else ger[i] = n + 1;
sta[++top] = i;
}
top = 0;
for(int i = 1; i <= n; i++) {
while(top && a[sta[top]] > a[i]) --top;
if(top) lel[i] = sta[top];
sta[++top] = i;
}
top = 0;
for(int i = n; i >= 1; i--) {
while(top && a[sta[top]] > a[i]) --top;
if(top) ler[i] = sta[top];
else ler[i] = n + 1;
sta[++top] = i;
}
for(int t = 1; t <= n; t++) {
int i = ia[t];
(ans += (ler[i] - i) * (i - lel[i]) % MOD * (BIT::query(1, i, a[i]) * BIT::query(i, n, a[i]) % MOD) % MOD) %= MOD;
BIT::insert(i, (ger[i] - i) * (i - gel[i]) % MOD, a[i]);
}
cout << ans << '\n';
return 0;
}
|
强力用脚维护题。
给定 \(3\) 个序列 \(a_{1\sim n},b_{1\sim n},c_{1\sim n}\)，维护 \(7\) 种操作：
- 给定区间 \([l,r]\)，对每个 \(i\in [l,r]\) 执行 \(a_i\gets a_i+b_i\)；
- 给定区间 \([l,r]\)，对每个 \(i\in [l,r]\) 执行 \(b_i\gets b_i+c_i\)；
- 给定区间 \([l,r]\)，对每个 \(i\in [l,r]\) 执行 \(c_i\gets c_i+a_i\)；
- 给定区间 \([l,r]\) 和数字 \(v\)，对每个 \(i\in [l,r]\) 执行 \(a_i\gets a_i+v\)；
- 给定区间 \([l,r]\) 和数字 \(v\)，对每个 \(i\in [l,r]\) 执行 \(b_i\gets b_i\times v\)；
- 给定区间 \([l,r]\) 和数字 \(v\)，对每个 \(i\in [l,r]\) 执行 \(c_i\gets v\)；
- 给定区间 \([l,r]\)，查询 \(\sum_{i=l}^{r}a_i,\ \sum_{i=l}^{r}b_i,\ \sum_{i=l}^{r}c_i\)；
全部数字对 \(998244353\) 取模。
\(n,q\le 2.5\times 10^5\)
发现 \(6\) 个修改操作非常线性，考虑在线段树内对每个区间维护一个 \(4\times 4\) 矩阵的懒标记 \(tag\)，\(tag_{i,j}\) 表示第 \(j\) 个序列对第 \(i\) 个序列有多少贡献，其中第 \(4\) 个序列为单位序列。同时再维护一个向量表示区间的答案。
把 \(6\) 个修改操作写成矩阵，每次 move_tag 就用该矩阵左乘懒标记和答案。
代码
| #include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N = 2.5e5 + 10;
const int MOD = 998244353;
struct Vec {
int a[4];
inline Vec() { a[0] = a[1] = a[2] = a[3] = 0; }
inline Vec(int v0, int v1, int v2, int v3) { a[0] = v0, a[1] = v1, a[2] = v2, a[3] = v3; }
inline int &operator[](int index) { return a[index]; }
inline const int &operator[](int index) const { return a[index]; }
inline Vec operator+(const Vec &b) const {
return (Vec){(a[0] + b[0]) % MOD, (a[1] + b[1]) % MOD, (a[2] + b[2]) % MOD, (a[3] + b[3]) % MOD};
}
};
struct Matrix {
int a[4][4];
inline Matrix() { for(int i = 0; i < 4; i++) a[i][0] = a[i][1] = a[i][2] = a[i][3] = 0; }
inline Matrix(int x) { for(int i = 0; i < 4; i++) a[i][0] = a[i][1] = a[i][2] = a[i][3] = 0; a[0][0] = a[1][1] = a[2][2] = a[3][3] = x; }
inline int *operator[](int index) { return a[index]; }
inline const int *operator[](int index) const { return a[index]; }
inline Vec operator*(const Vec &b) const {
Vec res;
res[0] = (b[0] * a[0][0] + b[1] * a[0][1] + b[2] * a[0][2] + b[3] * a[0][3]) % MOD;
res[1] = (b[0] * a[1][0] + b[1] * a[1][1] + b[2] * a[1][2] + b[3] * a[1][3]) % MOD;
res[2] = (b[0] * a[2][0] + b[1] * a[2][1] + b[2] * a[2][2] + b[3] * a[2][3]) % MOD;
res[3] = b[3] * a[3][3] % MOD;
return res;
}
inline Matrix operator*(const Matrix &b) const {
Matrix res;
res[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0] + a[0][2] * b[2][0] + a[0][3] * b[3][0]) % MOD;
res[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1] + a[0][2] * b[2][1] + a[0][3] * b[3][1]) % MOD;
res[0][2] = (a[0][0] * b[0][2] + a[0][1] * b[1][2] + a[0][2] * b[2][2] + a[0][3] * b[3][2]) % MOD;
res[0][3] = (a[0][0] * b[0][3] + a[0][1] * b[1][3] + a[0][2] * b[2][3] + a[0][3] * b[3][3]) % MOD;
res[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0] + a[1][2] * b[2][0] + a[1][3] * b[3][0]) % MOD;
res[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1] + a[1][2] * b[2][1] + a[1][3] * b[3][1]) % MOD;
res[1][2] = (a[1][0] * b[0][2] + a[1][1] * b[1][2] + a[1][2] * b[2][2] + a[1][3] * b[3][2]) % MOD;
res[1][3] = (a[1][0] * b[0][3] + a[1][1] * b[1][3] + a[1][2] * b[2][3] + a[1][3] * b[3][3]) % MOD;
res[2][0] = (a[2][0] * b[0][0] + a[2][1] * b[1][0] + a[2][2] * b[2][0] + a[2][3] * b[3][0]) % MOD;
res[2][1] = (a[2][0] * b[0][1] + a[2][1] * b[1][1] + a[2][2] * b[2][1] + a[2][3] * b[3][1]) % MOD;
res[2][2] = (a[2][0] * b[0][2] + a[2][1] * b[1][2] + a[2][2] * b[2][2] + a[2][3] * b[3][2]) % MOD;
res[2][3] = (a[2][0] * b[0][3] + a[2][1] * b[1][3] + a[2][2] * b[2][3] + a[2][3] * b[3][3]) % MOD;
res[3][0] = (a[3][0] * b[0][0] + a[3][1] * b[1][0] + a[3][2] * b[2][0] + a[3][3] * b[3][0]) % MOD;
res[3][1] = (a[3][0] * b[0][1] + a[3][1] * b[1][1] + a[3][2] * b[2][1] + a[3][3] * b[3][1]) % MOD;
res[3][2] = (a[3][0] * b[0][2] + a[3][1] * b[1][2] + a[3][2] * b[2][2] + a[3][3] * b[3][2]) % MOD;
res[3][3] = (a[3][0] * b[0][3] + a[3][1] * b[1][3] + a[3][2] * b[2][3] + a[3][3] * b[3][3]) % MOD;
return res;
}
};
int n, q;
Vec a[N];
namespace SegT {
const Matrix I(1);
bool has_tag[4 * N];
Matrix tag[4 * N];
Vec sum[4 * N];
inline int lc(int x) { return x << 1; }
inline int rc(int x) { return x << 1 | 1; }
inline void push_up(int p) {
sum[p] = tag[p] * (sum[lc(p)] + sum[rc(p)]);
}
inline void move_tag(int p, const Matrix &tg) {
tag[p] = tg * tag[p];
sum[p] = tg * sum[p];
has_tag[p] = 1;
}
inline void push_down(int p) {
if(!has_tag[p]) return;
has_tag[p] = 0;
move_tag(lc(p), tag[p]);
move_tag(rc(p), tag[p]);
tag[p] = I;
}
void build(int p, int l, int r) {
tag[p] = I;
if(l == r) {
sum[p] = (Vec){a[l][0], a[l][1], a[l][2], 1};
return;
}
int mid = (l + r) >> 1;
build(lc(p), l, mid);
build(rc(p), mid + 1, r);
sum[p] = sum[lc(p)] + sum[rc(p)];
}
void mul(int p, int l, int r, int ql, int qr, const Matrix &v) {
if(ql <= l && r <= qr) { move_tag(p, v); return; }
push_down(p);
int mid = (l + r) >> 1;
if(ql <= mid) mul(lc(p), l, mid, ql, qr, v);
if(mid < qr) mul(rc(p), mid + 1, r, ql, qr, v);
push_up(p);
}
Vec query(int p, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) return sum[p];
push_down(p);
int mid = (l + r) >> 1;
Vec res;
if(ql <= mid) res = res + query(lc(p), l, mid, ql, qr);
if(mid < qr) res = res + query(rc(p), mid + 1, r, ql, qr);
return tag[p] * res;
}
void print(int p, int l, int r) {
if(l == r) {
cout << sum[p][0] << ' ' << sum[p][1] << ' ' << sum[p][2] << ' ' << sum[p][3] << '\n';
return;
}
push_down(p);
int mid = (l + r) >> 1;
print(lc(p), l, mid);
print(rc(p), mid + 1, r);
}
}
signed main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i][0] >> a[i][1] >> a[i][2];
SegT::build(1, 1, n);
cin >> q;
while(q--) {
int op, l, r, v;
cin >> op >> l >> r;
if(op <= 3) {
Matrix mat(1);
if(op == 1) mat[0][1] = 1;
else if(op == 2) mat[1][2] = 1;
else mat[2][0] = 1;
SegT::mul(1, 1, n, l, r, mat);
} else if(op <= 6) {
cin >> v;
Matrix mat(1);
if(op == 4) mat[0][3] = v;
else if(op == 5) mat[1][1] = v;
else mat[2][2] = 0, mat[2][3] = v;
SegT::mul(1, 1, n, l, r, mat);
} else if(op == 7) {
Vec res = SegT::query(1, 1, n, l, r);
cout << res.a[0] << ' ' << res.a[1] << ' ' << res.a[2] << '\n';
} else SegT::print(1, 1, n);
}
return 0;
}
|
有两组区间，每组内区间编号为 \(1\sim n\)。称两个区间冲突当且仅当两区间有交（可以只有一个点）。问两组区间的冲突关系是否相同。
\(n\le 10^5\)
只需对每个区间求出，组内和它冲突的区间构成的集合，然后判断两组集合是否对应相等即可。集合判等考虑哈希，先给每个编号赋一个 unsigned long long 的随机权值，然后将所有与它冲突的区间编号的哈希异或起来即可。
接下来做法就很多了。显然可以二维数点。也可以正难则反，求出不冲突集合的哈希值。
给定一个长为 \(n\) 的序列 \(a\)，记 \(f_{i,k}=\min_{j=i}^{i+k-1}\{a_j\}\)。请对每个 \(k\in [1,n]\) 求出，\(\sum_{i=1}^{n-k+1}f(i,k)\)。
\(n\le 10^6\)
考察每个数字作为最小值的贡献。先用单调栈求出左侧第一个更小的数字和右侧第一个更小的数字，记这两个数字分别距离当前数字 \(d_1,d_2\) 远。发现 \(k\le \min(d_1,d_2)\) 时，区间数量等于 \(k\)；当 \(\min(d_1,d_2)<k\le \max(d_1,d_2)\) 时，区间数量等于 \(\min(d_1,d_2)\)；当 \(k>\max(d_1,d_2)\) 时，区间数量等于 \(d_1+d_2-k\)。
发现这个分段函数的二阶差分只有 \(O(1)\) 个位置有值，因此直接做做完了。
代码
| #include<iostream>
#include<iomanip>
using namespace std;
const int N = 1e6 + 10;
int n, q;
int a[N];
int lel[N], ler[N];
int sta[N], top;
long long ans[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) {
while(top && a[sta[top]] > a[i]) --top;
if(top) lel[i] = sta[top];
sta[++top] = i;
}
top = 0;
for(int i = n; i >= 1; i--) {
while(top && a[sta[top]] >= a[i]) --top;
if(top) ler[i] = sta[top];
else ler[i] = n + 1;
sta[++top] = i;
}
for(int i = 1; i <= n; i++) {
int mn = min(i - lel[i], ler[i] - i);
int mx = max(i - lel[i], ler[i] - i);
ans[1] += a[i];
ans[mn + 1] -= a[i];
ans[mx + 1] -= a[i];
ans[mn + mx + 1] += a[i];
}
for(int i = 1; i <= n; i++) ans[i] += ans[i - 1];
for(int i = 1; i <= n; i++) ans[i] += ans[i - 1];
cout << fixed << setprecision(15);
cin >> q;
while(q--) {
int k;
cin >> k;
cout << (long double)ans[k] / (n - k + 1) << '\n';
}
return 0;
}
|
给定一个长为 \(n\) 的序列，每次询问一个区间。定义 \(c(x)\) 表示区间内有多少个值出现了 \(x\) 次。问 \(x\times c(x)\) 的最大值。
\(n,q\le 2\times 10^5\)
由于 \(\sum x\times c(x)=r-l+1\)，因此 \(x>\sqrt n\) 的部分，\(c(x)\) 有值的位置不超过 \(\sqrt n\) 个。
考虑莫队和根号分治，\(x\le \sqrt n\) 的部分暴力查询，\(x>\sqrt n\) 的部分，扩展时将这些 \(x\) 放进一个列表中，查询时双指针删掉列表中已经无效的东西即可。有一个均摊所以还是单根号。
代码
| #include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
int blen, blo[N];
struct Qr {
int l, r, id;
inline bool operator<(const Qr &b) const {
if(blo[l] != blo[b.l]) return blo[l] < blo[b.l];
return (blo[l] & 1) ? r < b.r : r > b.r;
}
};
int n, nq, lim;
int a[N], ans[N];
Qr q[N];
int c_l = 1, c_r = 0;
int cnt[N];
int ccnt[N], vis[N];
int sta[N], top;
void add_cntval(int x) {
if(x == 0) return;
++ccnt[x];
if(x > lim) {
if(!vis[x]) sta[++top] = x;
}
}
void del_cntval(int x) {
if(x == 0) return;
--ccnt[x];
}
void add(int p) {
del_cntval(cnt[a[p]]++);
add_cntval(cnt[a[p]]);
}
void del(int p) {
del_cntval(cnt[a[p]]--);
add_cntval(cnt[a[p]]);
}
int query() {
int res = 0;
for(int i = 1; i <= lim; i++) res = max(res, ccnt[i] * i);
int j = 1;
for(int i = 1; i <= top; i++, j++) {
if(!ccnt[sta[i]]) { j--; vis[sta[i]] = 0; continue; }
sta[j] = sta[i];
res = max(res, ccnt[sta[i]] * sta[i]);
}
top = j - 1;
return res;
}
int main() {
cin >> n >> nq;
lim = sqrt(n);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= nq; i++) cin >> q[i].l >> q[i].r;
for(int i = 1; i <= nq; i++) q[i].id = i;
blen = max(1, (int)(n / sqrt(nq)));
for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;
sort(q + 1, q + 1 + nq);
for(int i = 1; i <= nq; i++) {
int l = q[i].l, r = q[i].r;
while(l < c_l) add(--c_l);
while(r > c_r) add(++c_r);
while(l > c_l) del(c_l++);
while(r < c_r) del(c_r--);
ans[q[i].id] = query();
}
for(int i = 1; i <= nq; i++) cout << ans[i] << '\n';
return 0;
}
|
给定一个长度为 \(n\) 的数组 \(a\)。有 \(q\) 次询问，每次询问给定 \(s,d,k\)，表示询问 \(a_s + a_{s+d} \cdot 2 + \dots + a_{s + d \cdot (k - 1)} \cdot k\) 的和。
\(n\le 10^5,\ q\le 2\times 10^5\)
显然可以根号分治。小于根号的预处理两个值即可。
代码
| #include<iostream>
#include<cmath>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int T;
int n, q, lim;
ll a[N];
ll s1[320][N], s2[320][N];
ll baoli(int s, int d, int k) {
ll res = 0;
for(int i = 1; i <= k; i++) res += a[s + (i - 1) * d] * i;
return res;
}
ll calc(int s, int d, int k) {
int r = s + (k - 1) * d;
if(s - d >= 0) return (s1[d][r] - s1[d][s - d]) - (s2[d][r] - s2[d][s - d]) * (s / d - 1);
else return s1[d][r] - s2[d][r] * (s / d - 1);
}
int main() {
cin >> T;
while(T--) {
cin >> n >> q;
lim = sqrt(n);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int d = 1; d <= lim; d++) {
for(int i = 1; i < d; i++) s2[d][i] = a[i];
for(int i = d; i <= n; i++) {
s1[d][i] = s1[d][i - d] + a[i] * (i / d);
s2[d][i] = s2[d][i - d] + a[i];
}
}
while(q--) {
int s, d, k;
cin >> s >> d >> k;
if(d > lim) cout << baoli(s, d, k) << ' ';
else cout << calc(s, d, k) << ' ';
}
cout << '\n';
}
return 0;
}
|
给定一个序列，支持两种操作：
- 给定 \(l,r\)，求 \([l,r]\) 的区间和模 \(10^9+7\)；
- 给定 \(x,y,z\)，将所有模 \(x\) 余 \(y\) 的位置加上 \(z\)；
先分治掉 \(x\) 比较大的部分，这些部分和原序列都用一个分块处理。
其余部分直接存起来；查询时枚举 \(x\)，然后对应的余数形如一个区间，可以在修改的时候暴力维护前缀和。
卡卡常，别实现太劣了，调调块长。
代码
| #include<ctype.h>
#include<cstdio>
#include<bits/stl_algobase.h>
#include<vector>
#include<cmath>
#define ll long long
#define rint register int
using namespace std;
const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
char endl = '\n';
namespace io {
struct istream {
char ch;
bool flag;
inline istream &operator>>(int &x) {
flag = 0;
while(!isdigit(ch = getchar_unlocked())) (ch == '-') && (flag = 1);
x = ch - '0';
while(isdigit(ch = getchar_unlocked())) x = (x << 3) + (x << 1) + ch - '0';
flag && (x = -x);
return *this;
}
} cin;
struct ostream {
char buf[60];
int top;
inline ostream() : top(0) {}
template<typename _Tp>
inline ostream &operator<<(_Tp x) {
if(x < 0) putchar_unlocked('-'), x = -x;
do buf[++top] = x % 10 + '0', x /= 10; while(x);
while(top) putchar_unlocked(buf[top--]);
return *this;
}
inline ostream &operator<<(char c) {
putchar_unlocked(c);
return *this;
}
inline ostream &operator<<(const char s[]) {
for(int i = 0; s[i]; i++) putchar_unlocked(s[i]);
return *this;
}
} cout;
}
using io::cin;
using io::cout;
#define addm(a, b) (a = (a + b) % MOD)
const int blen = 200;
const int lim = 150;
int n, m;
int a[N];
// O(1)-O(sqrt)
namespace B1 {
int blo[N], a[N], sum[1500];
inline void build(int data[]) {
for(rint i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;
for(rint i = 1; i <= n; i++) a[i] = data[i];
for(rint i = 1; i <= n; i++) addm(sum[blo[i]], a[i]);
}
inline void add(int p, int v) {
addm(a[p], v);
addm(sum[blo[p]], v);
}
inline int query(rint l, rint r) {
ll res = 0;
if(blo[l] == blo[r]) {
while(l <= r) res += a[l++];
return res % MOD;
}
while(blo[l] == blo[l - 1]) res += a[l++];
while(blo[r] == blo[r + 1]) res += a[r--];
r = blo[r];
while(r != blo[l] - 1) res += sum[r], r--;
return res % MOD;
}
}
int sum[450][450];
void modify(int x, int y, int z) {
if(x > lim) {
for(rint i = y; i <= n; i += x) B1::add(i, z);
} else {
for(rint i = y; i <= x; i++) addm(sum[x][i], z);
}
}
inline int query(int l, int r) {
ll res = 0;
for(rint d = 1; d <= lim; d++) {
int tl = (l - 1) % d + 1, tr = (r - 1) % d + 1;
res += sum[d][tr] - sum[d][tl - 1];
if(tl > tr) res += sum[d][d];
res += (ll)((r - l) / d) * sum[d][d];
}
res += B1::query(l, r);
return (res % MOD + MOD) % MOD;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
B1::build(a);
while(m--) {
int op, x, y, z, l, r;
cin >> op;
if(op == 1) {
cin >> x >> y >> z;
modify(x, y, z);
} else {
cin >> l >> r;
cout << query(l, r) << '\n';
}
}
return 0;
}
|
给定一个长为 \(n\) 的序列，支持三种操作：
- 区间加；
- 区间 \(x\gets \operatorname{popcnt}(x)\)；
- 单点查询；
\(n\le 3\times 10^5,\ q\le 10^6\)
考虑线段树。由于区间加的存在，因此较难使用势能分析。考虑记录 tag，发现 \(\operatorname{popcnt}\) 的值域只有 \(\log n\) 级别，因此在第一次 \(\operatorname{popcnt}\) 之后，同一个区间内只有 \(32\) 种本质不同的取值（即使经过了其他操作）。
因此考虑在线段树的 tag 中记录是否经过了一次 \(\operatorname{popcnt}\)，以及在第一次进行 \(\operatorname{popcnt}\) 之前区间加了多少。对于之后的操作，我们用一个大小为 \(\log V\) 的数组进行维护，表示第一次 \(\operatorname{popcnt}\) 之后生成的每个值，在之后的操作中会变成哪个数。
发现容易进行标记的下传（复合），因此维护是容易的。
代码
| // 注意要用 __builtin_popcountll
#include<iostream>
#define int long long
#define popcnt(x) __builtin_popcountll(x)
using namespace std;
const int N = 3e5 + 10;
int n, q;
int a[N];
namespace SegT {
struct Node {
int f[32];
int add, tag;
inline void clear() { for(int i = 0; i < 32; i++) f[i] = i; add = tag = 0; }
inline Node() { clear(); }
inline int t(int x) { x += add; if(tag) { x = popcnt(x); return f[x]; } return x; }
} tr[4 * N];
inline int lc(int x) { return x << 1; }
inline int rc(int x) { return x << 1 | 1; }
inline void move_tag1(int p, int v) {
if(tr[p].tag) for(int i = 0; i < 32; i++) tr[p].f[i] += v;
else tr[p].add += v;
}
inline void move_tag2(int p) {
if(tr[p].tag) for(int i = 0; i < 32; i++) tr[p].f[i] = popcnt(tr[p].f[i]);
else tr[p].tag = 1;
}
inline void move_tag(int p, const Node &tg) {
move_tag1(p, tg.add);
if(!tg.tag) return;
move_tag2(p);
for(int i = 0; i < 32; i++) tr[p].f[i] = tg.f[tr[p].f[i]];
}
inline void push_down(int p) {
if(!tr[p].tag && !tr[p].add) return;
move_tag(lc(p), tr[p]);
move_tag(rc(p), tr[p]);
tr[p].clear();
}
void add(int p, int l, int r, int ql, int qr, int v) {
if(ql <= l && r <= qr) {
move_tag1(p, v);
return;
}
push_down(p);
int mid = (l + r) >> 1;
if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
}
void cg_popcnt(int p, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
move_tag2(p);
return;
}
push_down(p);
int mid = (l + r) >> 1;
if(ql <= mid) cg_popcnt(lc(p), l, mid, ql, qr);
if(mid < qr) cg_popcnt(rc(p), mid + 1, r, ql, qr);
}
int query(int p, int l, int r, int q) {
if(l == r) return tr[p].t(a[l]);
int mid = (l + r) >> 1;
if(q <= mid) return tr[p].t(query(lc(p), l, mid, q));
return tr[p].t(query(rc(p), mid + 1, r, q));
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
while(q--) {
char op;
int l, r, x;
cin >> op;
if(op == 'A') {
cin >> l >> r >> x;
SegT::add(1, 1, n, l, r, x);
} else if(op == 'P') {
cin >> l >> r;
SegT::cg_popcnt(1, 1, n, l, r);
} else {
cin >> x;
cout << SegT::query(1, 1, n, x) << '\n';
}
}
return 0;
}
|