厦门 网站建设,做非法网站判什么邢,服装网站建设公司好吗,大连建设科技网站Supercomputer 设\(f_i\)为前\(i\)个时间内必须的完成的任务个数#xff0c;那么答案就是\[ \max_{i}\lceil\frac{f_i}{i}\rceil \] 现在要支持区间加和全局\(\max\) 考虑分块#xff0c;对每个块维护一个\(tag\)表示加标记 块内的\(\max\)则为\[ \max_i \frac{1}{i}\times t…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 N1e510;
const int B350;
template class T
void read(T x)
{x0;char cgetchar();while(!isdigit(c)) cgetchar();while(isdigit(c)) xx*10c-0,cgetchar();
}
int n,m,q,ans,T,L[B],R[B],belong[N],yuy[N];
struct koito_yuu
{int x,y;//k1/x,by/xkoito_yuu(){}koito_yuu(int X,int Y){xX,yY;}
};
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){tot0;for(int iL[x];iR[x];i){koito_yuu potkoito_yuu(i,yuy[i]);while(tot1ck(pot,s[tot],s[tot-1])) --tot;s[tot]pot;}}void Move(){while(tot1(1ll*(tags[tot].y)*s[tot-1].x)1ll*(tags[tot-1].y)*s[tot].x) --tot;ansmax(ans,(tags[tot].y-1)/s[tot].x1);}
}bee[B];
void query()
{for(int i1;iT;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,i1;im;i) read(x),yuy[x];for(int i1;in;i) yuy[i]yuy[i-1];int bsqrt(n)1;T(n-1)/b1;for(int i1;iT;i){L[i]R[i-1]1,R[i]min(i*b,n);for(int jL[i];jR[i];j) belong[j]i;bee[i].build(i);}query();printf(%d\n,ans);for(int k,v,i1;iq;i){read(k),read(v);int blbelong[v];for(int jv;jR[bl];j) yuy[j]k;bee[bl].build(bl);for(int jbl1;jT;j) bee[j].tagk;query();printf(%d\n,ans);}return 0;
} 2019.3.26 转载于:https://www.cnblogs.com/butterflydew/p/10601280.html
