热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HDU6521Party(SYSU校赛K题)(线段树)

题目链接题意:n个人排成一列,一开始他们互不认识,每次选[l,r]上的人开party,使他们互相认识,求出每次

题目链接

题意:n个人排成一列,一开始他们互不认识,每次选[l,r]上的人开party,使他们互相认识,求出每次party之后新互相认识的人的对数。

思路:把“互相认识”变成单向连边,只考虑左边的人对右边的贡献。对于每个人,他认识的人的区间必然是连续的,可以维护他认识的最右边的人R,这样更新操作相当于把[l,r]所有人的R值变成max(R,r),可以构造线段树维护每个区间中R的最小值mi,如果最小值大于等于R的话就不用更新了,直接退出,否则暴力修改每个点的值。

先上个假算法:

1 #include
2 using namespace std;
3 typedef long long ll;
4 const int N=5e5+10,inf=0x3f3f3f3f;
5 #define ls (u<<1)
6 #define rs (u<<1|1)
7 #define mid ((l&#43;r)>>1)
8 int mi[N<<2],n,m;
9 ll ans;
10 void pu(int u) {mi[u]&#61;min(mi[ls],mi[rs]);}
11 void build(int u&#61;1,int l&#61;1,int r&#61;n) {
12 if(l&#61;&#61;r) {mi[u]&#61;l; return;}
13 build(ls,l,mid),build(rs,mid&#43;1,r),pu(u);
14 }
15 void upd(int L,int R,int u&#61;1,int l&#61;1,int r&#61;n) {
16 if(l>R||r&#61;R)return;
17 if(l&#61;&#61;r) {ans&#43;&#61;R-mi[u],mi[u]&#61;R; return;}
18 upd(L,R,ls,l,mid),upd(L,R,rs,mid&#43;1,r),pu(u);
19 }
20 int main() {
21 while(scanf("%d%d",&n,&m)&#61;&#61;2) {
22 build();
23 while(m--) {
24 ans&#61;0;
25 int l,r;
26 scanf("%d%d",&l,&r);
27 upd(l,r);
28 printf("%lld\n",ans);
29 }
30 }
31 return 0;
32 }

View Code

这个算法本身是没有问题的&#xff0c;交上去也能AC&#xff0c;但会被一些极端的数据卡死&#xff0c;比如[1,1],[1,2],...,[1,n]这样的&#xff0c;会被卡成n^2&#xff0c;因此可以加一些优化。

由于每个人认识的最右边的人R的值是非递减的&#xff0c;即任意i>j&#xff0c;R[i]>&#61;R[j]&#xff0c;因此每次发生变化的区间必然是连续的&#xff0c;可以把单点修改换成区间修改&#xff0c;这样就不会被卡了。

1 #include
2 using namespace std;
3 typedef long long ll;
4 const int N&#61;5e5&#43;10,inf&#61;0x3f3f3f3f;
5 #define ls (u<<1)
6 #define rs (u<<1|1)
7 #define mid ((l&#43;r)>>1)
8 int mx[N<<2],mi[N<<2],lz[N<<2],n,m;
9 ll sum[N<<2],ans;
10 void pu(int u) {
11 mi[u]&#61;min(mi[ls],mi[rs]);
12 mx[u]&#61;max(mx[ls],mx[rs]);
13 sum[u]&#61;sum[ls]&#43;sum[rs];
14 }
15 void pd(int u,int l,int r) {
16 if(lz[u]) {
17 sum[ls]&#61;(ll)lz[u]*(mid-l&#43;1),sum[rs]&#61;(ll)lz[u]*(r-mid);
18 mi[ls]&#61;mi[rs]&#61;mx[ls]&#61;mx[rs]&#61;lz[ls]&#61;lz[rs]&#61;lz[u],lz[u]&#61;0;
19 }
20 }
21 void build(int u&#61;1,int l&#61;1,int r&#61;n) {
22 lz[u]&#61;0;
23 if(l&#61;&#61;r) {sum[u]&#61;mi[u]&#61;mx[u]&#61;l; return;}
24 build(ls,l,mid),build(rs,mid&#43;1,r),pu(u);
25 }
26 void upd(int L,int R,int u&#61;1,int l&#61;1,int r&#61;n) {
27 if(l>R||r&#61;R)return;
28 if(l>&#61;L&&r<&#61;R&&mx[u]<&#61;R) {sum[u]&#61;(ll)R*(r-l&#43;1),mi[u]&#61;mx[u]&#61;lz[u]&#61;R; return;}
29 pd(u,l,r);
30 upd(L,R,ls,l,mid),upd(L,R,rs,mid&#43;1,r),pu(u);
31 }
32 int main() {
33 while(scanf("%d%d",&n,&m)&#61;&#61;2) {
34 build(),ans&#61;sum[1];
35 while(m--) {
36 int l,r;
37 scanf("%d%d",&l,&r);
38 upd(l,r);
39 printf("%lld\n",sum[1]-ans);
40 ans&#61;sum[1];
41 }
42 }
43 return 0;
44 }

View Code

然后据说还有一种叫“吉司机线段树”的东西也能做&#xff1f;赶紧学了学(便乘)&#xff0c;感觉对于区间取max/min这类问题的处理强大的&#xff0c;普适性也比较高。

对于区间取max操作&#xff0c;其基本思想是维护区间和sum,区间最小值mi,区间次小值se以及区间最小值个数nmi。如果要对[l,r]上的所有数与x取max&#xff0c;那么分三种情况讨论即可&#xff1a;

1)若x<&#61;mi&#xff0c;则修改操作无效&#xff0c;退出

2)若mi

3)若x>&#61;se&#xff0c;则在左右区间递归进行下去

1 #include
2 using namespace std;
3 typedef long long ll;
4 const int N&#61;5e5&#43;10,inf&#61;0x3f3f3f3f;
5 #define ls (u<<1)
6 #define rs (u<<1|1)
7 #define mid ((l&#43;r)>>1)
8 int mi[N<<2],nmi[N<<2],se[N<<2],lz[N<<2],n,m;
9 ll sum[N<<2],ans;
10 void pu(int u) {
11 sum[u]&#61;sum[ls]&#43;sum[rs];
12 mi[u]&#61;min(mi[ls],mi[rs]),se[u]&#61;max(mi[ls],mi[rs]);
13 se[u]&#61;se[u]&#61;&#61;mi[u]?min(se[ls],se[rs]):min(se[u],min(se[ls],se[rs]));
14 nmi[u]&#61;(mi[ls]&#61;&#61;mi[u]?nmi[ls]:0)&#43;(mi[rs]&#61;&#61;mi[u]?nmi[rs]:0);
15 }
16 void change(int u,int x) {sum[u]&#43;&#61;(ll)nmi[u]*(x-mi[u]),mi[u]&#61;lz[u]&#61;x;}
17 void pd(int u) {
18 if(~lz[u]) {
19 if(mi[ls]<lz[u])change(ls,lz[u]);
20 if(mi[rs]<lz[u])change(rs,lz[u]);
21 lz[u]&#61;-1;
22 }
23 }
24 void build(int u&#61;1,int l&#61;1,int r&#61;n) {
25 lz[u]&#61;-1;
26 if(l&#61;&#61;r) {sum[u]&#61;mi[u]&#61;l,nmi[u]&#61;1,se[u]&#61;inf; return;}
27 build(ls,l,mid),build(rs,mid&#43;1,r),pu(u);
28 }
29 void upd(int L,int R,int x,int u&#61;1,int l&#61;1,int r&#61;n) {
30 if(l>R||rreturn;
31 if(l>&#61;L&&r<&#61;R&&xreturn;}
32 pd(u),upd(L,R,x,ls,l,mid),upd(L,R,x,rs,mid&#43;1,r),pu(u);
33 }
34 int main() {
35 while(scanf("%d%d",&n,&m)&#61;&#61;2) {
36 build(),ans&#61;sum[1];
37 while(m--) {
38 int l,r;
39 scanf("%d%d",&l,&r);
40 upd(l,r,r);
41 printf("%lld\n",sum[1]-ans);
42 ans&#61;sum[1];
43 }
44 }
45 return 0;
46 }

View Code

 

转:https://www.cnblogs.com/asdfsag/p/10773927.html



推荐阅读
  • 本题来自WC2014,题目编号为BZOJ3435、洛谷P3920和UOJ55。该问题描述了一棵不断生长的带权树及其节点上小精灵之间的友谊关系,要求实时计算每次新增节点后树上所有可能的朋友对数。 ... [详细]
  • JSOI2010 蔬菜庆典:树结构中的无限大权值问题
    本文探讨了 JSOI2010 的蔬菜庆典问题,主要关注如何处理非根非叶子节点的无限大权值情况。通过分析根节点及其子树的特性,提出了有效的解决方案,并详细解释了算法的实现过程。 ... [详细]
  • 深入解析Java虚拟机(JVM)架构与原理
    本文旨在为读者提供对Java虚拟机(JVM)的全面理解,涵盖其主要组成部分、工作原理及其在不同平台上的实现。通过详细探讨JVM的结构和内部机制,帮助开发者更好地掌握Java编程的核心技术。 ... [详细]
  • Coursera ML 机器学习
    2019独角兽企业重金招聘Python工程师标准线性回归算法计算过程CostFunction梯度下降算法多变量回归![选择特征](https:static.oschina.n ... [详细]
  • Java 实现二维极点算法
    本文介绍了一种使用 Java 编程语言实现的二维极点算法。该算法用于从一组二维坐标中筛选出极点,适用于需要处理几何图形和空间数据的应用场景。文章不仅详细解释了算法的工作原理,还提供了完整的代码示例。 ... [详细]
  • 本文介绍如何利用栈数据结构在C++中判断字符串中的括号是否匹配。通过顺序栈和链栈两种方式实现,并详细解释了算法的核心思想和具体实现步骤。 ... [详细]
  • 本文介绍如何从字符串中移除大写、小写、特殊、数字和非数字字符,并提供了多种编程语言的实现示例。 ... [详细]
  • 在高并发需求的C++项目中,我们最初选择了JsonCpp进行JSON解析和序列化。然而,在处理大数据量时,JsonCpp频繁抛出异常,尤其是在多线程环境下问题更为突出。通过分析发现,旧版本的JsonCpp存在多线程安全性和性能瓶颈。经过评估,我们最终选择了RapidJSON作为替代方案,并实现了显著的性能提升。 ... [详细]
  • 深入解析ESFramework中的AgileTcp组件
    本文详细介绍了ESFramework框架中AgileTcp组件的设计与实现。AgileTcp是ESFramework提供的ITcp接口的高效实现,旨在优化TCP通信的性能和结构清晰度。 ... [详细]
  • 深入解析RDMA中的队列对(Queue Pair)
    本文将详细探讨RDMA架构中的关键组件——队列对(Queue Pair,简称QP),包括其基本概念、硬件与软件实现、QPC的作用、QPN的分配机制以及用户接口和状态机。通过这些内容,读者可以更全面地理解QP在RDMA通信中的重要性和工作原理。 ... [详细]
  • 探讨ChatGPT在法律和版权方面的潜在风险及影响,分析其作为内容创造工具的合法性和合规性。 ... [详细]
  • 本题要求在一组数中反复取出两个数相加,并将结果放回数组中,最终求出最小的总加法代价。这是一个经典的哈夫曼编码问题,利用贪心算法可以有效地解决。 ... [详细]
  • 软件工程课堂测试2
    要做一个简单的保存网页界面,首先用jsp写出保存界面,本次界面比较简单,首先是三个提示语,后面是三个输入框,然 ... [详细]
  • 深入理解 JMeter 定时器
    本文详细介绍了JMeter中定时器的功能和使用方法,探讨了其在性能测试中的重要性,并结合实际案例解释了如何合理配置定时器以模拟真实的用户行为。文章还涵盖了定时器的执行顺序及其与其他元件的相互作用。 ... [详细]
  • SpringMVC RestTemplate的几种请求调用(转)
    SpringMVCRestTemplate的几种请求调用(转),Go语言社区,Golang程序员人脉社 ... [详细]
author-avatar
烦恼的天伦之乐_456
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有