记录编号	588354	评测结果	AAAAAAAAAA
题目名称	新年快乐！	最终得分	100
用户昵称	liuyiche	是否通过	通过
代码语言	C++	运行时间	6.600 s
提交时间	2024-05-28 21:00:57	内存使用	5.41 MiB

    #include <bits/stdc++.h>
     
    using namespace std;
     
    typedef long long ll;
     
    ll n, m;
    vector<ll> a(100005);
    vector<ll> L(500);
    vector<ll> R(500);
    vector<ll> sum(500);
    vector<ll> blog(100005);
    vector<ll> t;
    
     
    inline void build()
    {
        ll block = sqrt(n);
        ll num = n/block;
        if(n%block) num++;
        for(ll i = 1; i <= num; ++i)
        {
            L[i] = (i-1)*block+1;
            R[i] = i*block;
        }
        R[num] = n;
        for(ll i = 1; i <= n; ++i)
            blog[i] = (i-1)/block+1;
        for(ll i = 1; i <= num; ++i)
            sort(t.begin()+L[i],t.begin()+R[i]+1);  
    }
    
    inline void add(ll l, ll r, ll v)
    {
        if(blog[l] == blog[r])
        {
            for(ll i = l; i <= r; ++i)
                a[i] += v;
            for(ll i = L[blog[l]]; i <= R[blog[l]]; ++i)
                t[i] = a[i];
            sort(t.begin()+L[blog[l]],t.begin()+R[blog[l]]+1); 
        }
        else
        {
            for(ll i = l; i <= R[blog[l]]; ++i)
                a[i] += v;
            for(ll i = L[blog[l]]; i <= R[blog[l]]; ++i)
                t[i] = a[i];
            sort(t.begin()+L[blog[l]],t.begin()+R[blog[l]]+1); 
            for(ll i = L[blog[r]]; i <= r; ++i)
                a[i] += v;
            for(ll i = L[blog[r]]; i <= R[blog[r]]; ++i)
                t[i] = a[i];
            sort(t.begin()+L[blog[r]],t.begin()+R[blog[r]]+1); 
            for(ll i = blog[l]+1; i < blog[r]; ++i)
                sum[i] += v;
        }        
    }
     
    inline ll query(ll l, ll r, ll k)
    {
        ll ans = 0;
        if(blog[l] == blog[r])
        {
            for(ll i = l; i <= r; ++i)
                if(a[i] + sum[blog[l]] <= k)
                    ans++;
        }
        else
        {
            for(ll i = l; i <= R[blog[l]]; ++i)
                if(a[i] + sum[blog[l]] <= k)
                    ans++;
            for(ll i = blog[l]+1; i < blog[r]; ++i)
                ans += upper_bound(t.begin()+L[i],t.begin()+R[i]+1,k-sum[i])-t.begin()-L[i];
            for(ll i = L[blog[r]]; i <= r; ++i)
                if(a[i] + sum[blog[r]] <= k)
                    ans++;
        }
        return ans;
    }
     
    int main()
    {
        freopen("dss.in","r",stdin);
        freopen("dss.out","w",stdout);
     
        ios::sync_with_stdio(false);
        cin.tie(0);  cout.tie(0);
     
        cin >> n;
        for(ll i = 1; i <= n; ++i)
            cin >> a[i];
        t = a;
        build();
        cin >> m;
        for(ll i = 1; i <= m; ++i)
        {
            int x, l, r;
            ll k;
            cin >> x >> l >> r >> k;
            if(x == 1)
                add(l,r,k);
            else
                cout << query(l,r,k) << '\n';
        }
     
        return 0;
    }