https://nanti.jisuanke.com/t/31460
tree[rt].ans = tree[rt << 1].ans + tree[rt << 1 | 1].ans + tree[rt << 1].sum * tree[rt << 1 | 1].len;
注意询问时的合并操作
代码:
#include <iostream>
#include <cstdio>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = (int)1e5 + 5;
typedef long long ll;
using namespace std;
int n, q;
ll arr[maxn];
struct Tree {
ll sum, ans, len;
} tree[maxn << 2];
void pushup(int rt) {
tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
tree[rt].ans = tree[rt << 1].ans + tree[rt << 1 | 1].ans + tree[rt << 1].sum * tree[rt << 1 | 1].len;
}
void build(int l, int r, int rt) {
tree[rt].len = r - l + 1;
if (l == r) {
tree[rt].sum = tree[rt].ans = arr[l];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushup(rt);
}
void update(int p, ll val, int l, int r, int rt) {
if (l == r) {
tree[rt].ans = tree[rt].sum = val;
return;
}
int m = (l + r) >> 1;
if (p <= m) {
update(p, val, lson);
}
else {
update(p, val, rson);
}
pushup(rt);
}
ll _query(int L, int R, int l, int r, int rt) {
if (L <= l && R >= r) {
return tree[rt].sum;
}
int m = (l + r) >> 1;
ll res = 0;
if (L <= m) {
res += _query(L, R, lson);
}
if (R > m) {
res += _query(L, R, rson);
}
return res;
}
ll query(int L, int R, int l, int r, int rt) {
if (L <= l && R >= r) {
return tree[rt].ans;
}
int m = (l + r) >> 1;
if (L <= m && R > m) {
return query(L, m, lson) + query(m + 1, R, rson) + _query(L, m, lson) * (R - m);
}
else if (L <= m) {
return query(L, R, lson);
}
else {
return query(L, R, rson);
}
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%lld", &arr[i]);
}
build(1, n, 1);
while (q--) {
int op, a, b;
scanf("%d%d%d", &op, &a, &b);
if (op == 1) {
printf("%lld\n", query(a, b, 1, n, 1));
}
else {
update(a, b, 1, n, 1);
}
}
}
【线段树维护复杂状态】Ryuji doesn't want to study的更多相关文章
-
【8.26校内测试】【重构树求直径】【BFS模拟】【线段树维护DP】
题目性质比较显然,相同颜色联通块可以合并成一个点,重新建树后,发现相邻两个点的颜色一定是不一样的. 然后发现,对于一条链来说,每次把一个点反色,实际上使点数少了2个.如下图 而如果一条链上面有分支,也 ...
-
Codeforces GYM 100114 D. Selection 线段树维护DP
D. Selection Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/gym/100114 Descriptio ...
-
[BZOJ 3995] [SDOI2015] 道路修建 【线段树维护连通性】
题目链接:BZOJ - 3995 题目分析 这道题..是我悲伤的回忆.. 线段树维护连通性,与 BZOJ-1018 类似,然而我省选之前并没有做过 1018,即使它在 ProblemSet 的第一页 ...
-
CodeForces 343D 线段树维护dfs序
给定一棵树,初始时树为空 操作1,往某个结点注水,那么该结点的子树都注满了水 操作2,将某个结点的水放空,那么该结点的父亲的水也就放空了 操作3,询问某个点是否有水 我们将树进行dfs, 生成in[u ...
-
Codeforces 834D The Bakery【dp+线段树维护+lazy】
D. The Bakery time limit per test:2.5 seconds memory limit per test:256 megabytes input:standard inp ...
-
洛谷P4243/bzoj1558 [JSOI2009]等差数列(线段树维护差分+爆炸恶心的合并)
题面 首先感谢这篇题解,是思路来源 看到等差数列,就会想到差分,又有区间加,很容易想到线段树维护差分.再注意点细节,\(A\)操作完美解决 然后就是爆炸恶心的\(B\)操作,之前看一堆题解的解释都不怎 ...
-
hdu 5068 线段树维护矩阵乘积
http://acm.hdu.edu.cn/showproblem.php?pid=5068 题意给的略不清晰 m个询问:从i层去j层的方法数(求连段乘积)或者修改从x层y门和x+1层z门的状态反转( ...
-
bzoj 2124 等差子序列 (线段树维护hash)
2124: 等差子序列 Time Limit: 3 Sec Memory Limit: 259 MBSubmit: 1922 Solved: 714[Submit][Status][Discuss ...
-
BZOJ 2124: 等差子序列 线段树维护hash
2124: 等差子序列 Description 给一个1到N的排列{Ai},询问是否存在1<=p1=3),使得Ap1,Ap2,Ap3,…ApLen是一个等差序列. Input 输入的第一行包含一 ...
随机推荐
-
seq命令
seq 5 seq 5 >1.txt 其中的>是覆盖 seq 1 5 用来产生从数1到数5之间的所有整数 或, seq 5
-
将网页中的html代码的table保存成word文件
1.后台代码: string nowtime = DateTime.Now.ToString("yyyy-MM-dd"); Response.Clear(); Response.B ...
-
JAVA课程设计 计算器模拟程序 王华俊(201521123015)
1.团队课程设计博客链接 http://www.cnblogs.com/yuanj/p/7072137.html 2.个人负责模块或任务说明 GUI界面设计 各类之间拼接 3.自己的代码提交记录截图 ...
-
Nginx 负载均衡4种模式
转载请标明出处:http://blog.csdn.net/zhaoyanjun6/article/details/80541464 本文出自[赵彦军的博客] 4 种负载均衡算法 upstream 支持 ...
- 判断python字典中key是否存在
-
Python爬取新浪微博评论数据,写入csv文件中
因为新浪微博网页版爬虫比较困难,故采取用手机网页端爬取的方式 操作步骤如下: 1. 网页版登陆新浪微博 2.打开m.weibo.cn 3.查找自己感兴趣的话题,获取对应的数据接口链接 4.获取cook ...
-
批量导入数据到mssql数据库的
概述 批量导入数据到数据库中,我们有好几种方式. 从一个数据表里生成数据脚本,到另一个数据库里执行脚本 从EXCEL里导入数据 上面两种方式,导入的数据都会生成大量的日志.如果批量导入5W条数据到数据 ...
-
Haskell语言学习笔记(64)Lens(4)
安装 lens-tutorial Control.Lens.Tutorial $ cabal install lens-tutorial Installed lens-tutorial-1.0.3 P ...
-
ahjesus wp-autopost破解版,亲测可用
在funtion.php里 把fetchUrl 这个函数的判断去掉 直接执行判断为真的结果下面是修改后的函数 function fetchUrl($_var_22){ global $w ...
-
[BUAA OO]第三次博客作业
OO第三次博客作业 1. 规格化设计的发展 我认为,规格化设计主要源自于软件设计的两次危机.第一次是由于大量存在的goto语句,让当时被广泛应用的面向过程式的编程语言臃肿不堪,在逻辑性上与工程规模上鱼 ...