【Codeforces 8VC Venture Cup 2016 - Elimination Round】G Raffles

  随便来个数据结构维护一下就好了...不知道为什么把它放在G题。

  根据官方题解里的说法，除了第一次分配，其他时刻James最多移动一张彩票的位置。（好像挺显然的？）

  保险起见还是写了移动多个的。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=200010;
const double eps=1e-8;

int p[maxn];
int l[maxn];
double inc[maxn],dec[maxn];
int num[maxn];
int n,tickets,q;
double ans;

double Calc(int x,int pnum) {return (double)p[x]*pnum/(l[x]+pnum);}
double Changev(int x,int v) {if (num[x]+v>l[x]) return 0;if (num[x]+v<0) return 1e10;return fabs(Calc(x,num[x])-Calc(x,num[x]+v));}

struct Segment_Tree
{
	int incmax[maxn<<2],decmin[maxn<<2];
	int ID[maxn];
	
	#define ls (o<<1)
	#define rs (o<<1|1)
	#define fa (o>>1)
	#define mid ((l+r)>>1)
	
	void Update(int o)
	{
		incmax[o]=(inc[incmax[ls]]>inc[incmax[rs]])?incmax[ls]:incmax[rs];
		decmin[o]=(dec[decmin[ls]]<dec[decmin[rs]])?decmin[ls]:decmin[rs];
	}
	
	void Build_Tree(int o,int l,int r)
	{
		if (l==r) {incmax[o]=decmin[o]=l;ID[l]=o;return;}
		Build_Tree(ls,l,mid);
		Build_Tree(rs,mid+1,r);
		Update(o);
	}
	
	int Inc_Max() {return incmax[1];}
	int Dec_Min() {return decmin[1];}
	void Change(int x,int v,int ctr)
	{
		int o=ID[x];
		ans-=Calc(x,num[x]);
		if (ctr==0) l[x]+=v;else num[x]+=v;
		ans+=Calc(x,num[x]);
		inc[x]=Changev(x,1);dec[x]=Changev(x,-1);
		while (o) Update(o>>=1);
	}
}T;

int main()
{
	scanf("%d%d%d",&n,&tickets,&q);
	for (int i=1;i<=n;i++) scanf("%d",&p[i]);
	for (int i=1;i<=n;i++) scanf("%d",&l[i]);
	for (int i=1;i<=n;i++) inc[i]=Changev(i,1),dec[i]=Changev(i,-1);
	T.Build_Tree(1,1,n);
	while (tickets)
	{
		int incp=T.Inc_Max();
		if (fabs(inc[incp])<eps) break;
		T.Change(incp,1,1);
		tickets--;
	}
	for (int i=1;i<=q;i++)
	{
		int t,r;
		scanf("%d%d",&t,&r);
		if (t==1) T.Change(r,1,0);else T.Change(r,-1,0);
		if (num[r]>l[r]) T.Change(r,-1,1),tickets++;
		
		int incp=T.Inc_Max(),decp=T.Dec_Min();
		while (tickets && fabs(inc[incp])>eps)
		{
			T.Change(incp,1,1);
			tickets--;
			incp=T.Inc_Max();
		}
		while (inc[incp]>dec[decp])
		{
			T.Change(incp,1,1);
			T.Change(decp,-1,1);
			incp=T.Inc_Max(),decp=T.Dec_Min();
		}
		printf("%f\n",ans);
	}
	return 0;
}

  我上面的代码里打的是线段树，然而其实只要两个堆就够了。