李超线段树

cwy posted @ 2018年1月10日 21:07 in 板子 , 45 阅读

BZOJ1568

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
double ans,tagk[500010],S,P,tagb[500010];
bool flag[500010];
char s[666];
int n,x,T;
double crs(double k1,double b1,double k2,double b2){
	return (b2-b1)/(k1-k2);
}
void ins(int l,int r,int rt,double K,double B){
	if (!flag[rt]){
		flag[rt]=1;
		tagk[rt]=K;
		tagb[rt]=B;
		return;
	}
	int m=l+r>>1;
	double f1=K*l+B,f2=tagk[rt]*l+tagb[rt],f3=K*r+B,f4=tagk[rt]*r+tagb[rt];
	if (f2>=f1 && f4>=f3) return;
	if (f1>=f2 && f3>=f4){
		tagk[rt]=K,tagb[rt]=B;
		return;
	}
	double t=crs(K,B,tagk[rt],tagb[rt]);
	if (f1>=f2){
		if (t<=m){
			ins(l,m,rt<<1,K,B);
		}
		else{
			ins(m+1,r,rt<<1|1,tagk[rt],tagb[rt]);
			tagk[rt]=K,tagb[rt]=B;
		}
	}
	else{
		if (t<=m){
			ins(l,m,rt<<1,tagk[rt],tagb[rt]);
			tagk[rt]=K,tagb[rt]=B;
		}
		else{
			ins(m+1,r,rt<<1|1,K,B);
		}
	}
}
void que(int l,int r,int rt,int x){
	ans=max(ans,tagk[rt]*x+tagb[rt]);
	if (l==r) return;
	int m=l+r>>1;
	if (x<=m) que(l,m,rt<<1,x);
	else que(m+1,r,rt<<1|1,x);
}
int main(){
	T=50000;
	scanf("%d",&n);
	FOR(i,1,n){
		scanf("%s",s);
		if (s[0]=='Q'){
			getint(x);
			ans=0.0;
			que(1,T,1,x);
			printf("%lld\n",(long long)(ans/100));
		}
		else{
			scanf("%lf%lf",&S,&P);
			ins(1,T,1,P,S-P);
		}
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter