【学习笔记】用线段树维护区间计数问题

前言

简单的区间计数问题可能直接推式子就行了。
但有些问题必须要数据结构维护。线段树就是一个比较好的处理区间的数据结构。

Gym102222L

在这里插入图片描述

在这里插入图片描述

思路

满足条件的区间特征: max ⁡ { a i } − min ⁡ { a i } + 1 − c n t = 0 \max\{a_i\}-\min\{a_i\}+1-cnt=0 max{ai}min{ai}+1cnt=0,其中 c n t cnt cnt 代表区间内不同数字的个数。
考虑固定右端点,统计有多少个合法的左端点。
我们可以用线段树维护 m i n v = min ⁡ { max ⁡ { a i } − min ⁡ { a i } − c n t } minv=\min\{\max\{a_i\}-\min\{a_i\}-cnt\} minv=min{max{ai}min{ai}cnt} n u m = 有多少个区间左端点可以取到 m i n v num=有多少个区间左端点可以取到 minv num=有多少个区间左端点可以取到minv,答案就是 m i n v = − 1 minv=-1 minv=1 时的 n u m num num
max ⁡ { a i } \max\{a_i\} max{ai} min ⁡ { a i } \min\{a_i\} min{ai} 可以用两个单调栈维护。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18;
struct seg
{int minv,tag,cnt;seg(){minv=tag=cnt=0;}
};
vector<seg> tr;
void update(int u)
{tr[u].minv=min(tr[u<<1].minv,tr[u<<1|1].minv);if(tr[u<<1].minv==tr[u<<1|1].minv){tr[u].cnt=tr[u<<1].cnt+tr[u<<1|1].cnt;}else if(tr[u].minv==tr[u<<1].minv){tr[u].cnt=tr[u<<1].cnt;}else if(tr[u].minv==tr[u<<1|1].minv){tr[u].cnt=tr[u<<1|1].cnt;}else{assert(false);}
}
void pushdown(int u)
{if(tr[u].tag){tr[u<<1].minv+=tr[u].tag; tr[u<<1|1].minv+=tr[u].tag;tr[u<<1].tag+=tr[u].tag; tr[u<<1|1].tag+=tr[u].tag;tr[u].tag=0;}
}
void build(int u,int st,int ed)
{if(st==ed){tr[u].cnt=1;return;}int mid=st+ed>>1;build(u<<1,st,mid);build(u<<1|1,mid+1,ed);update(u);
}
void modify(int u,int st,int ed,int l,int r,int x)
{if(l<=st&&ed<=r){tr[u].minv+=x;tr[u].tag+=x;return;}pushdown(u);int mid=st+ed>>1;if(mid>=l)modify(u<<1,st,mid,l,r,x);if(mid<r)modify(u<<1|1,mid+1,ed,l,r,x);update(u);
}
int query(int u,int st,int ed,int l,int r)
{if(l<=st&&ed<=r){return tr[u].minv==-1?tr[u].cnt:0;}pushdown(u);int mid=st+ed>>1;int res=0;if(mid>=l)res=query(u<<1,st,mid,l,r);if(mid<r)res+=query(u<<1|1,mid+1,ed,l,r);return res;
}
int O_o()
{int n;cin>>n;tr.assign(n+1<<2,seg());vector<int> a(n+1),ls(n+1);map<int,int> mp;for(int i=1; i<=n; i++){cin>>a[i];ls[i]=mp[a[i]];mp[a[i]]=i;}build(1,1,n);stack<array<int,2>> sx,sy;// decrease, increaseint ans=0;for(int i=1; i<=n; i++){int x=a[i];while(sx.size()&&x>sx.top()[0]){auto [v,id]=sx.top(); sx.pop();modify(1,1,n,sx.size()?(sx.top()[1]+1):1,id,x-v);}sx.push({x,i});while(sy.size()&&x<sy.top()[0]){auto [v,id]=sy.top(); sy.pop();modify(1,1,n,sy.size()?(sy.top()[1]+1):1,id,v-x);}sy.push({x,i});modify(1,1,n,ls[i]+1,i,-1);ans+=query(1,1,n,1,i);}return ans;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(12);int T=1;cin>>T;for(int i=1; i<=T; i++){cout<<"Case #"<<i<<": "<<O_o()<<"\n";}
}

