博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU4578 线段树(区间更新 + 多种操作)
阅读量:6294 次
发布时间:2019-06-22

本文共 5726 字,大约阅读时间需要 19 分钟。

  题目链接:  , 线段树的区间更新 + 多种操作,好题。

  虽然是比较裸的线段树,但是比较麻烦,并且有很多细节需要考虑,最后我7.3s很惊险地过了,求大神告知优化方法。

 


 

  这道题坑在有三种询问:set , add , mul。所以lazy标记要有三个,如果三个标记同时出现的处理方法——当更新set操作时,就把add标记和mul标记全部取消;当更新mul操作时,如果当前节点add标记存在,就把add标记改为:add * mul。这样的话就可以在PushDown()操作中先执行set,然后mul,最后add。

  麻烦在有三种询问:和 , 平方和 , 立方和。对于set和mul操作来说,这三种询问都比较好弄。

  对于add操作,和的话就比较好弄,按照正常方法就可以;

  平方和这样来推:(a + c)2 = a2 + c2 + 2ac  , 即sum2[rt] = sum2[rt] + (r - l + 1) * c * c + 2 * sum1[rt] * c;

  立方和这样推:(a + c)3 = a3 + c3 + 3a(a2 + ac) , 即sum3[rt] = sum3[rt] + (r - l + 1) * c * c * c + 3 * c * (sum2[rt] + sum1[rt] * c);

  几个注意点:add标记取消的时候是置0,mul标记取消的时候是置1;在PushDown()中也也要注意取消标记,如set操作中取消add和mul,mul操作中更新add; 在add操作中要注意sum3 , sum2 , sum1的先后顺序,一定是先sum3 , 然后sum2 , 最后sum1; int容易爆,还是用LL要保险一点; 最后就是运算较多,不要漏掉东西。

 

