Lvat_s Blog

有神犇@cooordi留言说我好多坑没填……

正好最近也颓废了几天了，不能再颓废了。

我明年还可以去NOI,机会还是有的

但是，不做题永远没有机会

必须填坑！

这篇博文用来记录我填好的坑。

2016/7/31 3:00

简易FFT教程 填坑完成

2016/8/1 21:30

更了一堆文章,好累(懒)啊明天再更

小伙伴们从四川回来了

5Au 4Ag 1Cu

lyz大爷高一随手Au，day2考246成功虐场

太强了%%%

而我在家连超哥线段树都不会（这两者有什么关系……）

还有好多坑没填

所以补一下

考虑标记永久化

计算断点位置对应的区间，确定怎么传标记

一开始我YY了一种写法，始终不过

后来发现情况少考虑了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=100005;

int n;
char s[10];
double ans;

struct SegTree{
int l,r;
double k,b;
inline double V(int x){return k*x+b;}
}tree[N<<2];

void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].k=tree[rt].b=0;
if(l==r)return;
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
}

double Cross(double k1,double b1,double k2,double b2){return (b2-b1)/(k1-k2);}

void Insert(int rt,double k,double b){
if(k*tree[rt].l+b<=tree[rt].V(tree[rt].l) && k*tree[rt].r+b<=tree[rt].V(tree[rt].r))return;
else if(k*tree[rt].l+b>=tree[rt].V(tree[rt].l) && k*tree[rt].r+b>=tree[rt].V(tree[rt].r)){tree[rt].k=k;tree[rt].b=b;return;}
int mid=tree[rt].l+tree[rt].r>>1;
double x=Cross(k,b,tree[rt].k,tree[rt].b);
if(k*tree[rt].l+b>=tree[rt].V(tree[rt].l)){
	if(x<=mid)Insert(rt<<1,k,b);
    else Insert(rt<<1|1,tree[rt].k,tree[rt].b),tree[rt].k=k,tree[rt].b=b;
}
else {
	if(x>mid)Insert(rt<<1|1,k,b);
    else Insert(rt<<1,tree[rt].k,tree[rt].b),tree[rt].k=k,tree[rt].b=b;
}
}

void Query(int rt,int x){
ans=max(ans,tree[rt].V(x));
if(tree[rt].l==tree[rt].r)return;
int mid=tree[rt].l+tree[rt].r>>1;
if(x<=mid)Query(rt<<1,x);
else Query(rt<<1|1,x);
}

int main(){
freopen("1568.in","r",stdin);
freopen("1568.out","w",stdout);
scanf("%d",&n);
Build(1,1,50000);
for(int i=1;i<=n;i++){
    scanf("%s",s);
    if(s[0]=='P'){double k,b;scanf("%lf %lf",&b,&k);Insert(1,k,b-k);}
    else {int x;scanf("%d",&x);ans=0;Query(1,x);printf("%lld\n",(long long)floor(ans/100.0));/*printf("%lf\n",ans);*/}
}
return 0;
}