D. Petya and Array
题目大意:给定长度为 n n n的序列 a a a,求出有多少组 l , r l,r l,r使得 a l + a l + 1 + a l + 2 + . . . . + a r < t a_l+a_{l+1}+a_{l+2}+....+a_r<t al?+al+1?+al+2?+....+ar?<t.
解题思路:这题的关键点在于能否考虑到序列和用前缀和来表示,对于一对 l , r l,r l,r只要满足 p r e r ? p r e l < t pre_r-pre_l<t prer??prel?<t则符合,这个题可以转化为动态的插入维护来解决,我们每次枚举 p r e r pre_r prer?,然后将其插入到树状数组中,我们二分找到符合条件的值,并且查询在已有的树状数组中有多少个这样的值,就满足了 r ≥ l r\ge l r≥l的要求.对于这种类型的题目,都可以考虑用树状数组来单调的进行动态维护.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, m;
const int N = 2e5+5;
int tree[N];
inline int lowbit(int x){
return x & (-x);
}inline void update(int i, int x){
for (int pos = i; pos <= n; pos+=lowbit(pos))tree[pos]+=x;
}inline int query(int x){
int ans = 0;for (int pos = x; pos; pos-=lowbit(pos))ans += tree[pos];return ans;
}inline int query(int l, int r){
return query(r) - query(l-1);
}
ll a[N], pre[N], b[N];
int main(){
syncfalse#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifll t;cin>>n>>t;for (int i = 1; i <= n; ++i){
cin>>a[i];pre[i]=a[i]+pre[i-1];b[i]=pre[i];}ll ans = 0;sort(b+1, b+1+n);for (int i = 1; i <= n; ++i){
ll id = upper_bound(b+1, b+1+n, pre[i]-t)-b;if(id!=n+1)ans+=query(id, n); //当前可以选择的不为空前缀数if (pre[i]<t)ans++; //如果当前可以选空前缀ll pos = lower_bound(b+1, b+1+n, pre[i])-b;update(pos, 1);
// cout << ans << "\n";
// for (int i = 1; i <= n; ++i){
// cout << query(i, i) << " ";
// }
// cout << "\n";}cout << ans << "\n";return 0;
}