BZOJ 1568: [JSOI2008]Blue Mary开公司(超哥线段…
2018-06-17 22:06:00来源:未知 阅读 ()
1568: [JSOI2008]Blue Mary开公司
Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 1080 Solved: 379
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
Project 5.10200 0.65000
Project 2.76200 1.43000
Query 4
Query 2
Project 3.80200 1.17000
Query 2
Query 3
Query 1
Project 4.58200 0.91000
Project 5.36200 0.39000
Sample Output
0
0
0
0
HINT
Source
超哥线段树的模板题。
超哥线段树是处理一次函数的一种线段树,
在超哥线段树中,每一个节点保存着一个一次函数所对应的编号,
那他是怎么保存的呢?
借用一位大神的图片
没错就是这样,
然后对于每一次插入操作,
我们去递归当前 值小的节点 的值 可能比 值大的节点 的 值 大的方向。。。。。。。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<bitset> #define ls k<<1 #define rs k<<1|1 using namespace std; const int MAXN=1000001; inline void read(int &n) { char c='+';int x=0;bool flag=0; while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();} n=flag==1?-x:x; } struct funtion { double k,b; }a[MAXN];// 记录每一条线段 int tree[MAXN];// 每一个节点所对应线段的编号 int tot=0;// 总的线段数量 inline int pd(int now,int will,int day) { --day; return a[now].k*day+a[now].b>a[will].k*day+a[will].b; } inline void insert(int k,int l,int r,int now) { if(l==r) { if(pd(now,tree[k],l)) tree[k]=now; return ; } int mid=(l+r)>>1; if(a[now].k>a[tree[k]].k)// 当前点的斜率比目标点的斜率大 { if(pd(now,tree[k],mid)) insert(ls,l,mid,tree[k]),tree[k]=now; else insert(rs,mid+1,r,now); } else { if(pd(now,tree[k],mid)) insert(rs,mid+1,r,tree[k]),tree[k]=now; else insert(ls,l,mid,now); } } double ans=0; void query(int k,int l,int r,int now) { ans=max(ans,a[tree[k]].k*(now-1)+a[tree[k]].b); if(l==r) return ; int mid=(l+r)>>1; if(now<=mid) query(ls,l,mid,now); else query(rs,mid+1,r,now); } int main() { ios::sync_with_stdio(0); int n; cin>>n; for(int i=1;i<=n;i++) { string opt; cin>>opt; if(opt[0]=='P') { ++tot; cin>>a[tot].b>>a[tot].k; insert(1,1,n,tot); } else if(opt[0]=='Q') { int p; cin>>p; ans=0; query(1,1,n,p); printf("%d\n",(int)(ans/100)); } } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:离散化模板
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash