F.小红统计区间——离散化+树状数组

小红拿到了一个数组，她想知道，有多少非空区间满足区间所有元素之和不小于 k？ (存在负数，前缀和没有单调性，无法用双指针)

输入
第一行输入两个正整数 n,k (1 ≤ n ≤ 1e5,1 ≤ k ≤ 1e14) 用空格隔开。
第二行输入n个整数 ai(?1e9 ≤ ai ≤ 1e9) ，代表数组的元素。

输出
输出一个整数表示满足条件区间的数量。

样例输入1
5 5
1 4 2 1 3
样例输出1
8

样例输入2
4 5
2 -100 5 6
样例输出2
3

解析：
要求解 区间[l,r]满足s[r]-s[l]≥k 的区间数量，也就是求 s[r]-k ≥ s[l] 的数量
所以用到 树状数组，每次将前缀和 s[i-1] 加入树状数组中，再查询小于等于 s[i]-k 的个数，再累加即可。
当然前缀和有可能很大，形成的数轴过长，我们也只需要知道它们的相对位置，所以可以采用离散化，从小到大排序，并去重。

代码一：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int n,k;
int a[N],s[N],t[N];
int tr[N];
int cnt;
int get(int x)
{
    return lower_bound(t+1,t+cnt+1,x)-t;        //找到第一个大于等于x的位置
}
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int c)
{
    for (int i=x;i<=cnt;i +=lowbit(i)) tr[i] +=c;
}
int query(int x)
{
    int ans=0;
    for (int i=x;i>0;i -=lowbit(i)) ans +=tr[i];
    return ans;
}
int lowerbound(int x)
{
    int idx=upper_bound(t+1,t+cnt+1,x)-t-1;     //找到最后一个小于等于 s[i]-k 的位置
    return query(idx);
}
void solve()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++) 
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
        t[++cnt]=s[i];
    }
    t[++cnt]=0;

    sort (t+1,t+cnt+1);                         //将所有前缀和按大小重新排序，并去重
    cnt=unique(t+1,t+cnt+1)-(t+1);
    int ans=0;
    for (int i=1;i<=n;i++) 
    {
        add(get(s[i-1]),1);                     //将上一次循环的左端点加入树状数组中，在相应的位置 +1
        ans +=lowerbound(s[i]-k);               //找到最后一个小于等于 s[i]-k 的位置，query(idx)就是小于等于 s[i]-k 的数量
    }
    cout<<ans;
}
signed main()
{
    ios;
    int T=1;
    //cin>>T;
    while (T--) solve();
    return 0;
}

?代码二(用map 排序+去重)：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int n,k;
int a[N],s[N],tr[N];
map <int,int> mp;
int cnt;
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int c)
{
    for (int i=x;i<=cnt;i +=lowbit(i)) tr[i] +=c;
}
int query(int x)
{
    int ans=0;
    for (int i=x;i>0;i -=lowbit(i)) ans +=tr[i];
    return ans;
}
void solve()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
        mp[s[i]]=1;
        mp[s[i]-k]=1;
    }

    mp[0]=1;
    for (auto &[x,y]:mp) y=++cnt;
    
    int ans=0;
    for (int i=1;i<=n;i++)
    {
        add(mp[s[i-1]],1);
        ans +=query(mp[s[i]-k]);
    }
    cout<<ans;
}
signed main()
{
    ios;
    int T=1;
    //cin>>T;
    while (T--) solve();
    return 0;
}