回转寿司 题解

E1_de5truct0r · 2022-11-02 16:06:32 · 个人记录

思路

本题非常简单，其实就是求有多少个点对 (i,j) 满足 i<j \land L \leq p_j-p_i \leq R，其中 p 为前缀和数组。

这是一个经典的二维区间偏序问题，可以用线段树维护，但是需要动态开点比较麻烦；另外码量偏大。

我觉得 CDQ 更加优美。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1000005;
int a[MAXN],pre[MAXN];

int n,L,R,ans=0;

void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid),cdq(mid+1,r);

    int i=l,hd=l,tl=l-1;
    for(int j=mid+1;j<=r;j++){
        while(tl<mid && pre[j]-pre[tl+1]>=L) tl++;
        while(hd<=tl && pre[j]-pre[hd]>R) hd++;
        ans+=(tl-hd+1);
    }
    inplace_merge(pre+l,pre+mid+1,pre+r+1);
}

signed main(){
    cin>>n>>L>>R;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
    cdq(0,n);
    cout<<ans;
    return 0;
}