如何建设自己的php网站,对网页设计作品的意见,辽宁同鑫建设有限公司网站,竞价推广代运营企业正题
题目链接:http://172.17.55.160/contest/117/problem/1 题目大意 nnn个数的一个序列#xff0c;给其中的一些数打上标记。 一个标记方案的贡献为s1s_1s1表示有多少对L,RL,RL,R满足区间[L,R][L,R][L,R]都被打上了标记#xff0c;s2s_2s2表示标记的数字和。贡献为s1−…正题
题目链接:http://172.17.55.160/contest/117/problem/1 题目大意
nnn个数的一个序列给其中的一些数打上标记。 一个标记方案的贡献为s1s_1s1表示有多少对L,RL,RL,R满足区间[L,R][L,R][L,R]都被打上了标记s2s_2s2表示标记的数字和。贡献为s1−s2s_1-s_2s1−s2
mmm次询问修改一个数后求最大的可能贡献询问之间相互独立
1≤n,m≤3×1051\leq n,m\leq 3\times 10^51≤n,m≤3×105 解题思路
先把答案减去一个∑i1nai\sum_{i1}^na_i∑i1nai这样就变为对于一段[L,R][L,R][L,R]要么选择s1s_1s1要么选择s2s_2s2 先考虑不带修改怎么搞设fif_ifi表示前iii个的最大贡献。
定义si∑j1iais_i\sum_{j1}^ia_isi∑j1iai然后有方程 fimax{fjmax{si−sj,(i−j2)}}f_imax\{f_jmax\{s_i-s_j,\binom{i-j}{2}\}\}fimax{fjmax{si−sj,(2i−j)}} 这个东西可以斜率优化搞考场上犯病写了个CDQCDQCDQ调了我半天
然后带修改考虑到每次只会影响一个数字可以理解为一个前缀和后缀拼起来。把刚刚那个dpdpdp再反过来做一次记为gig_igi。
那么现在对于修改的位置xxx我们要么选择xxx要么跨过xxx也就是最大化 max{fjgisi−1−sj,fjgi(i−j−12)}(i∈[0,x−1],j∈[x1,n1])max\{f_jg_is_{i-1}-s_j,f_jg_i\binom{i-j-1}{2}\}(i\in[0,x-1],j\in[x1,n1])max{fjgisi−1−sj,fjgi(2i−j−1)}(i∈[0,x−1],j∈[x1,n1]) 前面那个可以把两个前/后缀的max的fj−sjf_j-s_jfj−sj和gisi−1g_is_{i-1}gisi−1加起来就好了。
后面那个考虑分治我们每次分治到一个位置[l,mid,r][l,mid,r][l,mid,r]如果需要往左走就统计i∈[0,l−1]i\in[0,l-1]i∈[0,l−1]和j∈[mid1,r]j\in[mid1,r]j∈[mid1,r]的答案。右边同理。
因为我们的每次的时间复杂度是外面的大小所以我们可以维护一个前后缀的凸壳然后在上面二分时间复杂度就是O(nlog2n)O(n\log^2 n)O(nlog2n)的。
同时维护两个凸壳需要回溯所以很麻烦分开两次正反做一次就好了。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) code
考场代码有点丑
#includecstdio
#includecstring
#includealgorithm
#includevector
#define ll long long
using namespace std;
const ll N3e510,inf1e18;
ll n,m,ans,lmax,rmax,top,st[N],suf[N];
ll a[N],f[N],g[N],s[N],prt[N],w[N],yf[N];
vectorll q[N];
ll px(ll x,ll *f)
{return f[x]*2x*x-x;}
ll xj(ll x1,ll y1,ll x2,ll y2)
{return x1*y2-x2*y1;}
ll xl(ll a,ll b,ll c,ll *f){ll y1px(b,f)-px(a,f),x1b-a;ll y2px(c,f)-px(a,f),x2c-a;return xj(x1,y1,x2,y2);
}
ll ck(ll l,ll r,ll *f)
{return f[l](r-l1)*(r-l)/2;}
ll solve(ll l,ll r,ll *f){if(lr)return f[l]-s[l];ll mid(lr)1;ll maxssolve(l,mid,f);top0;for(ll il;imid;i){while(top1xl(st[top-1],st[top],i,f)0)top--;st[top]i;}for(ll imid1;ir;i){while(top1ck(st[top],i,f)ck(st[top-1],i,f))top--;f[i]max(f[i],max(ck(st[top],i,f),s[i]maxs));}maxsmax(maxs,solve(mid1,r,f));return maxs;
}
ll cw(ll l,ll r)
{return f[l]g[r](r-l-1)*(r-l)/2;}
ll xll(ll a,ll b,ll c){ll y1(yf[b]-yf[a])*2,x1b-a;ll y2(yf[c]-yf[a])*2,x2c-a;return xj(x1,y1,x2,y2);
}
ll xlr(ll a,ll b,ll c){ll y1yf[b]-yf[a],x1(n-b1)-(n-a1);ll y2yf[c]-yf[a],x2(n-c1)-(n-a1);return xj(x1,y1,x2,y2);
}
void calc(ll L,ll R){if(LR){for(ll i0;iq[L].size();i){ll xq[L][i],tmp;prt[x]max(ans-w[x]a[L]-s[n],prt[x]);}while(top1xll(st[top-1],st[top],L)0)top--;st[top]L;return;}ll mid(LR)1,paans;if(top){for(ll imid1;iR;i){ll l1,rtop-1;while(lr){ll x(lr)1;if(cw(st[x],i)cw(st[x1],i))lx1;else rx-1;}ansmax(ans,cw(st[l],i));}}calc(L,mid);anspa;calc(mid1,R);return;
}
void cblc(ll L,ll R){if(LR){for(ll i0;iq[L].size();i){ll xq[L][i],tmp;prt[x]max(ans-w[x]a[L]-s[n],prt[x]);}while(top1xlr(st[top-1],st[top],L)0)top--;st[top]L;return;}ll mid(LR)1,paans;if(top){for(ll iL;imid;i){ll l1,rtop-1;while(lr){ll x(lr)1;if(cw(i,st[x])cw(i,st[x1]))lx1;else rx-1;}ansmax(ans,cw(i,st[l]));}}cblc(mid1,R);anspa;cblc(L,mid);return;
}
signed main()
{freopen(score.in,r,stdin);freopen(score.out,w,stdout);scanf(%lld,n);for(ll i1;in;i)scanf(%lld,a[n-i1]);for(ll i1;in;i)s[i]s[i-1]a[i];solve(0,n,g);for(ll i1;in-i1;i)swap(a[i],a[n-i1]),swap(g[i],g[n-i1]);for(ll i1;in;i)s[i]s[i-1]a[i];solve(0,n,f);scanf(%lld,m);for(ll i1;im;i){ll x;scanf(%lld%lld,x,w[i]);q[x].push_back(i);}suf[n2]-inf;for(ll in1;i1;i--)suf[i]max(suf[i1],g[i]s[i-1]);for(ll i0,pre-inf;in;i){for(ll j0;jq[i].size();j){ll xq[i][j];prt[x]suf[i1]pre-s[n];}premax(pre,f[i]-s[i]);}ans-inf;top0;for(ll i1;in;i)yf[i]f[i]*2i*ii;calc(0,n1);ans-inf;top0;for(ll i1;in;i)yf[i]g[i]*2(n-i1)*(n-i1)(n-i1);cblc(0,n1);for(ll i1;im;i)printf(%lld\n,max(prt[i],0ll));return 0;
}
