[CERC2017]Buffalo Barricades

news/2024/3/3 22:30:40

这个题目,扫描线+玄学**
大概操作就是用个扫描线从上往下扫。
博主有点懒,就直接贴代码了,但是我还是给大家贴个比较详细的博客,除了代码都可以看wym的博客,我基本上就是按wym大佬的思路来的,当然,我的代码里也加了点注释,大家也请凑合着看吧。

Ps:
ycz:STL什么辣鸡,跑这么慢,你看手写splay多么快
wym:STL有啥不好啦,代码量短,如果手写splay还要各种操作,STL多简洁明了啊

/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){int x=0,f=1;char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<1)+(x<<3)+ch-'0';return x*f;
}
inline void print(int x){if (x>=10)     print(x/10);putchar(x%10+'0');
}
const int N=3e5;
int Ans[N+10],last[N+10],cnt[N+10];
struct S1{int x,y,t;void join(int i){x=read(),y=read(),t=i;}bool operator <(const S1 &a)const{return y!=a.y?y>a.y:x<a.x;}
}A[N*2+10];
struct S2{//splay的维护需要按照x坐标为第一关键字,时间为第二关键字来维护 #define ls(x) tree[x][0]#define rs(x) tree[x][1]#define T(x) (rs(f[x])==x)struct S3{int x,t;void clear(){x=t=0;}void join(int a,int b){x=a,t=b;}bool operator <(const S3 &a)const{return x!=a.x?x<a.x:t<a.t;}}val[N*4+10],tmp;int f[N*4+10],tree[N*4+10][2];int root,len;void clear(int x){ls(x)=rs(x)=f[x]=0,val[x].clear();}void move(int x){int fa=f[x],son=tree[x][T(x)^1];tree[x][T(x)^1]=fa;tree[fa][T(x)]=son;if (son)    f[son]=fa;f[x]=f[fa];if (f[x])   tree[f[x]][T(fa)]=x;f[fa]=x;}void splay(int x){while (f[x]){if (f[f[x]])    T(x)==T(f[x])?move(f[x]):move(x);move(x);}root=x;}void insert(int x,int t){val[++len].join(x,t);if (!root){root=len;return;}int i=root;while (true){if (val[len]<val[i]){if (!ls(i)){f[ls(i)=len]=i;break;}i=ls(i);}else{if (!rs(i)){f[rs(i)=len]=i;break;}i=rs(i);}}splay(len);}int get_pre(){int x=ls(root);while (rs(x))   x=rs(x);return x;}int get_suc(){int x=rs(root);while (ls(x))   x=ls(x);return x;}void Delete(int x){splay(x);if (!(ls(x)&&rs(x))){f[root=ls(x)+rs(x)]=0;clear(x);return;}//删除必须找后继节点,这样才能保证根不变 int i=get_suc();splay(i);f[ls(i)=ls(x)]=i;clear(x);}
}Splay;
struct S4{int f[N+10];int find(int x){return f[x]?f[x]=find(f[x]):x;}void merge(int x,int y){x=find(x),y=find(y);if (x!=y)   f[x]=y,cnt[y]+=cnt[x];//merge有顺序 }
}F;
int main(){int n=read();for (int i=1;i<=n;i++){A[i].join(0);(A[i].x<<=1)--;(A[i].y<<=1)--;}int m=read();for (int i=1;i<=m;i++){A[i+n].join(i);A[i+n].x<<=1;A[i+n].y<<=1;}//消去0.5的影响,所以位移一位 sort(A+1,A+1+n+m);for (int i=1;i<=n+m;i++){Splay.insert(A[i].x,A[i].t);//因为if语句里两个都要insert,虽然用处不同,但是我懒 if (A[i].t){int suc=Splay.get_suc();if (suc)    last[A[i].t]=Splay.val[suc].t;//记录右边的第一个时间比其大的点,方便并查集维护 while (true){//保证根不变,一个个删掉前驱节点,类似于单调栈int pre=Splay.get_pre();if (!pre||Splay.val[pre].t<A[i].t)  break;Splay.Delete(pre);}}else{//insert之后才能找到其后继,但是这个点不能加进去,所以直接删掉 int T=Splay.get_suc();Splay.Delete(Splay.root);if (T)  cnt[Splay.val[T].t]++;//初步统计答案 }}for (int i=m;i;i--){Ans[i]=cnt[F.find(i)];if (last[i])    F.merge(i,last[i]);//merge操作有顺序,如果说last[i]的时间大于i的时间,加不加没有任何影响,为了方便,都加 }for (int i=1;i<=m;i++)  printf("%d\n",Ans[i]);return 0;
}

转载于:https://www.cnblogs.com/Wolfycz/p/8497097.html


http://www.ppmy.cn/news/724409.html

相关文章

布法罗计算机专业怎么样,布法罗大学 University at Buffalo

布法罗大学(University at Buffalo)——即纽约州立大学水牛城分校成立于1846年&#xff0c;前身是一所小型私人医学院&#xff0c;经过百年的发展&#xff0c;逐渐壮大成一所公立的综合性研究大学&#xff0c;培养了来自全国和世界各地约16万本科毕业生&#xff0c;布法罗大学提…

[Buffalo] 一些SQL函数

取得当前时间的函数&#xff1a;GETDATE() 计算时间的函数&#xff1a;DATEADD(datepart,number,date) 计算两个时间差额&#xff1a;DATEDIFF(datepart,startdate,enddate) 计算一个日期是星期几&#xff1a;DATENAME(datepart,date),datepartWEEK 取得日期的指定部分&#xf…

buffalo-命令

生成fizz文件命令 buffalo db g fizz table_name field_name:field_type(default string) eg: soda g fizz devops_controller name code desc:text deleted_at:nulls.Time 生成model文件命令 buffalo db g m table_name field_name:field_type(default string) eg: soda g m d…

buffalo之hello world

一个国产的ajax框架&#xff0c;定义了Web远程调用的传输基础&#xff0c; 并且将远程调用对象完整的序列化到了本地&#xff0c;成为可以被JavaScript编程触及的对象。 配置依赖包: <dependency><groupId>net.buffalo</groupId><artifactId>buffalo…

buffalo助手函数

buffalo助手函数 t(): 翻译函数 locales目录下翻译文件中定义: -id : createtranslation : "创建" 模版中使用 : t("create")form(): 前台生成表单函数,详细 form({action:"",method:"",var:"f"}) //自动生成csrf验证隐藏表…

无线路由Buffalo G300N V2 CH小测

硬件是日本的&#xff0c;固件是美国的。产品是日本的&#xff0c;钓鱼岛是中国的&#xff01; Buffalo是一家正宗日资企业&#xff0c;在这个敏感时期本来还是准备用华硕的RT-N10,但是公司采购华硕的RT-N10/N12/N13U的价格都比较离谱&#xff0c;所以把目光投向了这家日资企业…

java buffalo_当我传递中间件配置时,如何允许Buffalo(gobuffalo)中间件的skip()方法?...

我正在尝试创建一个自定义Buffalo(gobuffalo)中间件&#xff0c;它接受正在运行的配置 . 问题是我失去了使用此错误跳过中间件功能的能力&#xff1a; actions / app.go:63:22&#xff1a;不能使用myMiddlewareFunc(类型为func(myConfig)buffalo.MiddlewareFunc)作为app.Middle…

Buffalo Barricades 题解

Buffalo Barricades 题解 这题的难点在于某一头牛可能被多个农名占有。怎么处理呢&#xff1f; 我们仔细分析一下就会发现&#xff0c;每一个农名的篱笆最多被一个篱笆直接包含&#xff0c;所以我们把这些之间包含的农名之间连上边&#xff0c;最终形成的是一个森林。 但是我…

golang-buffalo框架

关于c.value("tx").(*pop.connection) var s x.(T) //语法为golang的类型断言, 如果x不为nil,且可以转换为T类型,则断言成功,返回一个T类型的变量 s, 如果T为接口,则要求x实现T,如果断言失败 panic c.valule() //获取context中的值,关于tx在下面 buffalo.context返回…

BUFFALO路由器,远程,端口映射

如上图所示&#xff0c;设置后&#xff0c;远程172.18.60.115即可远程到路由器配置IP为192.168.1.59那台PC 以上详细 右上角172.18.60.115为路由器IP 设置DMZ的IP192.168.1.59为想要访问的PC的IP 设置路由器网段192.168.1.1 路由器中DMZ主机是指什么&#xff0c;具体有什么…

7620a路由mysql_MT7620A路由刷DDWRT 及2.4G无线设置经验

本帖最后由 overthink 于 2015-6-15 15:10 编辑 MT7620A路由刷DDWRT 及2.4G无线设置经验 用了N久的buffalo WHR-HP-G54,刷了DDWRT,以前做主路由,后来我用ROS做主路由后WHR-HP-G54就用做AP接入了,一直很稳定,信号也不错,就是速度才54Mbps有点慢,顺手换了吧,入了一个MT76…

java buffalo_随你怎么玩!Buffalo 网络硬盘新潮流

现代时尚的办公环境是怎样的&#xff1f;ADSL、无线网络、笔记本、还有咖啡&#xff0c;惬意地被沙发包裹起来&#xff0c;自由自在地网上冲浪……&#xff1b;当然仅仅有这些还是不够&#xff0c;我们需要视频会议、需要网络下载、甚至打印、扫描&#xff0c;还有需要随时随地…

java buffalo_buffalo文档之buffalo-demo(1)--除法运算器

buffalo文档之buffalo-demo(1)&#xff0d;&#xff0d;除法运算器 buffalo官方站&#xff1a;国内的ajax,amowa开源项目 doc.simle.jsp /p> "http://www.w3.org/TR/html4/loose.dtd">除法运算器 var endPoint"/BUFFALO"; var buffalo new Buffalo(…

java buffalo_初玩Buffalo

页面调用服务器的一个类里面的方法&#xff0c;做下面的步骤就可以了&#xff0c;前提是你配置好了buffalo那个demo。 只需执行下面三个步骤&#xff0c;就可以完成一个简单的乘法调用。 Spring例子(使用于1.2以前的版本) 1) HTML页面上 /buffalo/WebContent/pages/simple.h…

基于线性准则的考虑风力发电不确定性的分布鲁棒优化机组组合(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

Android聚合SDK母包反编译出包教程

文章目录 【前言】一、SDK预处理1、SDK资源合并1.1、合并res目录下的资源1.2、合并libs目录1.3、合并assets目录1.4、合并AndroidManifest.xml1.5、合并jar 2、jar转smali2.1、jar 混淆合并2.2、jar转dex2.3、dex转smali 二、母包apk反编译1、删除母包模板代码1.1、删掉母包SDK…

Day09 文件操作相关

第二模块 函数&模块 从今天开始&#xff0c;我们将进入系列课程第二模块的的学习。 第一模块主要是学习python基础知识&#xff0c;从第二模块开始就可以通过程序去解决工作中实际的问题。 从今天开始&#xff0c;我们将进入第二模块的学习&#xff0c;此模块主要包含两大…

android dialog 不全屏,Android Dialog无法填满屏幕宽度问题解决

就是将上面的自定义布局放到一个Dialog里面,布局xml android:layout_width="match_parent" android:layout_height="155dp" android:background="@color/transparent" android:paddingLeft="0dp" android:paddingRight="0dp&quo…

Android硬编码——音频编码、视频编码及音视频混合

视频编解码对许多Android程序员来说都是Android中比较难的一个知识点。在Android 4.1以前&#xff0c;Android并没有提供硬编硬解的API&#xff0c;所以之前基本上都是采用FFMpeg来做视频软件编解码的&#xff0c;现在FFMpeg在Android的编解码上依旧广泛应用。本篇博客主要讲到…

android兼容huawei手机刘海屏解决方案

引用自华为官方文档&#xff1a;doc/50114 &#xff0c;这里缩减了一些内容&#xff0c;捡取重要内容。 转载请标明出处&#xff1a; https://blog.csdn.net/djy1992/article/details/80683575 本文出自:【奥特曼超人的博客】 推荐&#xff1a; android 兼容所有刘海屏的方…
最新文章