区 间 和 2 区间和2 区间和2


<mstyle mathcolor="red"> 正 解 部 分 </mstyle> \color{red}{正解部分} 正解部分

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

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

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

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

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

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

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

<mstyle mathcolor="red"> 实 现 部 分 </mstyle> \color{red}{实现部分} 实现部分

注意询问中的 L , R L,R L,R 由于区间的数量是 N 2 N^2 N2 级别的, 所以要开 l o n g <mtext>   </mtext> l o n g long\ long 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;
}