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

Supercomputer 解题报告

原文：https://www.cnblogs.com/butterflydew/p/10601280.html