P8049 [COCI 2010/2011 #5] DVONIZ加强版题目背景题面与原题P7635 [COCI2010-2011#5] DVONIZ无异仅有数据范围时空限制与分值不同。题目描述当前K KK个元素的和或最后K KK个元素的和都不大于S SS时我们说这个2 × K 2\times K2×K个元素的序列是有趣的。给出一个长度为N NN的序列A AA。对于每个元素输出从该元素开始的最长的有趣的子段。输入格式第一行包含整数N NN和S SS。下面的N NN行每行包含序列A AA中的一个整数A i A_iAi​。这些整数都是正的且它们的和不超过2 × 10 9 2\times 10^92×109。输出格式输出共N NN行。第i ii行包含一个整数表示从第i ii元素开始的最长的有趣的子段的长度。如果当前位置上没有有趣的子段输出0。输入输出样例 #1输入 #15 10000 1 1 1 1 1输出 #14 4 2 2 0输入输出样例 #2输入 #25 9 1 1 10 1 9输出 #22 0 0 2 0输入输出样例 #3输入 #38 3 1 1 1 1 1 1 1 1输出 #36 6 6 4 4 2 2 0说明/提示【样例解释#1】对于样例1 11的第一个位置一共有4 44个子段且都满足条件故取最长的长度为4 44的子段。【数据范围】对于30 % 30\%30%的数据2 ≤ N ≤ 200 2\le N \le 2002≤N≤200。对于50 % 50\%50%的数据2 ≤ N ≤ 5 × 10 3 2\le N \le 5 \times 10^32≤N≤5×103。对于70 % 70\%70%的数据2 ≤ N ≤ 2 × 10 5 2 \le N \le 2 \times 10^52≤N≤2×105。对于100 % 100\%100%的数据2 ≤ N ≤ 3 × 10 6 2\le N \le 3 \times 10^62≤N≤3×1061 ≤ S ≤ 10 9 1\le S \le 10^91≤S≤1091 ≤ A i ≤ 10 9 1\le A_i \le 10^91≤Ai​≤109。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;intn,m,a[3000001],l,r,mid,f[3000001];boolcheck(intx,inty){returna[x]-a[x-y]ma[xy]-a[x]m;}signedmain(){cinnm;for(inti1;in;i){cina[i];a[i]a[i-1];}for(inti1;in;i){l0,rmin(i,n-i);while(lr){midlr11;if(check(i,mid))lmid;elsermid-1;}f[i-l1]max(f[i-l1],2*l);}for(inti1;in;i)f[i]max(f[i],f[i-1]-2);for(inti1;in;i)coutf[i]\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容