2018牛客网暑假ACM多校训练赛(第四场)E Skyline 线段树 扫描线

时间:2022-09-21 08:47:49

原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round4-E.html

题目传送门 - https://www.nowcoder.com/acm/contest/142/E

题意

  给定二维平面上的 $n$ 个点,第 $i$ 个点的坐标是 $(x_i,y_i)$ ,第 $i$ 个点出现的概率是 $a_i\times b_i^{-1}$ 。

  现在让你求  [满足 “存在 $i$ 使得 $x\leq x_i,y\leq y_i$ ”的点 $(x,y)$  的数量]  的期望。答案对于 $10^9+7$ 取模。

  多组数据,$n\leq 10^5,\sum n\leq 10^6, \rm{Time\ Limit = 10s}$

题解

  出题人大概是着急有事吧。他讲的太快了这题不知道说了什么。只记得我去存了一下队友比赛时候的 AC 代码然后回来发现他讲了好几题。

  下面是我们队的做法。

  首先,我们考虑补集转化: 期望点数 = 可能的点 - 不满足条件的点数的期望

  其中可能的点我们设定为 左下角为 (1,1) ,右上角为 $ (max_x,max_y)$ ,其中右上角的两个坐标值分别为输入点的两个坐标值的最大值。

  那么我们考虑一个点对于“不满足条件的点数的期望”的贡献。这个贡献显然是 $1\times $ “在这个点左上方向的所有点都不出现的概率” 。

  我们只需要用一个算法把所有的点的贡献加起来就可以了。

  首先,我们离散化一下。然后线段树扫描线,从上往下一行一行操作。一个点的"操作"就是对 $x$ 坐标在其左侧的区间乘上 它不出现的概率。这个显然可以线段树区间乘法。每操作完一行,统计一下这一行与下一行之间区域的答案,并更新总答案。

  时间复杂度 $O (n\log n)$ 。

  不进行补集转化应该也可以做吧,但是会难写一些吧。比如我一开始用树状数组写到弃疗……

代码

%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
const int N=100005,mod=1e9+7;
namespace HashTable{
int hs,Ha[N];
void clear(){hs=0;memset(Ha,0,sizeof Ha);}
void push(int x){Ha[++hs]=x;}
void HASH(){
sort(Ha+1,Ha+hs+1);
int _hs=1;
for (int i=2;i<=hs;i++)
if (Ha[i]!=Ha[i-1])
Ha[++_hs]=Ha[i];
hs=_hs;
}
int find(int x){return lower_bound(Ha+1,Ha+hs+1,x)-Ha;}
}
using namespace HashTable;
inline int read(){
int x=0;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x;
}
inline int Pow(int x,int y){
int ans=1;
for (;y;y>>=1,x=1LL*x*x%mod)
if (y&1)
ans=1LL*ans*x%mod;
return ans;
}
struct Point{
int x,y,p;
}a[N];
bool cmp(Point a,Point b){
if (a.y!=b.y)
return a.y>b.y;
return a.x>b.x;
}
struct Seg{
int v,add;
}t[N<<2];
inline void build(int rt,int L,int R){
t[rt].add=1;
if (L==R){
t[rt].v=Ha[L]-Ha[L-1];
return;
}
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
build(ls,L,mid);
build(rs,mid+1,R);
t[rt].v=(t[ls].v+t[rs].v)%mod;
}
inline void pushdown(int rt){
int &v=t[rt].add;
if (v==1)
return;
int ls=rt<<1,rs=ls|1;
t[ls].v=1LL*t[ls].v*v%mod,t[ls].add=1LL*t[ls].add*v%mod;
t[rs].v=1LL*t[rs].v*v%mod,t[rs].add=1LL*t[rs].add*v%mod;
v=1;
}
inline void update(int rt,int L,int R,int x,int d){
if (R<=x){
t[rt].v=1LL*t[rt].v*d%mod;
t[rt].add=1LL*t[rt].add*d%mod;
return;
}
pushdown(rt);
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
update(ls,L,mid,x,d);
if (x>mid)
update(rs,mid+1,R,x,d);
t[rt].v=(t[ls].v+t[rs].v)%mod;
}
inline void solve(){
int n=read();
clear();
for (int i=1;i<=n;i++){
a[i].x=read(),a[i].y=read();
push(a[i].x);
int A=read(),B=read();
a[i].p=1LL*A*Pow(B,mod-2)%mod;
}
HASH();
for (int i=1;i<=n;i++)
a[i].x=find(a[i].x);
sort(a+1,a+n+1,cmp);
build(1,1,hs);
int ans=0;
for (int i=1,j;i<=n;i=j+1){
for (j=i;j<n&&a[j+1].y==a[i].y;j++);
for (int k=i;k<=j;k++)
update(1,1,hs,a[k].x,(mod+1-a[k].p)%mod);
ans=(1LL*(a[i].y-a[j+1].y)*(Ha[hs]-t[1].v+mod)+ans)%mod;
}
printf("%d\n",ans);
}
int main(){
for (int T=read();T;T--)
solve();
return 0;
}

  

