1 条题解

  • 1
    @ 2024-7-25 14:20:49
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int inf = 1e10+1;
    const int maxn = 3e5+10;
    #define mid (l+r>>1)
    int n,root,a[maxn],pre[maxn],l,r;
    int ls[maxn<<5],rs[maxn<<5],sum[maxn<<5],id;
    void update(int &rt,int l,int r,int val)
    {
    	if( !rt )	rt = ++id;
    	if( l==r ){ sum[rt]++; return; }
    	if( val<=mid )	update( ls[rt],l,mid,val);
    	else	update(rs[rt],mid+1,r,val);
    	sum[rt] = sum[ls[rt]]+sum[rs[rt]];
    }
    int ask(int &rt,int l,int r,int L,int R)
    {
    	if( !rt )	rt = ++id;
    	if( l>=L&&r<=R )	return sum[rt];
    	int ans = 0;
    	if( L<=mid )	ans += ask(ls[rt],l,mid,L,R);
    	if( R>mid  )	ans += ask(rs[rt],mid+1,r,L,R);
    	return ans;
    }
    signed main()
    {
    	cin >> n >> l >> r;
    	for(int i=1;i<=n;i++)	{ cin >> a[i]; pre[i] = pre[i-1]+a[i]; }
    	update(root,-inf,inf,0);
    	int ans = 0;
    	for(int i=1;i<=n;i++)
    	{
    		ans += ask( root,-inf,inf,pre[i]-r,pre[i]-l );
    		update(root,-inf,inf,pre[i] );
    	}
    	cout << ans;
    }
    
    • 1

    信息

    ID
    2278
    时间
    1000ms
    内存
    250MiB
    难度
    9
    标签
    递交数
    12
    已通过
    7
    上传者