公式

E - Subsegment Sum Finder 解説 by en_translator 印刷ページ


In case of C++, tree, the g++ extension (article in Japanese) facilitates the implementation.

Sample code (C++):

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>

using namespace __gnu_pbds;
using namespace std;
using ll=long long;
using pl=pair<ll,ll>;

ll f(ll x, vector<ll> &a){
  tree<pl,null_type,less<pl>,rb_tree_tag,tree_order_statistics_node_update> tr;
  tr.insert({0,-1});
  ll h=0;
  ll res=0;
  for(ll i=0;i<a.size();i++){
    h+=a[i];
    res+=tr.order_of_key(pl{h-x,8e18});
    tr.insert({h,i});
  }
  return res;
}

int main(){
  ll n,l,r;
  cin >> n >> l >> r;
  vector<ll> a(n);
  for(auto &nx : a){cin >> nx;}
  cout << f(l,a)-f(r+1,a) << "\n";
  return 0;
}

投稿日時:
最終更新: