Codechef 13.2 QUERY 可持久化线段树+可持久化数据结构+标记永久化
shinbokuow
posted @ Nov 20, 2015 04:24:04 PM
in Something
with tags
可持久化线段树 可持久化数据结构 标记永久化
, 1348 阅读
题目大意：
给定一棵$n$个点，点上有点权的树，支持在路径上加上一个等差数列，询问路径上的点权之和，还要支持版本回溯操作。
数据范围$n,Q\leq{10^5}$，等差数列的首项、公差均$\leq{1000}$。
算法讨论：
考虑如何在序列的一个区间上加上一个等差数列，我们可以利用线段树维护，并设延迟标记$(a,b)$表示在线段树节点对应的区间上加上一个首项为$a$，公差为$b$的等差数列。这个标记能够很容易地下传，不妨令左儿子区间的长度为$l$，那我们将标记$(a,b)$下传，只需要在左儿子上打上$(a,b)$的标记，并在右儿子上打上$(a+lb,b)$的标记。并且利用标记能够$O(1)$更新答案。这样就解决了序列上的问题。
将序列问题拓展到树上，只需要用到轻重链树链剖分，将路径上的操作转化为$O(\log n)$个序列上的操作，这样就能在$O(n\log ^2n)$的时间内解决这个问题。
注意到还需要将数据结构可持久化，我们只需要将用到的线段树可持久化即可，那么空间复杂度$O(n\log ^2n)$。
在将线段树可持久化的时候，由于每走到一个结点，在下传标记的时候都必须新建儿子节点，空间的常数很大。而注意到这里的标记是可加的，我们可以将标记永久化，即不下传标记，进行修改时只在完全覆盖的节点上打上标记，同时更新这个节点到根节点上的路径上的信息；查询时在递归过程中维护一个根节点到这个节点的路径上的标记的和，当区间完全覆盖节点时，返回这个节点的答案再加上维护的标记对于这个节点产生的贡献。这样就不用下传标记了，减小了空间的常数。
时空复杂度：
时间复杂度$O(Q\log ^2n)$，空间复杂度$O(Q\log ^2n)$。
代码：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int getc() {
static const int L = 1 << 15;
static char buf[L], *S = buf, *T = buf;
if (S == T) {
T = (S = buf) + fread(buf, 1, L, stdin);
if (S == T)
return EOF;
}
return *S++;
}
int getint() {
static int c, x;
while (!isdigit(c = getc()));
x = c - '0';
while (isdigit(c = getc()))
x = (x << 1) + (x << 3) + c - '0';
return x;
}
int getch() {
static int c;
while ((c = getc()) != 'c' && c != 'q' && c != 'l');
return c;
}
char buf[100010 * 21], *o = buf;
void print(ll x) {
static short stack[21], top;
if (!x)
*o++ = '0';
else {
top = 0;
while (x)
stack[top++] = x % 10, x /= 10;
while (top--)
*o++ = stack[top];
}
*o++ = '\n';
}
#define ls(x) S[x].l
#define rs(x) S[x].r
struct Node {
int l, r, suma, sumb;
ll ans;
}S[15000010];
int cnt;
ll calcTotal(ll a, ll b, ll len) {
return a * len + len * (len - 1) * b / 2;
}
int insert(int last, int tl, int tr, int dl, int dr, int a, int b) {
int q = ++cnt;
S[q] = S[last];
S[q].ans += calcTotal(a, b, dr - dl + 1);
if (dl <= tl && tr <= dr) {
S[q].suma += a;
S[q].sumb += b;
return q;
}
int mid = (tl + tr) >> 1;
if (dr <= mid)
ls(q) = insert(ls(last), tl, mid, dl, dr, a, b);
else if (dl > mid)
rs(q) = insert(rs(last), mid + 1, tr, dl, dr, a, b);
else {
ls(q) = insert(ls(last), tl, mid, dl, mid, a, b);
rs(q) = insert(rs(last), mid + 1, tr, mid + 1, dr, a + (mid + 1 - dl) * b, b);
}
return q;
}
ll query(int q, int tl, int tr, int dl, int dr, ll a, ll b) {
if (dl <= tl && tr <= dr)
return S[q].ans + calcTotal(a, b, tr - tl + 1);
int mid = (tl + tr) >> 1;
if (dr <= mid)
return query(ls(q), tl, mid, dl, dr, a + S[q].suma, b + S[q].sumb);
else if (dl > mid)
return query(rs(q), mid + 1, tr, dl, dr, a + S[q].suma + (b + S[q].sumb) * (mid + 1 - tl), b + S[q].sumb);
else
return query(ls(q), tl, mid, dl, mid, a + S[q].suma, b + S[q].sumb) +
query(rs(q), mid + 1, tr, mid + 1, dr, a + S[q].suma + (b + S[q].sumb) * (mid + 1 - tl), b + S[q].sumb);
}
#define N 100010
int n, Q;
int root[N];
int build(int tl, int tr) {
int q = ++cnt;
if (tl == tr)
return q;
int mid = (tl + tr) >> 1;
ls(q) = build(tl, mid);
rs(q) = build(mid + 1, tr);
return q;
}
int head[N], nxt[N << 1], to[N << 1];
void addedge(int a, int b) {
static int q = 1;
to[q] = b;
nxt[q] = head[a];
head[a] = q++;
}
void make(int a, int b) {
addedge(a, b);
addedge(b, a);
}
int pa[N], dep[N], siz[N], son[N];
void dfs(int x, int fa) {
int mx = 0;
siz[x] = 1;
for (int j = head[x]; j; j = nxt[j]) {
if (to[j] != fa) {
dep[to[j]] = dep[x] + 1;
pa[to[j]] = x;
dfs(to[j], x);
siz[x] += siz[to[j]];
if (siz[to[j]] > mx) {
mx = siz[to[j]];
son[x] = to[j];
}
}
}
}
int top[N], down[N], p_id[N], id_p[N], id;
void create(int x, int Top) {
top[x] = Top;
p_id[x] = ++id;
id_p[id] = x;
if (son[x])
create(son[x], Top);
else
down[Top] = x;
for (int j = head[x]; j; j = nxt[j])
if (to[j] != pa[x] && to[j] != son[x])
create(to[j], to[j]);
}
int length(int x, int y) {
static int ans;
ans = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]])
swap(x, y);
ans += dep[x] - dep[top[x]] + 1;
x = pa[top[x]];
}
if (dep[x] < dep[y])
swap(x, y);
ans += dep[x] - dep[y] + 1;
return ans;
}
int Modify(int ver, int x, int y, int a, int b) {
static int temp, lcount, rcount;
temp = root[ver];
lcount = 0;
rcount = length(x, y) - 1;
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) {
temp = insert(temp, 1, n, p_id[top[x]], p_id[x], a + (lcount + dep[x] - dep[top[x]]) * b, -b);
lcount += dep[x] - dep[top[x]] + 1;
x = pa[top[x]];
}
else {
temp = insert(temp, 1, n, p_id[top[y]], p_id[y], a + (rcount - (dep[y] - dep[top[y]])) * b, b);
rcount -= dep[y] - dep[top[y]] + 1;
y = pa[top[y]];
}
}
if (dep[x] > dep[y])
temp = insert(temp, 1, n, p_id[y], p_id[x], a + (lcount + dep[x] - dep[y]) * b, -b);
else
temp = insert(temp, 1, n, p_id[x], p_id[y], a + (rcount - (dep[y] - dep[x])) * b, b);
return temp;
}
ll Query(int ver, int x, int y) {
static ll ans;
ans = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]])
swap(x, y);
ans += query(root[ver], 1, n, p_id[top[x]], p_id[x], 0, 0);
x = pa[top[x]];
}
if (dep[x] < dep[y])
swap(x, y);
ans += query(root[ver], 1, n, p_id[y], p_id[x], 0, 0);
return ans;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
#endif
n = getint();
Q = getint();
int i, j, x, y, a, b;
for (i = 1; i < n; ++i) {
a = getint();
b = getint();
make(a, b);
}
dep[1] = 1;
dfs(1, -1);
create(1, 1);
for (i = 1; i <= n; ++i)
down[i] = down[top[i]];
int totver = 0, nowver = 0;
root[0] = build(1, n);
char type;
ll lastans = 0;
while (Q--) {
type = getch();
if (type == 'c') {
x = (lastans + getint()) % n + 1;
y = (lastans + getint()) % n + 1;
//x = getint();
//y = getint();
a = getint();
b = getint();
root[++totver] = Modify(nowver, x, y, a, b);
nowver = totver;
}
else if (type == 'q') {
x = (lastans + getint()) % n + 1;
y = (lastans + getint()) % n + 1;
//x = getint();
//y = getint();
printf("%lld\n", lastans = Query(nowver, x, y));
}
else {
nowver = (lastans + getint()) % (totver + 1);
}
}
return 0;
}
评论 (0)