题目链接
https://www.luogu.org/problemnew/show/P4254
思路
超哥线段树模板题
若当前线段完全高于标记线段, 则将当前线段进行标记
若当前线段完全低于标记线段, 则将当前线段扔掉
若当前线段与标记线段有交点, 考虑在上面的一部分是一个两条线段形成的分段函数, 将长的线段作为当前节点的标记, 短的线段继续下放
代码
- #include <iostream>
- #include <cstdio>
- #define ls rt<<1
- #define rs rt<<1|1
- using namespace std;
- const int N=1e5+7;
- int read() {
- int x=0,f=1;char s=getchar();
- for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
- for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
- return x*f;
- }
- int tr[N<<2];
- double a[N],b[N];
- double f(int x,int l) {return a[x]*l+b[x];}
- int cmp(int x,int y,int r) {return f(x,r)>=f(y,r);}
- void modify(int l,int r,int k,int rt) {
- if(l==r) {
- if(cmp(k,tr[rt],l)) tr[rt]=k;
- return;
- }
- int mid=(l+r)>>1;
- if(a[k]>a[tr[rt]])
- if(cmp(k,tr[rt],mid))
- modify(l,mid,tr[rt],ls),tr[rt]=k;
- else
- modify(mid+1,r,k,rs);
- if(a[k]<a[tr[rt]])
- if(cmp(k,tr[rt],mid))
- modify(mid+1,r,tr[rt],rs),tr[rt]=k;
- else
- modify(l,mid,k,ls);
- }
- double query(int l,int r,int L,int rt) {
- if(l==r) return f(tr[rt],L);
- int mid=(l+r)>>1;
- double ans=0;
- if(L<=mid) return max(f(tr[rt],L),query(l,mid,L,ls));
- else return max(f(tr[rt],L),query(mid+1,r,L,rs));
- }
- int main() {
- int n=read();
- char s[10];
- for(int i=1;i<=n;++i) {
- scanf("%s",s);
- if(s[0]=='Q') {
- int id=read();
- printf("%d\n",(int)(query(1,n,id,1))/100);
- } else {
- scanf("%lf%lf",&b[i],&a[i]);
- b[i]-=a[i];
- modify(1,n,i,1);
- }
- }
- return 0;
- }
- /*
- 100
- Query 30
- Project 5.52800 0.96000
- Query 24
- Project -409.19200 18.24000
- Project -209.51200 13.24800
- Project -2.15200 2.88000
- Query 20
- Project 0.15200 2.49600
- Query 34
- 0
- 0
- 0
- 2
- */
来源: http://www.bubuko.com/infodetail-2947533.html