Codeforces 444C(线段树)

区间颜色不一致就更新到底,否则lazy标记

#include #include #include #include using namespace std; #define lc l,m,index>1; if(seg[index].add) { color(seg[index].col,seg[index].add,lc); color(seg[index].col,seg[index].add,rc); seg[index].add=0; } } void build(ll l,ll r,ll index) { ll m=(l+r)>>1; if(l==r) { seg[index].same=true; seg[index].col=l; seg[index].sum=0; return; } build(lc); build(rc); pushup(l,r,index); } void update(ll L,ll R,ll x,ll l,ll r,ll index) { ll m=(l+r)>>1; if(L==l&&R==r&&seg[index].same) { color(x,abs(seg[index].col-x),l,r,index); return; } pushdown(l,r,index); if(Rm)update(L,R,x,rc); else { update(L,m,x,lc); update(m+1,R,x,rc); } pushup(l,r,index); } ll query(ll L,ll R,ll l,ll r,ll index) { ll m=(l+r)>>1; if(L==l&&R==r)return seg[index].sum; pushdown(l,r,index); if(Rm)return query(L,R,rc); else return query(L,m,lc)+query(m+1,R,rc); } int main() { scanf("%I64d%I64d",&n,&m); build(1,n,1); while(m--) { ll op,a,b,c; scanf("%I64d",&op); if(op==1) { scanf("%I64d%I64d%I64d",&a,&b,&c); update(a,b,c,1,n,1); } else { scanf("%I64d%I64d",&a,&b); printf("%I64d\n",query(a,b,1,n,1)); } } return 0; }

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:POJ 1386 Play on Words
下一篇:hdu 3652 B-number(数位dp)
相关文章

poj1066巧妙的线段相交的应用

poj 1823 Hotel 线段树,注意懒惰标

poj 1410 矩形与线段相交判断

hdu 4339 Query 线段树 多校联合赛

poj 3667 Hotel 线段树 内存分配问题

线段树和单调队列优化DP---POJ2373解题

poj 3162 线段树 hdu 4123 bfs

[线段树]POJ 2374 Fence Obstacle

POJ 1823 Hotel 线段树 + lazy标签

HDU OJ 1754 I Hate It [线段树

图文推荐
Codeforces 444C(线段树)
ZOJ 3640 Help Me
Codeforces 444C(线段树)
CF 518C(Anya and
Codeforces 444C(线段树)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-07 人气:2
本文关键词:
分享到:

相关文章

  • CodeForces 444C DZY Loves Colors 2012-04-22

    题意: 一段区间a一开始是1、2、3、4……n这样的 每次1操作可以将[l,r]覆盖成x 同时得到abs(a[i]-x)的价值 2操作查询[l,r]的价值 思路: 线段树 又是一道加深线段树理解的题 操作2是简单的求和 线段树基本操作 难点在操作1 用cov表示该区间的值(如果为0说明是混合区间) 用val表示该区间的价值和 那么在更新时就不仅仅是找到 tree[i].l==l&&tree[i].r==r 就停止了 而是继续向下递归 直到一段区间的cov>0才结束 之所以这

  • hdu4882ZCC Loves Codefires(贪心) 2012-06-28

    题目链接: 啊哈哈,选我选我 题目: ZCC Loves Codefires Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 182 Accepted Submission(s): 97 Problem Description Though ZCC has many Fans, ZCC himself is a crazy Fan of a

  • POJ 1386 Play on Words 2013-11-13

    欧拉回路问题。 题意是说给你一些字符串,类似于成语接龙,上一个字符串尾字母必须和下一个字符串首字母相同。 把所有字符串连成一串。 根据定理判断欧拉通路,然后DFS判连通(并查集也可) 没注意题意 字符串开了str[100] 结果RE。结果字符串最长有1000.改了就AC了。 #include #include #include #include #include #include #include #include #include #include #include #include #def

  • Codeforces445B_DZY Loves Chemistry(DFS) 2014-04-17

    DZY Loves Chemistry time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output DZY loves chemistry, and he enjoys mixing chemicals. DZY has n chemicals, and m pairs of them will react. He wants to pou

  • codeforces 448C Painting Fence 2012-01-01

    刷篱笆,只有横和竖, 竖着肯定最多是 n , 另一种 那么每一次先把最下面的那个刷掉, 刷掉之后 , 继续把上面的 刷掉,, 每一次把 剩下的 再按横着或竖着 刷 就是分治了 #include #include #include #include using namespace std; #define inf 0x7f7f7f7f int a[6000]; int n; int ans; int len; int dfs(int l,int r) { int i,mina = inf; int

  • Codeforces 432 D. Prefixes and Suffixes 2012-01-10

    ?ㄦ?╁?KMP??绠???????.... D. Prefixes and Suffixes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output You have a string s????em>s1s2...s|s|, where |s| is the length of string s, and si its i-t

  • Codeforces Round #262 (Div. 2) 2012-01-13

    Codeforces Round #262 (Div. 2) A:水题,直接不断模拟即可 B:由于s(x)大小最大到1e9,所以数位和最多为81,这样只要枚举s(x),就只要枚举1到81即可,然后在计算出x,判断是否符合,符合就加进答案 C:二分高度,然后判断的时候for一遍,每次不符合的位置就去浇水,从左往右推一遍即可 D:构造,如果k >= 5, 那么就可以直接放偶数,奇数,偶数,奇数,由于偶数和偶数+1异或必然为1,所以这样放4个异或和就到最小的0了,然后k = 1,2,4都可以特判

  • Codeforces Round #270 A-D 2012-01-16

    Codeforces Round #270 A. Design Tutorial: Learn from Math time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output One way to create a task is to learn from math. You can generate some random math s

  • Codeforces 208 B. Solitaire 2012-01-21

    记忆化搜索 dp【还剩下几个】【倒1】【倒2】【倒3】 CF JAVA中 public static class 前面好像不能再开类了,连注释掉的类也不可以,好像是个BUG??? B. Solitaire time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output A boy named Vasya wants to play an ol

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.096 (s). 10 q(s)