怎么比 Ntokisq 还简略
思路
线段树 + 势能分析。
popcount 看起来不好维护，每次都需要对整个序列大力做。
注意到 popcount 的值域只有 O(logV)O(logV)，所以考虑在线段树上的每个结点维护一个置换标记 ff 来维护 popcount.
可以认为 popcount 操作等价于应用一次置换：(1popcount(1)2popcount(2)3popcount(3)⋯⋯log(V)popcount(log(V)))(123⋯log(V)popcount(1)popcount(2)popcount(3)⋯popcount(log(V))).
并且多次 popcount 操作等价于对置换进行多次乘法。
假设在这些 popcount 操作中间出现区间加法，形式上等价于 f(popcount(x+A))+Bf(popcount(x+A))+B.
所以只需要合理地对置换和加法标记进行合并。
当只有置换标记的时候，只需要简单复合两种置换标记。
假设当前是区间置换，那么在下一次区间置换前进行的区间加法一定是非负整数次。只需要维护加法标记。
下一次区间置换显然需要清空整个区间的加法标记。这里只能大力向下清空子树的标记，然后再重新给区间打上置换标记。
对于清空子树外的操作，显然复杂度为 O(nlogn)O(nlogn)。上面的复杂度看起来很劣，考虑分析一下清空子树的复杂度。
清空子树只需要递归到第一个有置换标记的结点。记这些结点为终止结点，令势能为终止结点的个数。
每次操作至多增加 O(logn)O(logn) 个终止结点，共 O(qlogn)O(qlogn) 个；每次 push_down 至多增加 22 个终止结点，总数也是 O(qlogn)O(qlogn).
清空两个终止结点的复杂度是 O(logV)O(logV)，所以复杂度均摊下来是 O(nlogn+qlognlogV)O(nlogn+qlognlogV).
代码
hide code#include<cstdio>
usingnamespace std;
typedeflonglong ll;
constint maxn = 3e5 + 5;
constint lg_sz = 32;
constint sgt_sz = maxn << 2;
int n, q;
int a[maxn];
namespace SGT
{
#define ls (k << 1)
#define rs (k << 1 | 1)
int per[sgt_sz][lg_sz];
ll tag[sgt_sz];
bool comp[sgt_sz];
voidbuild(int k, int l, int r)
{
for (int i = 0; i < lg_sz; i++) per[k][i] = i;
if (l == r) return tag[k] = a[l], comp[k] = true, void();
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
}
voidcls_tag(int k)
{
for (int i = 0; i < lg_sz; i++) per[k][i] = __builtin_popcountll(per[k][i] + tag[k]);
tag[k] = 0;
}
voidpush_down(int k)
{
if (comp[k])
{
for (int i = 0; i < lg_sz; i++) per[ls][i] = per[k][per[ls][i]], per[rs][i] = per[k][per[rs][i]];
for (int i = 0; i < lg_sz; i++) per[k][i] = i;
comp[ls] = comp[rs] = true, comp[k] = false;
}
if (tag[k]) tag[ls] += tag[k], tag[rs] += tag[k], tag[k] = 0;
}
voidcls_comp(int k, int l, int r)
{
if (comp[k]) returncls_tag(k), void();
push_down(k);
int mid = (l + r) >> 1;
cls_comp(ls, l, mid), cls_comp(rs, mid + 1, r);
}
voidupd_comp(int k, int l, int r, int ql, int qr)
{
if ((l >= ql) && (r <= qr)) returncls_comp(k, l, r), comp[k] = true, void();
push_down(k);
int mid = (l + r) >> 1;
if (ql <= mid) upd_comp(ls, l, mid, ql, qr);
if (qr > mid) upd_comp(rs, mid + 1, r, ql, qr);
}
voidupd_tag(int k, int l, int r, int ql, int qr, int w)
{
if ((l >= ql) && (r <= qr)) return tag[k] += w, void();
push_down(k);
int mid = (l + r) >> 1;
if (ql <= mid) upd_tag(ls, l, mid, ql, qr, w);
if (qr > mid) upd_tag(rs, mid + 1, r, ql, qr, w);
}
ll query(int k, int l, int r, int p)
{
if (l == r) return per[k][0] + tag[k];
push_down(k);
int mid = (l + r) >> 1;
if (comp[k])
{
if (p <= mid) return per[k][query(ls, l, mid, p)] + tag[k];
return per[k][query(rs, mid + 1, r, p)] + tag[k];
}
if (p <= mid) returnquery(ls, l, mid, p) + tag[k];
returnquery(rs, mid + 1, r, p) + tag[k];
}
}
usingnamespace SGT;
intmain()
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
while (q--)
{
int l, r, v;
char ch = getchar();
while ((ch < 'A') || (ch > 'Z')) ch = getchar();
if (ch == 'A') scanf("%d%d%d", &l, &r, &v), upd_tag(1, 1, n, l, r, v);
elseif (ch == 'P') scanf("%d%d", &l, &r), upd_comp(1, 1, n, l, r);
elsescanf("%d", &l), printf("%lld\n", query(1, 1, n, l));
// puts("done");
}
return0;
}
