$区间和2$区间和2

$正解部分$正解部分

题目要求的是 ${\sum }_{i=L}^R{B}_i$i=L∑R​Bi​, 转化为求 ${\sum }_{i=1}^R{B}_i-{\sum }_{i=1}^{L-1}{B}_i$i=1∑R​Bi​−i=1∑L−1​Bi​,
即 求前 $K$K 小所有区间的前缀和 .

怎么求前 $K$K 小区间的和呢 ? 首先找出所有区间再去找第前 $K$K个区间 是不可行的, 考虑二分答案,

先二分出 $mid$mid, 转化为 判断是否有 $K$K个区间比 $mid$mid小,
考虑怎么枚举区间, 有哪些算法可以快速地求出 符合某些条件的区间的个数 $?$?

尺取可以快速地求出符合条件的区间个数, 使用 尺取 统计 $A$A 数列中有多少子段是 $\le mid$≤mid 的, 设为 $num$num,

• 若 $num\&lt;K$num<K, 说明 $mid$mid 小了 .
• 若 $num=K$num=K, 理想情况, 表示正好找到了 .
• 若 $num\&gt;K$num>K, 此时注意, 可能去掉一些权值等于 $mid$mid 的区间就可以使得 $num=mid$num=mid 了, 否则说明 $mid$mid 大了 .

这里说明一下为什么可以尺取, 因为对每个左端点, 右端点往右移产生的新区间的和满足单调递增, 又因为有界限存在, 所以可以不重不漏地照顾到所有满足条件的区间.

但若出现负数, 就不可以这么做了, 这道题 就是一个例子 .

$实现部分$实现部分

注意询问中的 $L,R$L,R 由于区间的数量是 $N^2$N2 级别的, 所以要开 $longlong$long long .

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 200005;

int N;
int Q;
int A[maxn];
int sum[maxn];

int chk(int mid, ll K, ll &tmp){
        int t = 1, cnt_e = 0;
        ll res = 0, cur_sum = 0, cnt = 0;
        for(reg int i = 1; i <= N; i ++){
                while(t <= N && sum[t]-sum[i-1] <= mid) cur_sum += sum[t ++];
                cnt += t - i;
                if(sum[t-1]-sum[i-1] == mid) cnt_e ++;
                res += cur_sum - (1ll*t-i)*sum[i-1];
                cur_sum -= sum[i];
        }
        tmp = res;
        if(cnt < K) return 1;		// mid 太小 
        else if(cnt-cnt_e < K){ tmp -= (cnt-K)*mid; return 1; }
        return 0;
}

ll Calc(ll x){
        int l = 1, r = sum[N];
        ll res = 0;
        while(l <= r){
                int mid = l+r >> 1;
                ll tmp = 0;
                if(chk(mid, x, tmp)) res = tmp, l = mid + 1;
                else r = mid - 1;
        }
        return res;
}

void Work(){ 
        scanf("%d%d", &N, &Q);
		for(reg int i = 1; i <= N; i ++) scanf("%d", &A[i]);
		for(reg int i = 1; i <= N; i ++) sum[i] = sum[i-1] + A[i];
        while(Q --){
                ll L, R;
                scanf("%lld%lld", &L, &R);
                printf("%lld\n", Calc(R) - Calc(L-1));
        }
}

int main(){
		int T;
    	scanf("%d", &T);
    	while(T --) Work();
		return 0;
}