bzoj1568: [JSOI2008]Blue Mary开公司 三分+二分+线段树

#include<cstdio>
#define Z int l=1,int r=N,int k=1
#define N 50000
#define M (l+r>>1)
#define P (k<<1)
#define S (k<<1|1)
#define K l,r,k
#define L l,M,P
#define R M+1,r,S
double a[N*4],b[N*4];
void devolve(Z){
	if(b[k]){
		a[S]=a[k]+(M-l+1)
		*(b[P]=b[S]=b[k]);
		a[P]=a[k],b[k]=0;
	}
}
double query(int s,Z){
	if(l!=r){
		devolve(K);
		return s<=M
		?query(s,L)
		:query(s,R);
	}
	return a[k];
}
void amend(double u,
double v,int s,int t,Z){
	if(s==l&&t==r)
		a[k]=u,b[k]=v;
	else{
		devolve(K);
		if(t<=M)
			amend(u,v,s,t,L);
		else if(s>M)
			amend(u,v,s,t,R);
		else{
			amend(u,v,s,M,L);
			amend(u+(M-s
			+1)*v,v,M+1,t,R);
		}
	}
}
double s,t;
int i,j,m,r,l;
char k[8];
void solve(){
	scanf("%lf%lf",&s,&t);
	l=1,r=N;
	while(l!=r){
		i=l+(r-l)/3;
		j=r-(r-l)/3;
		if(t*(i-j)
		<query(i)-query(j))
			l=i+1;
		else r=j-1;
	}
	if(s+t*l-t>query(l)){
		r=l,l=1;
		while(l!=r){
			i=l+r>>1;
			if(s+t*i-t>query(i))
				r=i;
			else l=i+1;
		}
		j=l,r=N;
		while(l!=r){
			i=l+r+1>>1;
			if(s+t*i-t>query(i))
				l=i;
			else r=i-1;
		}
		amend(s+t*j-t,t,j,l);
	}
}
int main(){
	for(scanf("%d",&m);m;--m){
		scanf("%s",k);
		if(*k==80)solve();
		else{
			scanf("%d",&i);
			printf("%d\n",
			(int)query(i)/100);
		}
	}
}