Dãy số

Điểm: 0,30 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

Sưu tầm

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy ~A~ gồm ~N~ số nguyên và ~2~ số ~L,R~.

Đếm số cặp chỉ số ~(i,j), i \leq j~ sao cho $$L \leq \sum_{k=i}^{j} A_k \leq R$$

Input

Dòng đầu gồm ~3~ số nguyên dương ~N \leq 10^5,-10^9 \leq L,R \leq 10^9~.

Dòng thứ hai là dãy ~A~ gồm ~N~ số nguyên, ~|A_i| \leq 10^9~.

Output

Một số nguyên duy nhất là số cặp chỉ số thoả mãn.

Sample Input

4 2 4
1 2 3 4

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

vuonghoaitamdz9 đã bình luận lúc 12, Tháng 11, 2025, 11:07

Một cách là khác khá là thú vị

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define str string
#define fi first
#define se second
#define pb push_back
#define sp ' '
#define all(v) (v).begin(), (v).end()
#define pii pair<int,int>
#define el '\n'
using namespace std;
const int N=1e6;
const int mod=1e9+7;
ll res,d[N+2],n,x,y,z;
vector<ll>v;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    cin>>n>>x>>y;
    for (int i=1;i<=n;i++){
        cin>>z;
        d[i]=d[i-1]+z;
    }
    v.push_back(0);
    for (int i=1;i<=n;i++){
        int l=lower_bound(all(v),d[i]-y)-v.begin();
        int r=upper_bound(all(v),d[i]-x)-v.begin();
        res+=r-l;
        v.insert(lower_bound(all(v),d[i]),d[i]);
    }
    cout<&lt;res;
    return 0;
}

ngoccaidu2008 đã bình luận lúc 3, Tháng 11, 2025, 16:08 ← chỉnh sửa →

Ý tưởng bài này dùng segment tree kết hợp mảng cộng dồn, nén số và binary_search. Như vậy ta nhận xét kết quả bài toán là kết quả của đoạn cnt(r)-cnt(l-1).

Bài này có thể giải theo 2 cách. Cách thứ 2 mình nghĩ dùng chia để trị để làm. Nó mới là ý tưởng thôi. Còn viết như nào thì tự mà viết

code tham khảo:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define __Hormer_Nguyen__ signed main()
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
const int MOD=1000000007;
const int maxn=5+1e5;
int n,l,r;
int s[maxn],st[4*maxn];
vector<int>vt;
int binary(int val)
{
    auto k=lower_bound(vt.begin(),vt.end(),val)-vt.begin();
    return k+1;
}
void seg(int v,int l,int r)
{
    if (l==r)
    {
        st[v]=0;
        return;
    }m=(l+r)/2;
    seg(2*v,l,m);
    seg(2*v+1,m+1,r);
    st[v]=st[2*v]+st[2*v+1];
}
void update(int v,int l,int r,int pos,int val)
{
    if (l>pos || r<pos) return;
    if (l==pos && r==pos)
    {
        st[v]+=val;
        return;
    }int m=(l+r)/2;
    update(2*v,l,m,pos,val);
    update(2*v+1,m+1,r,pos,val);
    st[v]=st[2*v]+st[2*v+1];
}
int get(int v,int l,int r,int a,int b)
{
    if (b<l || a>r) return 0;
    if (l>=a && r<=b) return st[v];
    int m=(l+r)/2;
    return get(2*v,l,m,a,b)+get(2*v+1,m+1,r,a,b);
}
int ans(int k)
{
    int cnt=0;
    m=vt.size();
    seg(1,1,m);
    update(1,1,m,binary(s[0]),1);
    for (int j=1;j<=n;j++)
    {
        int h=s[j]-k;
        int idx=binary(h);
        cnt+=get(1,1,m,idx,m);
        idx=binary(s[j]);
        update(1,1,m,idx,1);
    }return cnt;
}
__Hormer_Nguyen__
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>l>>r;
    s[0]=0;
    vt.push_back(s[0]);
    for (int i=1;i<=n;i++)
    {
        int x;cin>>x;
        s[i]=s[i-1]+x;
        vt.push_back(s[i]);
    }sort(vt.begin(),vt.end());
    vt.erase(unique(vt.begin(),vt.end()),vt.end());
    cout<<ans(r)-ans(l-1);
}

0

ChiPhatNguyen đã bình luận lúc 4, Tháng 11, 2025, 14:50

cảm ơn bạn

-2

huydang_17 đã bình luận lúc 17, Tháng 10, 2025, 9:42

non

-1

kthcpp đã bình luận lúc 27, Tháng 9, 2025, 13:34

hii

-5

Tuan_Anh đã bình luận lúc 23, Tháng 2, 2025, 16:17

damn

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

0

tuanmanh123 đã bình luận lúc 15, Tháng 8, 2025, 6:04

hi bro

-5

nghiaasd258 đã bình luận lúc 13, Tháng 1, 2025, 3:40 ← sửa 3 →

.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-19

khanhlani đã bình luận lúc 19, Tháng 8, 2024, 3:26

:(

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.