hdu4046 不错的线段树单点更新
更新 线段 单点 不错
2023-09-11 14:14:00 时间
题意:
给一个字符串,两种操作 0 a b 询问a,b之间有多少个wbw, 1 a c 就是把第a个改成c.
思路:
给一个字符串,两种操作 0 a b 询问a,b之间有多少个wbw, 1 a c 就是把第a个改成c.
思路:
这个题目我们可以用线段树的点更新来做,一开始写了个好长好长的线段树,pushup写了很长,每个节点7个变量,结果 "呵呵"。其实根本不用那么麻烦,我当时想的麻烦了,每个节点只有一个sum就行了,每个节点代表的是以当前这段的每个点为终点的wbw的个数,比如节点4,6那么当前的这个节点存的就是以4,5,6,为终点的wbw的个数(4,6最多三个),每次更新的时候改变当前的这个字母可能会影响三个权值改变,所以更新三次,具体看代码。
#include<stdio.h> #include<string.h> #define lson l ,mid ,t << 1 #define rson mid + 1 ,r ,t << 1 | 1 int sum[300000]; char num[55000]; void Pushup(int t) { sum[t] = sum[t<<1] + sum[t<<1|1]; } void BuidTree(int l ,int r ,int t) { sum[t] = 0; if(l == r) { if(l >= 3 && num[l] == 'w' && num[l-1] == 'b' && num[l-2] == 'w') sum[t] = 1; return ; } int mid = (l + r) >> 1; BuidTree(lson); BuidTree(rson); Pushup(t); } void Update(int l ,int r ,int t ,int a) { if(l == r) { if(num[l] == 'w' && num[l-1] == 'b' && num[l-2] == 'w') sum[t] = 1; else sum[t] = 0; return; } int mid = (l + r) >> 1; if(a <= mid) Update(lson ,a); else Update(rson ,a); Pushup(t); } int Query(int l ,int r ,int t ,int a ,int b) { if(a <= l && b >= r) return sum[t]; int mid = (l + r) >> 1; int Ans = 0; if(a <= mid) Ans = Query(lson ,a ,b); if(b > mid) Ans += Query(rson ,a ,b); return Ans; } int main () { int t ,n ,m ,a ,b ,c ,cas = 1; scanf("%d" ,&t); while(t--) { scanf("%d %d" ,&n ,&m); scanf("%s" ,num + 1); BuidTree(1 ,n ,1); printf("Case %d:\n" ,cas ++); while(m--) { scanf("%d" ,&a); if(!a) { scanf("%d %d" ,&b ,&c); b ++ ,c ++; if(c - b < 2) printf("0\n"); else printf("%d\n" ,Query(1 ,n ,1 ,b + 2 ,c)); } else { char str[5]; scanf("%d %s" ,&b ,str); num[++b] = str[0]; if(b >= 3) Update(1 ,n ,1 ,b); if(b + 1 >= 3 && b + 1 <= n) Update(1 ,n ,1 ,b + 1); if(b + 2 >= 3 && b + 2 <= n) Update(1 ,n ,1 ,b + 2); } } } return 0; }
相关文章
- hdu1698 线段树(区间更新~将区间[x,y]的值替换为z)
- poj 2777(线段树的节点更新策略)
- vs扩展和更新插件的开发
- 如何安装最新版本的 SAP ABAP Development Tool ( ADT ) 2021年度更新
- SAP CRM索引数据库表CRMD_ORDER_INDEX的更新原理
- Atitit 小程序前端api艾提拉总结 索引 目录 1. 基础372 1.1. 系统38更新 38小程序 39调试 41定时器 422 2. 路由432 3. 界面442 3.1.
- Flutter高级第4篇:inappbrowser、StatefulBuilder 更新 Flutter showDialog、showModalBottomSheet中的状态
- Database之SQLSever:SQLSever数据库管理学习并深入理解SQL命令语句进阶综合篇《初级→中级→高级》(持续更新,建议收藏)
- Paper之DL:深度学习高质量论文分类推荐(建议收藏,持续更新)
- Wikioi 1081 线段树成段更新单点查询
- Win11 22000.613(KB5012592)更新失败怎么办?
- Mybatis分页插件更新
- Golang服务器热重启、热升级、热更新(safe and graceful hot-restart/reload http server)详解
- 虚拟化之Proxmox VE更换apt源并更新软件包数据库
- kotlin与java的比较:数组(正在更新)