Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #216 - C11SEQ
Ngày: 01-07-2011
Cập nhật: 19-07-2011
Người gửi: hunterphu
Ngôn ngữ: C++
Xem: 1101

Điểm: 4.6/5 (32 Phiếu)


/*
Gọi s[i]=a[1]+...+a[i]
Duyệt từ n->1, xét i là vị trí bắt đầu của dãy con.
Số lượng vị trí j>=i sau cho L<=a[i]+a[i+1]...+a[j]<=R chính là số phần tử >=L+s[i-1] và <=R+s[i-1].
Dùng BIT để đếm, đoạn code này chỉ là tư tưởng :D
*/
#include<iostream>
#define nm 100010
using namespace std;
long long s[nm],t[nm];
long long res,L,R;
int n;
void update(int i)
{
     while (i<nm)
           t[i]++,i+=i&-i;
}
long long visit(int i)
{
     int r=0;
     while (i)
           r+=t[i],i-=i&-i;
     return r;
}
int main()
{
    cin>>n>>L>>R;
    for (int i=1;i<=n;i++)
        cin>>s[i],s[i]+=s[i-1];
    for (int i=n;i>=1;i--)
    {
        update(s[i]);
        res+=visit(s[i-1]+R)-visit(s[i-1]+L-1);
    }
    cout<<res;
    return 0;
}