看似二次函数
f(x)=a*x*x+b*x+c
因为b=a*2,其实是一次函数
g((x+1)^2)=a*((x+1)^2)-a+c
于是，题目转化为：给一堆直线g(x)=a*x+d，求某个点的最小值
换句话说，就是给一堆半平面，求交的下边界

两个序列：
A[i]
N[i]
表示：下边界中第i段的斜率为A[i],投影到x轴的范围是(N[i-1],N[i]]
其中，必有
A[0]>A[1]>A[2]>...
N[0]<N[1]<N[2]<...
并且，N[i]=(C[i+1]-A[i+1]-C[i]+A[i])/(A[i]-A[i+1])
这样，对于落到(N[i-1],N[i]]这个区间内的x,最小值就是A[i]*x*x+B[i]*x+C[i]

\                      /
 \                    /
  0                  2
   \                /
    \              /
     =======1======
        
    n[0]          n[1]
每次查找x点的最值就是找到i,满足N[i-1]<(x+1)^2<=N[i]，然后输出
A[i]*x*x+2*A[i]*x+C[i]就好了。

如何维护这两个序列呢？
很显然，用某种数据结构维护以A[i]为关键字的队列，然后套公式更新N[i]
如果发现N[i]>=N[i+1],那么把第i段删除,更新N[i-1]。
也就是：
I a b c:
  插入 a c 到  list,设插入他的位置是第i个
  计算  N[i],N[i-1]
  从i依次往后遍历，如果某个j满足B[j]>=B[j+1],那么删除第j个,计算N[j-1]
  从i再依次往前遍历，如果某个j满足B[j]>=B[j+1],那么删除第j个,计算N[j-1]

Q x
  查找最小i使(x+1)^2<=N[i]
  输出A[i]*x*x+2*A[i]*x+C[i]

关于数据结构的选择，我的思考是：
1.他必须要短，否则调不完
2.他必须要灵活，以便拓展（例如快速求前驱、后继）
3.他一定要省内存，有1000000个查询！

综上，我选择了treap和跳跃表，
但是跳跃表的内存很可能要超，于是选择了treap
与普通treap不同，这个treap顺便维护了每个接点的前驱 后继，也就是treap+双链表

关键代码：
struct node{
	int a,c,n,weight;
	node *next,*pre;
	node *lc,*rc;
	node(){next=pre=rc=lc=NULL;}
}；
int ran(){
	static int a=1325;
	a+=(a<<7)+1;
	a&=0x7fffffff;
	return a;
}
struct Treap{
	node *root;
	Treap(){root=NULL;}
	void link(node *p,node *q){
		if (p)p->next=q;
		if (q)q->pre=p;
	}
	node* ins(node *&p,node *q,int a,int c){
		node *r,*s;
		if (!p){
			p=etop++;p->a=a;p->c=c;p->weight=ran();
			if (q){
				if (q->lc==p){
					r=q;
					s=r->pre;
					link(s,p);link(p,r);
				}else if (q->rc==p){
					r=q;
					s=r->next;
					link(r,p);link(p,s);
				}
			}
			return p;
		}else{
			if (p->a==a){
				if (p->c<=c)return p;
				else return p->c=c,p;
			}else if (a>p->a){
				r=ins(p->lc,p,a,c);
				if (p->lc->weight>p->weight){
					s=p->lc;
					p->lc=s->rc;s->rc=p;p=s;
				}
			}else{
				r=ins(p->rc,p,a,c);
				if (p->rc->weight>p->weight){
					s=p->rc;
					p->rc=s->lc;s->lc=p;p=s;
				}
			}
			return r;
		}
	}
	node* ins(int a,int c){
		node *r=ins(root,NULL,a,c);
		return r;
	}
	void merge(node *&p,node *a,node *b){
		if (!a)p=b;
		else if (!b)p=a;
		else if (a->weight>b->weight){
			p=a;
			if (b->a>a->a)merge(a->lc,a->lc,b);
			else merge(a->rc,a->rc,b);
		}else{
			p=b;
			if (a->a>b->a)merge(b->lc,b->lc,a);
			else merge(b->rc,b->rc,a);
		}
	}
	void del(int a){
		node **p=&root,*r,*s;
		while ((*p)->a!=a){
			if (a>(*p)->a)p=&((*p)->lc);
			else p=&((*p)->rc);
		}
		r=(*p)->pre;s=(*p)->next;
		merge(*p,(*p)->lc,(*p)->rc);
		link(r,s);
	}
	node* find2(int y){
		node *p=root;
		while (1){
			if (p->n<y)p=p->rc;
			else if (p->pre && p->pre->n>=y)p=p->lc;
			else return p;
		}
		return NULL;
	}
}list;
void updata(node *p){if (!p)return;
	if (p->next){
		p->n=(p->next->c-p->c)/(p->a-p->next->a);
	}else p->n=100000001;
}
void Ins(int a,int c){
	int x,y;
	node *p=list.ins(a,c);
	updata(p);updata(p->pre);
	if (p->pre && p->pre->n>=p->n){
		list.del(p->a);
		updata(p->pre);
	}else{
		while (p->next && p->n>=p->next->n){
			list.del(p->next->a);
			updata(p);
		}
		while (p->pre && p->pre->pre && p->pre->pre->n>=p->pre->n){
			list.del(p->pre->a);
			updata(p->pre);
		}
	}
}
int Ask(int x){
	int y;
	if (x<10000)y=x*x;else y=100000000;
	node *p=list.find2(y);
	return p->a*x*x+p->c;
}
                scanf("%s",buf);
		if (buf[0]=='I'){
			scanf("%d %d %d",&a,&b,&c);
			Ins(a,c-a);
		}else{
			scanf("%d",&x);
			x++;
			if (x<0)x=-x;
			printf("%d\n",Ask(x));
		}

• Orz。其实就是维护斜率嘛。 (2) _gXX 2009-12-09 20:00:00