noip模拟赛 三部曲
2024-08-31 03:42:50
分析:子树上操作,要用到线段树+dfs序,关键就是子树内k还要增加,这个就不是很好办.可以求出在根节点+0后每个点会加多少,记为d[i],如果要对点x进行A操作,实际上只需要对子树加k - d[i]再加上子树的d[i]和,但是在实际求答案的时候不能直接求出子树和+Σd[i],因为如果你没有修改的话答案本该是0,程序却会输出一个数.因此还要维护一个线段树,记录Σd[i],每次在修改操作的时候将信息合并到第一个线段树上.还要注意的是每个点加的次数不同Σd[i]对答案是有影响的,不能单单只下传一个增加标记,还要记录当前节点增加了多少次,如果点x增加k,那么它的子节点就要增加(k - d[x]) * son[x] + Σd[son[x]] * cnt[x],son[x]为x的子节点,cnt[x]为x增加了多少次.
这道题比较麻烦,要很快反应过来这道题用dfs序+线段树来做,把每次增加变成在一个标准量上增加.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; const int maxn = ; typedef long long ll; ll dfs_clock, n, p, head[maxn], to[maxn * ],d[maxn], nextt[maxn * ], tot = ;
ll l[maxn], r[maxn], v[maxn], c[maxn << ], tag[maxn << ], L[maxn << ], R[maxn << ], c2[maxn << ], cnt[maxn << ]; void add(ll x, ll y)
{
to[tot] = y;
nextt[tot] = head[x];
head[x] = tot++;
} void dfs(ll u, ll dep)
{
v[u] += dep;
l[u] = ++dfs_clock;
d[dfs_clock] = dep;
for (int i = head[u]; i; i = nextt[i])
{
int vv = to[i];
dfs(vv, dep + );
v[u] += v[vv];
}
r[u] = dfs_clock;
} void pushup2(int o)
{
c2[o] = c2[o * ] + c2[o * + ];
} void pushup(int o)
{
c[o] = c[o * ] + c[o * + ];
} void pushdown(int o)
{
if (cnt[o])
{
tag[o * ] += tag[o];
tag[o * + ] += tag[o];
cnt[o * ] += cnt[o];
cnt[o * + ] += cnt[o];
c[o * ] += tag[o] * (R[o * ] - L[o * ] + ) + cnt[o] * c2[o * ];
c[o * + ] += tag[o] * (R[o * + ] - L[o * + ] + ) + cnt[o] * c2[o * + ];
tag[o] = cnt[o] = ;
}
} void build(int o, int l, int r)
{
L[o] = l;
R[o] = r;
if (l == r)
{
c2[o] = d[l];
return;
}
int mid = (l + r) >> ;
build(o * , l, mid);
build(o * + , mid + , r);
pushup2(o);
} void update(int o, int l, int r, int x, int y, int p)
{
if (x <= l && r <= y)
{
tag[o] += p;
cnt[o]++;
c[o] += p * (r - l + ) + c2[o];
return;
}
pushdown(o);
int mid = (l + r) >> ;
if (x <= mid)
update(o * , l, mid, x, y, p);
if (y > mid)
update(o * + , mid + , r, x, y, p);
pushup(o);
} ll query(int o, int l, int r, int x, int y)
{
if (x <= l && r <= y)
return c[o];
pushdown(o);
int mid = (l + r) >> , res = ;
if (x <= mid)
res += query(o * , l, mid, x, y);
if (y > mid)
res += query(o * + , mid + , r, x, y);
return res;
} int main()
{
scanf("%lld%lld", &n, &p);
for (int i = ; i <= n; i++)
{
int u;
scanf("%d", &u);
add(u, i);
}
for (int i = ; i <= n; i++)
if (!l[i])
dfs(i, );
build(, , n);
while (p--)
{
char ch[];
int x, k;
scanf("%s", ch);
if (ch[] == 'A')
{
scanf("%d%d", &x, &k);
k -= d[l[x]];
update(, , n, l[x], r[x], k);
}
else
{
scanf("%d", &x);
printf("%lld\n", query(, , n, l[x], r[x]));
}
} return ;
}
最新文章
- Hibernate4.2.4入门(二)——一对多的映射关系
- Eclipse 启动出现错误 no java virtual machine was found
- spring+mybatis整合读取不了配置文件
- ajax请求后加额外的数据
- Languages
- linux中fork()函数详解(原创!!实例讲解)
- (原创)如何在spannableString中使用自定义字体
- Bzoj 2393: Cirno的完美算数教室 容斥原理,深搜
- Yslow-23条规则编辑
- Maven合并多个war包的工程需要用到的插件
- 安全相关及HttpClient
- Some untracked working tree files would be overwritten by checkout. 		Please move or remove them before you can checkout. View them
- dfs1321
- python基础入门学习1
- Unity读取配置文件
- mysql where语句多条件查询是and和or联合使用bug
- MVC框架以及实例(补充)
- Canvas路径方向
- 常见协议基础知识总结--FTP协议
- Github 配置 SSH