hdu5358 推公式+在一个区间内的尺取+枚举法

尺取+枚举，推出公式以后就是一个枚举加尺取

但是这题的尺取不是对一个值尺取，而是在一个区间内，所以固定左边界，尺取右边界即可

#include<bits/stdc++.h>

#define maxn 100005

#define ll long long

using namespace std;

int t,n,m,k,x,y,z,l,tot;

ll cnt,sum[maxn];

int a[maxn];

ll solve(ll L,ll R){//求区间[l,R)内i+j的和

    ll ans=;

    int l=,r=;

    for(int i=;i<=n;i++){

        if(l<i) l=i;

        if(r<i-) r=i-;

        while(l<=n && sum[l]-sum[i-]<L) l++;//sum(i,l)必须>=L;

        while(r+<=n && sum[r+]-sum[i-]<R) r++;//sum(i,r)必须<R

        if(sum[r]-sum[i-]<L) continue;

        ans+=(ll)(r-l+)*i + (ll)(l+r)*(r-l+)/;

    }

    return ans;

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        sum[]=;

        for(int i=;i<=n;i++){

            scanf("%d",&a[i]);

            sum[i]=sum[i-]+a[i];

        }

        ll ans=;

        for(int k=;k<=;k++)

            ans+=(ll)k*(solve(pow(,k-),pow(,k)));

        ans+=solve(,);

        printf("%lld\n",ans);

    }

}