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/xkoito_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