热门标签 | 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



推荐阅读
  • 火星商店问题:线段树分治与持久化Trie树的应用
    本题涉及编号为1至n的火星商店,每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品,以及查询某段时间内某些商店中所有商品(含永久商品)与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]
  • 本文探讨了如何在模运算下高效计算组合数C(n, m),并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元,从而实现除法取余的计算。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • 基于KVM的SRIOV直通配置及性能测试
    SRIOV介绍、VF直通配置,以及包转发率性能测试小慢哥的原创文章,欢迎转载目录?1.SRIOV介绍?2.环境说明?3.开启SRIOV?4.生成VF?5.VF ... [详细]
  • 使用Numpy实现无外部库依赖的双线性插值图像缩放
    本文介绍如何仅使用Numpy库,通过双线性插值方法实现图像的高效缩放,避免了对OpenCV等图像处理库的依赖。文中详细解释了算法原理,并提供了完整的代码示例。 ... [详细]
  • 深入解析Android自定义View面试题
    本文探讨了Android Launcher开发中自定义View的重要性,并通过一道经典的面试题,帮助开发者更好地理解自定义View的实现细节。文章不仅涵盖了基础知识,还提供了实际操作建议。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • python的交互模式怎么输出名文汉字[python常见问题]
    在命令行模式下敲命令python,就看到类似如下的一堆文本输出,然后就进入到Python交互模式,它的提示符是>>>,此时我们可以使用print() ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本教程涵盖OpenGL基础操作及直线光栅化技术,包括点的绘制、简单图形绘制、直线绘制以及DDA和中点画线算法。通过逐步实践,帮助读者掌握OpenGL的基本使用方法。 ... [详细]
  • MySQL索引详解与优化
    本文深入探讨了MySQL中的索引机制,包括索引的基本概念、优势与劣势、分类及其实现原理,并详细介绍了索引的使用场景和优化技巧。通过具体示例,帮助读者更好地理解和应用索引以提升数据库性能。 ... [详细]
  • 基因组浏览器中的Wig格式解析
    本文详细介绍了Wiggle(Wig)格式及其在基因组浏览器中的应用,涵盖variableStep和fixedStep两种主要格式的特点、适用场景及具体使用方法。同时,还提供了关于数据值和自定义参数的补充信息。 ... [详细]
  • Codeforces Round #566 (Div. 2) A~F个人题解
    Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意:给你一个的表格,你 ... [详细]
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社区 版权所有