P2184 贪婪大陆 线段树 + 区间覆盖
发布日期:2021-09-25 23:57:52 浏览次数:8 分类:技术文章

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

题意:每次给定一个区间,有两个操作

(1)区间炸弹的种类数 + 1
(2)查询区间的不同炸弹种类数

仔细想想可以想到,可以转换成求一个区间内不同区间覆盖的最大次数,以前做过很多类似的题,大体思想就是把 l 的位置 + 1 ,r + 1 的位置 - 1 ,这个题也是类似,用线段树维护区间左端起点的值和右端起点的值,对于每次添加的区间,l 和 r 的位置都 + 1 。每次查询的区间,用 lsum ( 1 ~ r ) - rsum ( 1 ~ ( l -1 ) ) ,也就是起点减去终点,就可以得到区间内最大的覆盖次数。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)using namespace std;typedef long long LL;typedef pair
PII;const int N=100010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;struct Node{ int l,r; int lsum,rsum;}tr[N<<2];void pushup(int u){ tr[u].lsum=tr[L].lsum+tr[R].lsum; tr[u].rsum=tr[L].rsum+tr[R].rsum;}void build(int u,int l,int r){ tr[u]={ l,r,0,0}; if(l==r) return; build(L,l,Mid),build(R,Mid+1,r);}void modify(int u,int l,int r,int c){ if(tr[u].l>=l&&tr[u].r<=r) { if(c==1) tr[u].lsum+=1; else tr[u].rsum+=1; return; } if(l<=Mid) modify(L,l,r,c); else modify(R,l,r,c); pushup(u);}int query(int u,int l,int r,int op){ if(tr[u].l>=l&&tr[u].r<=r) { if(op==1) return tr[u].lsum; else return tr[u].rsum; } int t=0; if(l<=Mid) t+=query(L,l,r,op); if(r>Mid) t+=query(R,l,r,op); return t;}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); cin>>n>>m;; build(1,1,n); while(m--) { int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op==1) modify(1,l,l,1),modify(1,r,r,2); else printf("%d\n",query(1,1,r,1)-query(1,1,l-1,2)); } return 0;}

转载地址:https://blog.csdn.net/DaNIelLAk/article/details/106304213 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:POJ - 2728 Desert King 最小生成树 + 01分数规划
下一篇:upc 兔 最小生成树

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年03月01日 13时43分05秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql分组显示行号_mysql 显示行号,以及分组排序 2019-04-21
MySQL常见的主从复制架构_如何搭建经典的MySQL 主从复制架构 2019-04-21
编写python程序、计算账户余额_小明有20w存款存在余额宝中,按余额宝年收益为3.35%计算,用Python编写程序计算,多少年后小明的存款达到30w?... 2019-04-21
python 公众号引流_公众号引流方法有哪些? 2019-04-21
java 减少内存_java中减少内存占用小技巧 2019-04-21
centos 7 mysql图形界面_centos7-vnstat图形界面搭建 2019-04-21
java 防渗透_「java、工程师工作经验怎么写」-看准网 2019-04-21
java中跳出当前循环怎么做_在java中,如何跳出当前的多重循环? 2019-04-21
java程序中执行maven_java – 将一个enviornment变量传递给Maven中的已执行进程 2019-04-21
java16下载_java lombok下载 2019-04-21
python 图像处理与识别书籍_Python图像处理之识别图像中的文字(实例讲解) 2019-04-21
java安全初始化_java安全编码指南之:声明和初始化 2019-04-21
java jstat gc_分析JVM GC及内存情况的方法 2019-04-21
php pclzip.lib.php,php使用pclzip类实现文件压缩的方法(附pclzip类下载地址) 2019-04-21
php dns更新,php_mzdns: 站群,大量域名 通过 dns 服务商 api 批量添加 ip 工具。你懂的~ 基于 mzphp2 框架。... 2019-04-21
jdk 1.8 java.policy,JDK1.8 导致系统报错:java.security.InvalidKeyException:illegal Key Size 2019-04-21
php linux权限,Linux权限详细介绍 2019-04-21
典型环节的matlab仿真分析,典型环节的MATLAB仿真.doc 2019-04-21
Php contenttype类型,各种类型文件的Content Type 2019-04-21
php使用redis持久化,redis如何持久化 2019-04-21