2018牛客网暑假ACM多校训练赛(第四场)E Skyline 线段树 扫描线的更多相关文章

  1. 2018牛客网暑假ACM多校训练赛(第二场)E tree 动态规划

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round2-E.html 题目传送门 - 2018牛客多校赛第二场 E ...

  2. 2018牛客网暑假ACM多校训练赛(第三场)I Expected Size of Random Convex Hull 计算几何&comma;凸包&comma;其他

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round3-I.html 题目传送门 - 2018牛客多校赛第三场 I ...

  3. 2018牛客网暑假ACM多校训练赛(第三场)G Coloring Tree 计数&comma;bfs

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round3-G.html 题目传送门 - 2018牛客多校赛第三场 G ...

  4. 2018牛客网暑假ACM多校训练赛(第三场)D Encrypted String Matching 多项式 FFT

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round3-D.html 题目传送门 - 2018牛客多校赛第三场 D ...

  5. 2018牛客网暑假ACM多校训练赛(第七场)I Tree Subset Diameter 动态规划 长链剖分 线段树

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round7-I.html 题目传送门 -  https://www.n ...

  6. 2018牛客网暑假ACM多校训练赛(第六场)I Team Rocket 线段树

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round6-I.html 题目传送门 - https://www.no ...

  7. 2018牛客网暑假ACM多校训练赛(第五场)F take 树状数组&comma;期望

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round5-F.html 题目传送门 - https://www.no ...

  8. 2018牛客网暑假ACM多校训练赛(第四场)B Interval Revisited 动态规划

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round4-B.html 题目传送门 - https://www.no ...

  9. 2018牛客网暑假ACM多校训练赛(第十场)H Rikka with Ants 类欧几里德算法

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round10-H.html 题目传送门 - https://www.n ...

随机推荐

  1. 如何利用【DataTable】结合自己本地数据库,使用表格

    如何利用[DataTable]结合自己本地数据库,使用表格我们都知道DataTable的使用与配置,平时我们都是用一个json文件来代替后台,但是实际上我们在与后台交互的时候,后台先取到数据库里面的信 ...

  2. ExtJs中实现tree节点,全部是单击展开和收缩效果,和收藏夹点击功能一样

    listeners : { click : function(node, c) {// 单击节点事件(node是节点对象) if(!node.isLeaf()){//不是叶子节点 node.singl ...

  3. Java常见排序算法之直接插入排序

    在学习算法的过程中,我们难免会接触很多和排序相关的算法.总而言之,对于任何编程人员来说,基本的排序算法是必须要掌握的. 从今天开始,我们将要进行基本的排序算法的讲解.Are you ready?Let ...

  4. &lbrack;原创&rsqb;-IIS7&period;5优化,支持同时10万个请求

    背景:        IIS7.5是微软推出的最新平台IIS,性能也较以前有很大的提升,但是默认的设置配不适合很大的请求.但是我们可以根据实际的需要进行IIS调整,使其性能更佳,支持同时10万个请求. ...

  5. python手记&lpar;32&rpar;

    #!/usr/bin/env python #-*- coding: utf-8 -*- import cv2 import numpy as np fn="test2.jpg" ...

  6. poj 3084 最小割

    题目链接:http://poj.org/problem?id=3084 本题主要在构图上,我采用的是把要保护的房间与源点相连,有intruder的与汇点相连,相对麻烦. #include <cs ...

  7. redis的数据类型 (一) 字符串

    redis中存储方式是以键值对存储的,所以叫做字典试.redis(Remote dictionary server)远程字典服务器 每个redis数据类型,都会有增加.删除,查看的功能,用实例来学习命 ...

  8. &lbrack;持续交付实践&rsqb; pipeline使用:语法详解

    一.引言 jenkins pipeline语法的发展如此之快用日新月异来形容也不为过,而目前国内对jenkins pipeline关注的人还非常少,相关的文章更是稀少,唯一看到w3c有篇相关的估计是直 ...

  9. PHP常见的一些问题总结(收藏)

    本篇文章给大家带来的内容是关于PHP常见的一些问题总结(收藏),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助. 1. 字符串定义的时候单引号和双引号有什么区别? 单引号加载速度比双引号 ...

  10. 腾讯QQ会员中心g&lowbar;tk32算法【C&num;版】

    最近用C#写qq活动辅助类程序,碰到了会员签到的gtk算法不一样,后来网上找了看,发现有php版的(https://www.oschina.net/code/snippet_1378052_48831 ...