interlinkage:

https://jzoj.net/senior/#main/show/6073

description:

solution:

  • 考虑一条河$x$被染的效果
  • 显然对于一条河$i$来说,若$k_i>k_x,b_i<b_x$,那么$i$会被$x$直接染
  • 这实际上启示我们可以把直线按$k$为第一关键字,$b$为第二关键字升序排序
  • 又发现若$k_i>k_x,b_i>b_x$,这条河会被$x$染色的充要条件是存在$k_y>k_i>k_x,b_y<b_x$
  • 这样就易得一个结论,按上述方法将直线排序,一条直线能染得部分是向右最后一个$b$比它小的和向左最后一个$b$比它大的
  • 问题转化为了有$n$个区间,询问覆盖总长的方案数,注意到这些区间不存在完全包含关系,$DP$即可
  • $f(n)$为染色到$n$的方案数,把这些区间按右端点排序再枚举右端点转移即可。这个可以前缀和优化

code:

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll; const int N=5e5+;
const ll mo=1e9+;
int n;
struct node
{
int k,b;
int id;
}p[N];
bool cmpk(node a,node b) {return a.k==b.k?a.b<b.b:a.k<b.k;}
bool cmpb(node a,node b) {return a.b<b.b;}
struct seg
{
int l,r;
}c[N];
bool operator < (seg a,seg b) {return a.r==b.r?a.l<b.l:a.r<b.r;}
inline int read()
{
char ch=getchar();int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
ll f[N],s[N];
int main()
{
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
n=read();
for (int i=;i<=n;i++) p[i].b=read(),p[i].k=read();
sort(p+,p++n,cmpk);
for (int i=;i<=n;i++) p[i].id=i;
sort(p+,p++n,cmpb);
int mi=n;
for (int i=n;i>=;i--) mi=min(mi,p[i].id),c[p[i].id].l=mi;
int mx=;
for (int i=;i<=n;i++) mx=max(mx,p[i].id),c[p[i].id].r=mx;
sort(c+,c++n);
int pos=;
for (int i=;i<=n;i++)
{
while (pos<c[i].r-)
{
++pos;
s[pos]=(s[pos-]+f[pos])%mo;
}
(f[c[i].r]*=)%=mo;//这个区间可以选,也可以不选
(f[c[i].r]+=s[c[i].r-]-(c[i].l>=?s[c[i].l-]:)+mo)%=mo;
if (c[i].l==) (f[c[i].r]+=)%=mo;
}
printf("%lld\n",f[n]%mo);
return ;
}

最新文章

  1. app使用微信支付成功后,点击返回到该app却跳到另外一个app去了
  2. 错误代码:ERR_UNSAFE_PORT
  3. Gauss elimination Template
  4. Spring相框
  5. 使用adb shell启动特定activity
  6. 深入了解Android蓝牙Bluetooth——《基础篇》
  7. 安装 cgilib 0.5
  8. es6学习笔记--新数据结构Set,Map以及WeakSet,WeakMap
  9. erlang进程概述
  10. C#线程安全使用(三)
  11. vue的事件处理梳理
  12. zabbix通过自动发现tomcat应用端口监控连接数
  13. NFS服务配置
  14. 牛客多校10 D Rikka with Prefix Sum 不是数据结构
  15. sql 循环语句几种方式(变量循环,游标循环,事务)
  16. mySQL 教程 第2章 安装和介绍mySQL
  17. Unity学习笔记(3):一些常用API和应用场景
  18. OK6410 rmmod卸载模块失败:No such file or directory -- 转
  19. [转载]Java抽象类和接口的学习
  20. 彻底解密C++宽字符(一)

热门文章

  1. 【Oracle】DG中物理备库、快照备库的相互转换
  2. C# Datetime 使用详解
  3. 机器学习:随机森林RF-OBB袋外错误率
  4. Python学习①. 基础语法
  5. appium处理app与web页面的转换
  6. (转)C#开发微信门户及应用(6)--微信门户菜单的管理操作
  7. trait 和abstract的区别在哪里
  8. 在Android 上运行 openCV ,并做灰度变化的一个例子
  9. 编写 Shell 脚本的最佳实践
  10. [POI2012]OKR-A Horrible Poem