#include 
#include
#include
#include
#include
#include
#include
using namespace std;#define LL __int64#define eps 1e-8#define INF INT_MAX#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int MOD = 10007; const int maxn = 100000 + 5;const int N = 12;LL add[maxn << 2] , set[maxn << 2] , mul[maxn << 2];LL sum1[maxn << 2] , sum2[maxn << 2] , sum3[maxn << 2];void PushUp(int rt){ sum1[rt] = (sum1[rt << 1] + sum1[rt << 1 | 1]) % MOD; sum2[rt] = (sum2[rt << 1] + sum2[rt << 1 | 1]) % MOD; sum3[rt] = (sum3[rt << 1] + sum3[rt << 1 | 1]) % MOD;}void build(int l , int r , int rt){ add[rt] = set[rt] = 0; mul[rt] = 1; if(l == r) { sum1[rt] = sum2[rt] = sum3[rt] = 0; return; } int m = (l + r) >> 1; build(lson); build(rson); PushUp(rt);}void PushDown(int rt , int len){ if(set[rt]) { set[rt << 1] = set[rt << 1 | 1] = set[rt]; add[rt << 1] = add[rt << 1 | 1] = 0; //注意这个也要下放 mul[rt << 1] = mul[rt << 1 | 1] = 1; LL tmp = ((set[rt] * set[rt]) % MOD) * set[rt] % MOD; sum1[rt << 1] = ((len - (len >> 1)) % MOD) * (set[rt] % MOD) % MOD; sum1[rt << 1 | 1] = ((len >> 1) % MOD) * (set[rt] % MOD) % MOD; sum2[rt << 1] = ((len - (len >> 1)) % MOD) * ((set[rt] * set[rt]) % MOD) % MOD; sum2[rt << 1 | 1] = ((len >> 1) % MOD) * ((set[rt] * set[rt]) % MOD) % MOD; sum3[rt << 1] = ((len - (len >> 1)) % MOD) * tmp % MOD; sum3[rt << 1 | 1] = ((len >> 1) % MOD) * tmp % MOD; set[rt] = 0; } if(mul[rt] != 1) { //这个就是mul[rt] != 1 , 当时我这里没注意所以TLE了 mul[rt << 1] = (mul[rt << 1] * mul[rt]) % MOD; mul[rt << 1 | 1] = (mul[rt << 1 | 1] * mul[rt]) % MOD; if(add[rt << 1]) //注意这个也要下放 add[rt << 1] = (add[rt << 1] * mul[rt]) % MOD; if(add[rt << 1 | 1]) add[rt << 1 | 1] = (add[rt << 1 | 1] * mul[rt]) % MOD; LL tmp = (((mul[rt] * mul[rt]) % MOD * mul[rt]) % MOD); sum1[rt << 1] = (sum1[rt << 1] * mul[rt]) % MOD; sum1[rt << 1 | 1] = (sum1[rt << 1 | 1] * mul[rt]) % MOD; sum2[rt << 1] = (sum2[rt << 1] % MOD) * ((mul[rt] * mul[rt]) % MOD) % MOD; sum2[rt << 1 | 1] = (sum2[rt << 1 | 1] % MOD) * ((mul[rt] * mul[rt]) % MOD) % MOD; sum3[rt << 1] = (sum3[rt << 1] % MOD) * tmp % MOD; sum3[rt << 1 | 1] = (sum3[rt << 1 | 1] % MOD) * tmp % MOD; mul[rt] = 1; } if(add[rt]) { add[rt << 1] += add[rt]; //add是+= , mul是*= add[rt << 1 | 1] += add[rt]; LL tmp = (add[rt] * add[rt] % MOD) * add[rt] % MOD; //注意sum3 , sum2 , sum1的先后顺序 sum3[rt << 1] = (sum3[rt << 1] + (tmp * (len - (len >> 1)) % MOD) + 3 * add[rt] * ((sum2[rt << 1] + sum1[rt << 1] * add[rt]) % MOD)) % MOD; sum3[rt << 1 | 1] = (sum3[rt << 1 | 1] + (tmp * (len >> 1) % MOD) + 3 * add[rt] * ((sum2[rt << 1 | 1] + sum1[rt << 1 | 1] * add[rt]) % MOD)) % MOD; sum2[rt << 1] = (sum2[rt << 1] + ((add[rt] * add[rt] % MOD) * (len - (len >> 1)) % MOD) + (2 * sum1[rt << 1] * add[rt] % MOD)) % MOD; sum2[rt << 1 | 1] = (sum2[rt << 1 | 1] + (((add[rt] * add[rt] % MOD) * (len >> 1)) % MOD) + (2 * sum1[rt << 1 | 1] * add[rt] % MOD)) % MOD; sum1[rt << 1] = (sum1[rt << 1] + (len - (len >> 1)) * add[rt]) % MOD; sum1[rt << 1 | 1] = (sum1[rt << 1 | 1] + (len >> 1) * add[rt]) % MOD; add[rt] = 0; }}void update(int L , int R , int c , int ch , int l , int r , int rt){ if(L <= l && R >= r) { if(ch == 3) { set[rt] = c; add[rt] = 0; mul[rt] = 1; sum1[rt] = ((r - l + 1) * c) % MOD; sum2[rt] = ((r - l + 1) * ((c * c) % MOD)) % MOD; sum3[rt] = ((r - l + 1) * (((c * c) % MOD) * c % MOD)) % MOD; } else if(ch == 2) { mul[rt] = (mul[rt] * c) % MOD; if(add[rt]) add[rt] = (add[rt] * c) % MOD; sum1[rt] = (sum1[rt] * c) % MOD; sum2[rt] = (sum2[rt] * (c * c % MOD)) % MOD; sum3[rt] = (sum3[rt] * ((c * c % MOD) * c % MOD)) % MOD; } else if(ch == 1) { add[rt] += c; LL tmp = (((c * c) % MOD * c) % MOD * (r - l + 1)) % MOD; //(r - l + 1) * c^3 sum3[rt] = (sum3[rt] + tmp + 3 * c * ((sum2[rt] + sum1[rt] * c) % MOD)) % MOD; sum2[rt] = (sum2[rt] + (c * c % MOD * (r - l + 1) % MOD) + 2 * sum1[rt] * c) % MOD; sum1[rt] = (sum1[rt] + (r - l + 1) * c) % MOD; } return; } PushDown(rt , r - l + 1); int m = (l + r) >> 1; if(L > m) update(L , R , c , ch , rson); else if(R <= m) update(L , R , c , ch , lson); else { update(L , R , c , ch , lson); update(L , R , c , ch , rson); } PushUp(rt);}LL query(int L , int R , int p , int l , int r , int rt){ if(L <= l && R >= r) { if(p == 1) return sum1[rt] % MOD; else if(p == 2) return sum2[rt] % MOD; else return sum3[rt] % MOD; } PushDown(rt , r - l + 1); int m = (l + r) >> 1; if(L > m) return query(L , R , p , rson); else if(R <= m) return query(L , R , p , lson); else return (query(L , R , p , lson) + query(L , R , p , rson)) % MOD;}int main(){ int n , m; int a , b , c , ch; while(~scanf("%d %d" , &n , &m)) { if(n == 0 && m == 0) break; build(1 , n , 1); while(m--) { scanf("%d %d %d %d" , &ch , &a , &b , &c); if(ch != 4) { update(a , b , c , ch , 1 , n , 1); } else { printf("%I64d\n" , query(a , b , c , 1 , n , 1)); } } } return 0;}

 

转载于:https://www.cnblogs.com/H-Vking/p/4297973.html

你可能感兴趣的文章
idea的maven项目,install下载重复下载本地库中已有的jar包,而且下载后jar包都是lastupdated问题...
查看>>
2019测试指南-web应用程序安全测试(二)指纹Web服务器
查看>>
树莓派3链接wifi
查看>>
js面向对象编程
查看>>
Ruby中类 模块 单例方法 总结
查看>>
jQuery的validate插件
查看>>
5-4 8 管道符 作业控制 shell变量 环境变量配置
查看>>
Enumberable
查看>>
开发者论坛一周精粹(第五十四期) 求购备案服务号1枚!
查看>>
validate表单验证及自定义方法
查看>>
javascript 中出现missing ) after argument list的错误
查看>>
使用Swagger2构建强大的RESTful API文档(2)(二十三)
查看>>
Docker容器启动报WARNING: IPv4 forwarding is disabled. Networking will not work
查看>>
(转)第三方支付参与者
查看>>
程序员修炼之道读后感2
查看>>
DWR实现服务器向客户端推送消息
查看>>
js中forEach的用法
查看>>
Docker之功能汇总
查看>>
!!a标签和button按钮只允许点击一次,防止重复提交
查看>>
(轉貼) Eclipse + CDT + MinGW 安裝方法 (C/C++) (gcc) (g++) (OS) (Windows)
查看>>