2024牛客暑期多校训练营7 D

在这里插入图片描述
在这里插入图片描述

思路

首先预处理每个点要往后走到哪才会出现 k k k 次和 k + 1 k+1 k+1
具体的,令 L i L_i Li 为从点 i i i 往后走,出现 k k k a i a_i ai 的最近位置;令 R i R_i Ri 为从点 i i i 往后走,出现 k k k a i a_i ai 的最远位置。
考虑倒着枚举左端点,对于每个左端点考虑有多少个右端点是合法的。

我们定义点 i i i 的合法区间为 [ L i , R i ] ∪ [ 1 , i − 1 ] [L_i,R_i]∪[1,i-1] [Li,Ri][1,i1] [ L i , R i ] [L_i,R_i] [Li,Ri] a i a_i ai 出现了 k k k 次, [ 1 , i − 1 ] [1,i-1] [1,i1] 不在 i i i 的管辖范围内),那么对于 i i i 为左端点的答案就是 [ i , n ] [i,n] [i,n] 中所有不同的数最前面的合法区间的交集。

也就是我们要维护一棵线段树,支持区间加、区间减、求区间最大值和最大值个数。这样做其实有些麻烦。
不难想到,合法区间的交集 = 不合法区间的并集的反集,求区间的并就完全可以像扫描线那样做。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18;
struct seg
{int val,len;seg(){val=len=0;}
};
vector<seg> tr;
int n;
void update(int u,int st,int ed)
{if(tr[u].val>0){tr[u].len=ed-st+1;}else{if(st==ed){tr[u].len=0;return;}tr[u].len=tr[u<<1].len+tr[u<<1|1].len;}
}
void add(int u,int st,int ed,int l,int r,int x)
{if(l>r||l>n||r>n) return;if(l<=st&&ed<=r){tr[u].val+=x;update(u,st,ed);return;}
//	pushdown(u);int mid=st+ed>>1;if(mid>=l)add(u<<1,st,mid,l,r,x);if(mid<r)add(u<<1|1,mid+1,ed,l,r,x);update(u,st,ed);
}
int query(int u,int st,int ed,int l,int r)
{if(l>r||l>n||r>n) return 0;if(l<=st&&ed<=r){return tr[u].len;}int mid=st+ed>>1;int res=0;if(mid>=l)res=query(u<<1,st,mid,l,r);if(mid<r)res+=query(u<<1|1,mid+1,ed,l,r);return res;
}
void O_o()
{int k;cin>>n>>k;map<int,vector<int>> mp;vector<int> a(n+1);for(int i=1; i<=n; i++){cin>>a[i];mp[a[i]].push_back(i);}tr.assign((n<<2)+1,seg());vector<array<int,2>> pos(n+1);vector<int> p,nxt(n+1);p.push_back(-1);for(auto [v,t]:mp){p.push_back(v);int m=t.size();for(int i=0; i<m; i++){int l,r;if(i+k-1>=m){l=n+1;}else l=t[i+k-1];if(i+k>=m){r=n+1;}else r=t[i+k];pos[t[i]]={l,r};if(i==m-1)nxt[t[i]]=n+1;else nxt[t[i]]=t[i+1];}}int ans=0;for(int i=n; i>=1; i--){if(nxt[i]!=n+1){auto [l,r]=pos[nxt[i]];add(1,1,n,nxt[i],l-1,-1);add(1,1,n,r,n,-1);}auto [l,r]=pos[i];add(1,1,n,i,l-1,1);add(1,1,n,r,n,1);int t=query(1,1,n,i,n);ans+=(n-i+1)-t;}cout<<ans<<"\n";
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(12);int T=1;cin>>T;while(T--){O_o();}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/395442.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

解锁创意之门:如何使用DALL·E-3创作惊艳的图像

在这个视觉驱动的时代&#xff0c;图像已经成为表达创意和传递信息的重要媒介。最近&#xff0c;OpenAI发布了新一代的图像生成模型——DALLE-3&#xff0c;它以其卓越的生成能力和细致的图像质量迅速成为了创意工作者的热门工具。今天&#xff0c;我将带你一步步了解如何使用D…

13.3 正则表达式的应用

欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;欢迎订阅相关专栏&#xff1a; 工&#x1f497;重&#x1f497;hao&#x1f497;&#xff1a;野老杂谈 ⭐️ 全网最全IT互联网公司面试宝典&#xff1a;收集整理全网各大IT互联网公司技术、项目、HR面试真题.…

2024年6月scratch图形化编程等级考试三级真题

202406 青少年软件编程等级考试Scratch三级真题 试卷总分数&#xff1a;100分 考试时长&#xff1a;60 分钟 第 1 题 运行程序后&#xff0c;角色的x坐标是&#xff1f;&#xff08; &#xff09; A&#xff1a;99 B&#xff1a;100 C&#xff1a;199 D&#xff1a;200 正…

矩阵的导数运算

1. 标量方程对向量的导数 一维方程f(y)求极值即求导,令 二维方程f(y1,y2)求极值即求偏导,令 如果一个标量方程f(y1,y2,...ym)有m个自变量,求取它的极值就需要求取m组的方程组。当然可以用一种简洁的方式来表达它,比如二维方程f(y1,y2)可以把其中的变量写成向量的形式,此…

指针基础知识(笔记)

文章目录 1. 概念理解2. 空指针和野指针3. 计算4. 小结5. size_t6. 案例一: 指针查找并返回指定元素索引7. 指针访问多维数组(涉及 int (*ptr)[3]解析)8. 指针数组9. 函数的值传递与地址引用传递① 函数的值传递(pass by value)② 地址传递(pass by reference) 10. 案例二&…

C语言宠物系统

功能有增加宠物信息&#xff0c;显示宠物信息&#xff0c;删除宠物信息&#xff0c;修改功能和排序功能&#xff0c;可以选择姓名排序&#xff0c;年龄排序&#xff0c;价格排序。进阶的功能有文件操作&#xff0c;动态内存开辟。。 test.c源文件 #include "Pet.h"v…

机器人帮助文档

文章目录 机器交流使用群使用图例1. 查看机器人使用文档2. 直接问问题&#xff08;系统默认AI&#xff09;3. 系统默认AI切换4. 直接问问题&#xff08;指定讯飞星火AI&#xff09;5. 直接问问题&#xff08;指定百度文心AI&#xff09;6. 直接问问题&#xff08;指定谷歌AI&am…

代码随想录算法训练营Day34 | 62.不同路径 | 63. 不同路径 II | 343.整数拆分 | 96.不同的二叉搜索树

今日任务 62.不同路径 题目链接&#xff1a; https://leetcode.cn/problems/unique-paths/description/题目描述&#xff1a; Code class Solution { public:int uniquePaths(int m, int n) {// vector<vector<int>> memo(m, vector<int>(n, -1));// fu…

从0开始的1panel搭配雷池社区版保护网站

1.安装1panel 使用默认安装地址&#xff1a;/opt [1Panel Log]: 外网地址: http://xxxxx:35628/dc54fe6a54 [1Panel Log]: 内网地址: http://10.0.4.3:35628/dc54fe6a54 [1Panel Log]: 面板用户: root [1Panel Log]: 面板密码: xxxxx 安装完成第一次登陆 安装openresty&…

【原创】springboot+mysql法律咨询网设计与实现

个人主页&#xff1a;程序猿小小杨 个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交…

初学51单片机1602液晶时序图实例分析

上篇博文笔者分享了关于液晶1602基本的工作流程&#xff0c;本篇主要是通过逻辑分析仪来看一下程序使能的电平时序&#xff0c;是否符合产品文档给出 的时序逻辑。 先看一下1602的时序图 认识下时序图中各个标识的含义&#xff1a; Tc信号周期&#xff08;E Cycle Time&#x…

【解压既玩】PS3模拟器v0.0.32+战神3+战神升天+各存档 整合包 ,完美不死机,没有BUG,旷世神作,强力推荐

战神3是圣莫尼卡公司的大作&#xff0c;PS3 上必玩的游戏之一。 本文收集了战神3和升天两作&#xff0c;附存档&#xff0c;完美不死机&#xff0c;没有BUG&#xff0c;强烈推荐。 解压即玩。 立即下载&#xff1a;【chumenx.com】【解压既玩】PS3模拟器v0.0.32战神3战神升天…

Docker数据管理,数据卷,容器服务器数据卷

一、容器的数据管理介绍 1.1 Docker容器分层 Docker镜像由多个只读层叠加而成&#xff0c;启动容器时&#xff0c;Docker会加载只读镜像层并在镜像栈顶部添加一个读写层。 如果运行中的容器修改了现有的一个已经存在的文件&#xff0c;那该文件将会从读写层下面的只读层复制到…

Redis相关面试题(二)

一、Bit中不同命令使用的场景 二、什么是缓存击穿&#xff0c;缓存穿透&#xff0c;缓存雪崩&#xff1f; 缓存击穿&#xff1a;是指当某一个key的缓存过期时大并发量的请求同时访问key&#xff0c;瞬间击穿服务器直接访问到数据库&#xff0c;使得数据库处于负载情况 缓存穿透…

mysql8.4.2数据库做主从复制

linux rocky 9.2系统安装mysql-wsrep-8.4.2-26.20-linux-x86_64.tar.gz二进制包-CSDN博客文章浏览阅读472次&#xff0c;点赞7次&#xff0c;收藏4次。linux rocky 9.2系统安装mysql-wsrep-8.4.2-26.20-linux-x86_64.tar.gz二进制包https://blog.csdn.net/xikui1551/article/de…

C++的深拷贝和浅拷贝

浅拷贝是一种简单的拷贝方式&#xff0c;仅仅是复制对象的基本类型成员和指针成员的值&#xff0c;而不复制指针所指向的内存。这可能会导致两个对象共享相同的资源&#xff0c;从而引发潜在的问题&#xff0c;如内存泄漏、意外修改共享资源等。一般来说编译器默认帮我们实现的…

Openwrt配置ZeroTier,实现公网访问内网中服务器

ZeroTier注册&Openwrt初始配置 首先来到Openwrt的VPN→ZeroTier页面&#xff0c;进行一个很简单的注册 注册后去zerotier的网页管理页面进行一个很简单的创建网络 复制网络ID备用 在openwrt填写网络ID并启用。如果你需要访问内网主机勾上 自动客户端NAT 在zerotier网络管理…

十一、vector 类

Ⅰ . vector 的介绍和使用 01 vector 的介绍 vector 的文档介绍&#xff1a;vector ① vector 是表示可变大小数组的序列容器&#xff0c;既像数组&#xff0c;又不像数组 像体现在&#xff1a;同样采用连续存储空间存储元素&#xff0c;可以使用下标访问元素 不像体现在&…

大模型笔记5 Extractive QA任务评估

目录 Extractive QA任务评估 Extractive QA评测指标 precision, recall, f1 ROUGE 划分训练与评估数据集 token位置评估 单个token位置评估 输入label的token位置 预测token位置 评估 Wandb 共享机器同时登录 样本类别平衡 标记token label时对窗口进行筛选 训练…

IT运维岗适用的6本证书

作为IT从业人员&#xff0c;不断提升自身的专业技能和知识是提升职场竞争力、助力升职加薪的重要途径。特别是在运维领域&#xff0c;虽然工作看似简单&#xff0c;但实际上需要掌握的技术知识却相当全面。为了全面提升自己的技术能力&#xff0c;并证明自己的专业能力&#xf…