洛谷P2082 区间覆盖(加强版)(珂朵莉树)
2024-08-26 00:49:46
虽然是黄题而且还是一波离散就能解决的东西
然而珂朵莉树还是很好用
相当于一开始区间全为0,然后每一次区间赋值,问最后总权值
珂朵莉树搞一搞就好了
//minamoto
#include<set>
#include<iostream>
#include<cstdio>
#define ll long long
#define IT set<node>::iterator
using std::set;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
ll read(){
#define num ch-'0'
char ch;bool flag=;ll res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
struct node{
ll l,r;mutable int v;
node(ll L,ll R=-,int V=):l(L),r(R),v(V){}
inline bool operator <(const node &b)const
{return l<b.l;}
};set<node> s;
IT split(ll pos){
IT it=s.lower_bound(node(pos));
if(it!=s.end()&&it->l==pos) return it;
--it;int l=it->l,r=it->r;ll v=it->v;
s.erase(it),s.insert(node(l,pos-,v));
return s.insert(node(pos,r,v)).first;
}
void assign(ll l,ll r){
IT itr=split(r+),itl=split(l);
s.erase(itl,itr),s.insert(node(l,r,));
}
ll sum(ll l,ll r){
IT itr=split(r+),itl=split(l);ll res=;
for(;itl!=itr;++itl) res+=itl->v?itl->r-itl->l+:;
return res;
}
int main(){
// freopen("testdata.in","r",stdin);
int n=read();s.insert(node(,1e17+,));
while(n--){
ll l=read(),r=read();assign(l,r);
}
printf("%lld\n",sum(,1e17));
return ;
}
最新文章
- sql存储过程中加引号
- 单片机联网需求攀升 WIZnet全硬件TCP/IP技术崛起
- magento 切换数据库,使用不同数据库
- 关于SQL语句中SUM函数返回NULL的解决办法
- BeautifulSoup解析非标准HTML的问题
- 《c陷阱与缺陷》笔记--移位运算
- 将图片转为ASCII字符画
- Code Blocks 使用 VC2013编译HelloWord
- 刚由pc端做移动端的感受
- Mysql按时间段分组查询
- JAVA开发中遇到的异常总结
- HDU 5412 CRB and Queries 动态整体二分
- 让iframe自适应高度-真正解决
- legend2---开发日志11(如何提高终极开发效率)
- 10.QT-定时器
- PlugNT CMS v4.6.3 调用文章上一页和下一页及点击数加1
- 数据库技术丛书:SQL Server 2016 从入门到实战(视频教学版) PDF
- 服务器较稳妥的磁盘阵列方案:RAID5+热备盘
- mysql查询当前时间,一天内,一周,一个月内的sql语句
- django-csrf攻击
热门文章
- [CERC2015]Digit Division
- loj6157 A^B Problem (并查集)
- 基于数据库的代码自动生成工具,生成JavaBean、生成数据库文档、生成前后端代码等(v6.0.0版)
- ntfs格式uefi启动u盘
- eclipse bug之&#39;<;>;&#39;operator is not allowed for source level below 1.7
- [WinForm]DataGridView列头右键菜单
- pip命令自动补全功能;设置代理;使用国内源
- php 获取TZ时间格式
- [Android]自己定义带删除输入框
- 实践部署与使用apache kafka框架技术博文资料汇总