Supercomputer 解题报告

时间：2021-07-11 11:39:09

Supercomputer

Supercomputer 解题报告

设\(f_i\)为前\(i\)个时间内必须的完成的任务个数，那么答案就是

\[\max_{i}\lceil\frac{f_i}{i}\rceil
\]

现在要支持区间加和全局\(\max\)

考虑分块，对每个块维护一个\(tag\)表示加标记

块内的\(\max\)则为

\[\max_i \frac{1}{i}\times tag+\frac{f_i}{i}
\]

则把\(k=\frac{1}{i},b=\frac{f_i}{i}\)，就对一个块维护一个关于直线的上凸壳

然后发现\(tag\)是单增的，所以可以均摊\(O(n)\)的在每个块的凸壳上维护

修改的时候不满一块的暴力重构块，否则打tag上去

Code:

#include <cstdio>

#include <cctype>

#include <cmath>

#include <algorithm>

#define ll long long

using std::max;

using std::min;

const int N=1e5+10;

const int B=350;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

int n,m,q,ans,T,L[B],R[B],belong[N],yuy[N];

struct koito_yuu

{

	int x,y;

	//k=1/x,b=y/x

	koito_yuu(){}

	koito_yuu(int X,int Y){x=X,y=Y;}

};

bool ck(koito_yuu a,koito_yuu b,koito_yuu c)

{

	return (1.0*a.x*b.y-1.0*b.x*a.y)*(c.x-b.x)>=(1.0*b.x*c.y-1.0*c.x*b.y)*(b.x-a.x);

}

struct Block

{

	koito_yuu s[B];

	int tot,tag;

	void build(int x)

	{

	    tot=0;

		for(int i=L[x];i<=R[x];i++)

		{

			koito_yuu pot=koito_yuu(i,yuy[i]);

			while(tot>1&&ck(pot,s[tot],s[tot-1])) --tot;

			s[++tot]=pot;

		}

	}

	void Move()

	{

		while(tot>1&&(1ll*(tag+s[tot].y)*s[tot-1].x)<=1ll*(tag+s[tot-1].y)*s[tot].x) --tot;

		ans=max(ans,(tag+s[tot].y-1)/s[tot].x+1);

	}

}bee[B];

void query()

{

	for(int i=1;i<=T;i++)

		bee[i].Move();

}

int main()

{

    freopen("computer.in","r",stdin);

    freopen("computer.out","w",stdout);

	read(n),read(m),read(q);

	for(int x,i=1;i<=m;i++) read(x),++yuy[x];

	for(int i=1;i<=n;i++) yuy[i]+=yuy[i-1];

	int b=sqrt(n)+1;T=(n-1)/b+1;

	for(int i=1;i<=T;i++)

	{

		L[i]=R[i-1]+1,R[i]=min(i*b,n);

		for(int j=L[i];j<=R[i];j++) belong[j]=i;

		bee[i].build(i);

	}

	query();

	printf("%d\n",ans);

	for(int k,v,i=1;i<=q;i++)

	{

		read(k),read(v);

		int bl=belong[v];

		for(int j=v;j<=R[bl];j++) yuy[j]+=k;

		bee[bl].build(bl);

		for(int j=bl+1;j<=T;j++) bee[j].tag+=k;

		query();

		printf("%d\n",ans);

	}

	return 0;

}

2019.3.26

相关文章