题解：CF2173F Isla's Memory Thresholds

· · 题解

显然，对于每个询问，我们可以想到一种比较暴力的方法：不断地二分或倍增地查找下一个清空记忆的节点。

由于 a_i 不增，假设最小的令 \sum_{i=1}^j a_i\ge x 的 x 为 B，那么，显然，后续每次清空记忆都至少会清空长度为 B 的区间，如此的单次时间复杂度为 O(\frac{n}{B} \log n)。

当或每次清空的区间长度都极短时，使用二分回答单次询问的时间复杂度为 O(n \log n)，使用倍增则为 O(n)，显然这都无法接受。

设每次清空的区间长度为 len，我们想到可以在 len 较小时将其使用某种方法跳过以增大 len。

假设当前枚举到 len=i，且 len\le i 的情况都已经被妥善处理。

那么：假设最右端的长度为 i 的区间右端点为 r_i，则对于所有 i \le r_i，必有 sum_i-sum_{i-len}\ge x ，且对于所有区间 sum_r-sum_{l-1}<x 的区间 [l,r]，其区间长度必然大于 i。

因此，对于每个 len_i，我们找到最大的令 sum_r-sum_{r-len}\ge x 的 r_i。

显然，r_{i-1} 必然在之前被处理好了，而 (r_{i-1},r_i] 之间必然不可能有的长度小于 len_i 的区间，由于 a_i 不增，因此也必然不可能有完整的长度大于 len_i 的区间。

因此，通过此法，我们可以倍增地找到所有的 r_i，单次时间复杂度小于 O(\log n)，由于是倍增，所有的查找时间复杂度不会高于 O(sum_{len})，其中 sum_{len} 为所有以此法查找的区间的总长度。

因此，对于长度不大于 \sqrt{n} 的区间，倍增地跳过，对于长度大于 \sqrt{n} 的区间，不断找到下一个区间即可。

代码如下

#include<bits/stdc++.h>
using namespace std;

#define int long long

int const N = 150007;

int n,q;
int a[N];
long long sum[N];

void solve(){
    cin >> n >> q;
    for(int i=1 ;i<=n ;i++) 
        cin >> a[i];
    for(int i=1 ;i<=n ;i++)
        sum[i] = sum[i-1]+a[i];

    while(q--){
        int l,r,x;
        cin >> l >> r >> x;
        int sqrtn = sqrt(n);
        int cnt = 0;
        int now = l-1;
        //找到l~now中每一段都＞=x 且 len<=sqrtn 的最大值now
        for(int len=1 ;len<=sqrtn ;len++){ //从len==1开始，跳过len==len_i的片段

            if(now+len>r) break;
            int nextn = now+len;
            if(sum[nextn]-sum[now]<x) continue; //len至少更大

            //倍增跳过所有长度为len的区间
            int step = 1;
            for(;nextn+step<=r ;step*=2){
                if(sum[nextn+step]-sum[nextn+step-len]<x) 
                    break;
                nextn += step;
            }
            for(;step ;step>>=1){
                if(nextn+step<=r and sum[nextn+step]-sum[nextn+step-len]>=x)
                    nextn += step;
            }
            //累积答案
            cnt += (nextn-now)/len;
            now += (nextn-now)/len*len; 
        }
        //暴力处理
        while(now!=r){
            if(sum[r]-sum[now]<x){
                break;
            }
            int L=now,R=r;
            while(L<R){
                int mid = (L+R)>>1;
                if(sum[mid]-sum[now]>=x)
                    R = mid;
                else 
                    L = mid+1;
            }
            now = R;
            ++cnt;
        }

        cout << cnt << " " << sum[r]-sum[now] << "\n";
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while(T--) solve();
}