题解 CF212D 【Cutting a Fence】

~~真的，已经不想说什么了，这道题出的真的太好了……orzorzorz~~ - 对于每个数a[x]在它左边找一个离它最近的小于它的数，在它右边找一个离它最近 的小于等于它的数 记所找到左边数的位置为 _l_ ,所找到右边数的位置为 _r_ 。 **那么在[ _l_ +1, _r_ -1]中的所有子区间，只要包含a[x]，最小值都是a[x]** - 设a[x]到a[ _l_ +1]长度为L，a[x]到a[ _r_ -1]长度为R 当第二问的区间长度为K时(K是个变量)，把所有长度为K的区间最小值的和设为Sum 我们开始分类讨论 设L<=R ① 当1<=K<=L,会有K个长度为K的区间的最小值是a[x]，Sum=Sum+K*a[x] ② 当L+1<=K<=R 会有L个长度为K的区间的最小值是a[x],Sum=Sum+L*a[x] ③ 当R+1<=K<=L+R-1 会有L+R-K个长度为K的区间的最小值a[x], Sum=Sum+a[x] (L+R-K)=Sum+a[x] (L+R)-K*a[x] 对于每一个a[x]，我们需要把它**对所有区间长度询问的答案贡献**求出 也就是对于每个Len(1<=len<=L+R-1)，我们都要根据上面分类讨论得出的结论， 算出对Sum的贡献。观察关于Sum的式子可以发现，只有K*a[x]才是一个会变化的值， 其余都是定值。 我们不妨设C1[K]是区间长度为K时,所有需要乘K的a[x]的和，C2[K]是区间长度为K时，所有定值的和。 设ans[K]是区间长度为K的答案，ans[K]=(K*C1[K]+C2[K])/(n-K+1) 我们需要预处理出所有区间长度的答案，然后O(1)解出每一个询问。 显然对于每一个a[x] (1<=x<=n),都会有一系列的K满足前面的三种讨论情况， 而每一个K，都会有一个C1[K],C2[K]，会发现，当连续的几个K都处于同一种情况的时候，所对应的C1[],C2[]增加的值是相等的，这就可以看作是区间加，可以用差分来做。 For Example 2 5 5 5 3 5 5 5 5 5 5 2 a[6]=3, L=4, R=7 当K取[1,4]时，对于a[6]会有4个区间满足最小值是a[6]的条件 那么 C1[1]=C1[1]+a[6], C1[2]=C1[2]+a[6], C1[3]=C1[3]+a[6], C1[4]=C1[4]+a[6] ——显然一个区间加 当K取[5,7]时,对于a[6]会有5个区间满足最小值是a[6]的条件 那么 C2[5]=C2[5]+4*a[6] C2[6]=C2[6]+4*a[6] C2[7]=C2[7]+4*a[6] ——显然一个区间加 当K取[8,10]时,对于a[6]会有11-K个区间满足最小值是a[6]的条件 那么 C1[8]=C1[8]+11*a[6] C1[9]=C1[9]+11*a[6] C1[10]=C1[10]+11*a[6] ——显然一个区间加 C2[8]=C2[8]-a[6] C2[9]=C2[9]-a[6] C2[10]=C2[10]-a[6] ——显然一个区间加 至于为什么对于每个数a[x]一个是找离它最近的小于它的数，另一个是找右边离它最近的小于等于它的数？ 同一个区间内最小值有多个的话，也只需要算一次，比如样例二的这种数据是会被多次计算的，[1,2]这个区间，a[1]的时候算一次，a[2]的时候算一次，所以为什么要这么做，你可以感性的理解为去重。 OK,OK，其余就看代码吧！ ```cpp #include<cstdio> #include<algorithm> #include<cstring> using namespace std; long long n,m,R[1000100],a[1000100],k,x,L[1001000],y,C1,C2; long long c1[1001000],c2[1001000]; double ans[1001000]; inline long long read() { long long cnt=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){cnt=cnt*10+ch-48;ch=getchar();} return cnt*f; } int main() { n=read(); for (int i=1;i<=n;i++) a[i]=read(); a[n+1]=-((long long)1<<60); a[0]=-((long long)1<<60); for (int i=n;i;i--) { if (a[i+1]<=a[i]) R[i]=i+1; else for (int j=R[i+1];j<=n+1;j=R[j]) if (a[j]<=a[i]) {R[i]=j;break;} } for (int i=1;i<=n;i++) { if (a[i-1]<a[i]) L[i]=i-1; else for (int j=L[i-1];j>=0;j=L[j]) if (a[j]<a[i]) {L[i]=j;break;} } for (int i=1;i<=n;i++) { L[i]=i-L[i]; R[i]=R[i]-i; } for (int i=1;i<=n;i++) { x=L[i];y=R[i]; if (x>y) swap(x,y); c1[1]+=a[i];c1[x+1]-=a[i]; c2[x+1]+=a[i]*x;c2[y+1]-=a[i]*x; c2[y+1]+=a[i]*(x+y);c2[x+y]-=a[i]*(x+y); c1[y+1]-=a[i];c1[x+y]+=a[i]; } for (int i=1;i<=n;i++) { C1+=c1[i]; C2+=c2[i]; ans[i]=((C1*i+C2)*1.0)/((n-i+1)*1.0); } m=read(); for (int i=1;i<=m;i++) { k=read(); printf("%.9lf\n",ans[k]); } return 0; } ``` LuckyCloud