KIDx的解题报告
题目链接:http://lightoj.com/volume_showproblem.php?problem=1164
题意:区间内初始时全部为0
命令1:0 x y v; 从x到y全部+v
命令2:1 x y; 输出x到y的值的总和
典型lazy的应用
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define inf 0x3fffffff
#define M 100005
#define LL long long
#define Max 26
struct Node{
int l, r; //sum是l到r的总和
LL v, sum; //v积累要加的数,需要往下时才更新儿子:lazy标记
}N[M<<2];
void create (int u, int a, int b)
{
N[u].l = a, N[u].r = b, N[u].v = N[u].sum = 0;
if (a == b) return ;
int mid = (a + b) >> 1, lc = u+u, rc = lc+1;
create (lc, a, mid);
create (rc, mid+1, b);
}
void update (int u, int a, int b, LL c)
{
if (a <= N[u].l && b >= N[u].r)
{
N[u].v += c;
N[u].sum += c * (N[u].r-N[u].l+1); //注意积累是用+=
return ;
}
int lc = u+u, rc = lc+1;
if (N[u].v > 0) //lazy一下,需要访问我儿子,我才去更新
{
N[lc].v += N[u].v;
N[lc].sum += N[u].v * (N[lc].r-N[lc].l+1);
N[rc].v += N[u].v;
N[rc].sum += N[u].v * (N[rc].r-N[rc].l+1);
N[u].v = 0;
}
if (a <= N[lc].r)
update (lc, a, b, c);
if (b >= N[rc].l)
update (rc, a, b, c);
N[u].sum = N[lc].sum + N[rc].sum;
}
LL find (int u, int a, int b) //和比较大,要用long long
{
if (a <= N[u].l && b >= N[u].r)
return N[u].sum;
LL m1 = 0, m2 = 0;
int lc = u+u, rc = lc+1;
if (N[u].v > 0) //同理lazy一下
{
N[lc].v += N[u].v;
N[lc].sum += N[u].v * (N[lc].r-N[lc].l+1);
N[rc].v += N[u].v;
N[rc].sum += N[u].v * (N[rc].r-N[rc].l+1);
N[u].v = 0;
}
if (a <= N[lc].r)
m1 = find (lc, a, b);
if (b >= N[rc].l)
m2 = find (rc, a, b);
return m1+m2;
}
int main()
{
LL c;
int t, cc = 1, n, q, k, a, b;
scanf ("%d", &t);
while (t--)
{
scanf ("%d%d", &n, &q);
create (1, 1, n);
printf ("Case %d:\n", cc++);
while (q--)
{
scanf ("%d%d%d", &k, &a, &b);
a++, b++;
if (k) printf ("%lld\n", find (1, a, b));
else scanf ("%lld", &c), update (1, a, b, c);
}
}
return 0;
}
分享到:
相关推荐
关于一些典型的线段树的例题,大家可以看一看,给一个评价,这些内容,后续我也会在博客上慢慢更新。希望大家多多的支持作者,谢谢! 这篇内容主要包含了一些我写的线段树的代码,可以帮助大家更好的理解线段树建树...
原理就大概如图所示,线段树的每个节点都是原数组的一段区间和,而叶子节点就是原数组对应 的值 建树代码: void build(int p,int lf,int rt){//建树 ans[p]=0; if(lf==rt) { ans[p]=A[lf]; return ; } int mid...
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
Lazy
jQuery_lazyload插件示例Demo
Lazy_Theta_star是在 Theta_star上的进一步改进,Theta_star是当节点加入open表时和当前点的父节点进行比较g值是否更小,对一些不必要的节点计算浪费了时间,而Lazy_Theta_star则是在弹出open表后进行比较,减少了...
Lazyload是通过延迟加载来实现按需加载,达到节省资源,加快浏览速度的目的。 网上也有不少类似的效果,这个Lazyload主要特点是: 支持使用window(窗口)或元素作为容器对象; 对静态(位置大小不变)元素做了大量...
lazyload, JavaScript, 图片懒加载, h5
Lazy Load 是一个用 JavaScript 编写的 jQuery 插件. 它可以延迟加载长页面中的图片. 在浏览器可视区域外的图片不会被载入, 直到用户将页面滚动到它们所在的位置. 这与图片预加载的处理方式正好是相反的. 在包含很多...
图片懒加载lazyload,增快页面访问速度。
Lazy Load Plugin for jQuery
lazyload技术内幕,当下最流行的图片浏览技术
lazyload-2.x 最新版本包括api使用
JQuery Lazyload加载图片实例
很好的资源,快来下载,里面有经典的例子。让开发lazy起来吧
macOS Mojave 10.14 18A391 Lazy Installer.cdr
Lazyload图片延迟加载效果
优化网站加载速度,使用lazyload.js,有完整的demo,有jquery.lazyload.js和jquery-1.11.0.min.js
lazyload使用案例及DEMO,里面包含了lazyload.js,一些测试图片,jquery.js。开箱即用!2020.06.22更新降低下载积分需求,我个人原意是免费下载的,奈何网站规则不允许!
Hibernate 的 lazyload 在FLEX中的解决方法例子 用的是gilead 因为LIB包太大上传很慢所以被我删掉了。