Cho dãy số nguyên gồm n phần tử a1,a2,,an (|ai|109). Cho giá trị x và q câu hỏi có dạng S(u,v). Với S(u,v) là tổng các giá trị của các phần tử từ u đến v. Yêu cầu: Đếm xem trong q câu hỏi đó có bao câu hỏi có giá trị nhỏ hơn x. Input Dòng đầu tiên chứa ba số nguyên dương n,x,q(x109,q105). Dòng thứ hai chứa a1,a2,,an(|ai|109). q dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u,v(1uvn). Output In ra một số nguyên là số lượng câu hỏi có giá trị nhỏ hơn x Input 5 6 3 7 2 1 6 5 2 3 3 4 5 5 Output 2

Thuật toán: Ta sử dụng mảng cộng dồn để tính.

$\texttt{C++}$

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long n,a[100005],x,q,d[100005],dem=0;
    cin>>n>>x>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    d[0]=0;
    for(int i=1;i<=n;i++)
    {
        d[i]=d[i-1]+a[i];
    }
    while(q--)
    {
        int u,v;
        cin>>u>>v;
        if(d[v]-d[u-1]<x) dem++;
    }
    cout<<dem;
}

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[10000007];
int main()
{
    ll n,x,q,ans=0;
    cin>>n>>x>>q;
    for (ll i=1;i<=n;++i) 
    cin>>a[i];
    a[0]=0;
    for(ll i=1;i<=n;++i) 
    a[i]+=a[i-1];
    while (q--)
    {
        ll l,r,t=0;
        cin>>l>>r;
        if (a[r]-a[l-1]<x) 
        ans++;
    }
    cout<<ans;
    return 0;
}