题解 | 小红统计区间（easy）

叽里呱啦说什么呢？和我的线段树说去吧，这个放在hard一样能用喵，动态开点的线段树喵

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
#define int long long

struct Dysegtree
{
    struct Info
    {
        ll val;
        Info operator+(const Info&x)
        {
            return {val+x.val};
        }
        void operator+=(const Info&x){*this = *this + x;}
    };
    const Info ie = {0};//所谓单位元
    //根节点应该是单位元喵如果是求和就是0，求max就是-inf
    struct Node
    {
        int ls,rs;
        Info v;
    };
    int max_,min_,root;
    vector<Node> info;
    struct lazy {/* data */};
    Dysegtree(int l,int r):min_(l),max_(r),root(0){info.push_back({0,0,ie});}//数据范围喵
private:
    void pull(int p){info[p].v = info[info[p].ls].v + info[info[p].rs].v;}
    int set(int p,int pos,int l,int r,Info x)
    {
        if (!p)
        {
            p = info.size();
            info.push_back({0,0,ie});           
        }
        if (l == r) {info[p].v = x;return p;}
        int mid = l + (r - l) / 2;
        if (pos <= mid) 
        {
            int newls = set(info[p].ls,pos,l,mid,x);
            info[p].ls = newls;
        }
        else 
        {
            int newrs = set(info[p].rs,pos,mid + 1,r,x);
            info[p].rs = newrs;
        }
        pull(p);
        return p;
    }
    Info query(int p,int l,int r,int ql,int qr)
    {
        if (!p || ql > qr) return ie;
        int mid = l + (r - l) / 2;
        if (ql <= l && qr >= r) return info[p].v;
        if (qr <= mid) return query(info[p].ls,l,mid,ql,qr);
        else if (ql > mid) return query(info[p].rs,mid + 1,r,ql,qr);
        else return query(info[p].ls,l,mid,ql,qr) + query(info[p].rs,mid + 1,r,ql,qr);
    }
public:
    void set(int pos,Info val) {root = set(root,pos,min_,max_,val);}
    Info query(int l,int r){return query(root,min_,max_,l,r);}
};

void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int> a(n + 1),pre(n + 1);
    Dysegtree sgt(-1e14 - 11,1e14 + 10);
    for (int i = 1 ; i <= n ; i++) cin>>a[i];
    int ans = 0;
    sgt.set(0,{1});
    for (int i = 1 ; i <= n ; i++)
    {
        pre[i] = pre[i - 1] + a[i];
        ans += sgt.query(-1e14 - 10,pre[i] - k).val;
        //cout<<(sgt.query(-1e14 - 10,pre[i] - k).val)<<'\n';
        sgt.set(pre[i],{sgt.query(pre[i],pre[i]).val + 1});
    }
    cout<<ans<<'\n';
    return;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int _ = 1;
    //std::cin>>_;
    while (_--)
    {
        solve();
    }
    return 0;
}