题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
-
这个题的话是得找到有多少对(l, r) 满足 R >= sum[l~r] >= L
一般遇到这样的题我们都要分解sum[l~r],然后再继续推式子
所以就 R >= sum[l-r] >= L ->> R >= sum[r] - sum[l-1] >= L
sum[r] - L >= sum[l-1] >= sum[r] - R; -
所以对于一个给定的右端点， 那么我们只需要查询在这之前有多少个前缀和在
[sum[r]-R,sum[l]-L] 之内， 然后累加就行了 -
而 sum[r] - R比较大 我们动态开点就行了。
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
struct node
{
int ls,rs;
int sum ;
node()
{
ls = rs = sum = 0;
}
}tr[N*130];
int idx = 1;
void pushup(int u)
{
tr[u].sum = tr[tr[u].ls].sum + tr[tr[u].rs].sum;
}
void modify(int &u, LL pos, LL L, LL R,int v)
{
if(L > pos || pos > R) return;
if(!u) u = ++idx ;
if(L == R)
{
tr[u].sum += 1;
return ;
}
LL mid = (L + R)>>1;
modify(tr[u].ls , pos, L , mid, v);
modify(tr[u].rs, pos , mid + 1, R, v);
pushup(u);
}
int query(int &u, LL l ,LL r, LL L, LL R)
{
if(L > r || R < l || !u) return 0;
if(L >= l && R <= r) return tr[u].sum;
LL mid = (L + R) >> 1;
LL sum = 0;
sum +=query(tr[u].ls , l, r, L, mid);
sum +=query(tr[u].rs, l, r, mid + 1, R);
return sum;
}
LL sum[N];
int main()
{
int n, L, R, root = 1;
LL l = -1e10, r = 1e10;
cin>>n>>L>>R;
LL res = 0;
modify(root, 0, l, r, 1);
for(int i = 1; i <= n; i++)
{
int x;
cin>>x;
sum[i] = sum[i-1] + x;
res += query(root, sum[i]-R, sum[i]-L, l, r);
modify(root, sum[i], l, r, 1);
}
cout<<res;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
