fork(6) download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define M 1000000007
  4. typedef long long ll;
  5. #define pb push_back
  6. #define F first
  7. #define S second
  8. #define M6 3000009
  9. #define M5 3000009
  10. #define pi 3.14159265
  11. typedef pair<ll,ll> pll;
  12. ll power(ll x,ll n){
  13. ll ret=1;
  14. while(n>0){
  15. if(n&1) ret=(ret*x);
  16. x=(x*x);
  17. n/=2;
  18. }
  19. return ret;
  20. }
  21. ll m,n,ar[M5],cr[M5],tree[M6],ql[M5],qr[M6];
  22. void update(ll st,ll en,ll nd,ll i,ll v){
  23. if(st==en) {tree[nd]+=v; return;}
  24. ll mid=(st+en)/2;
  25. if(i>=st&&i<=mid){
  26. update(st,mid,2*nd,i,v);
  27. }
  28. else update(mid+1,en,2*nd+1,i,v);
  29. tree[nd]=tree[2*nd]+tree[2*nd+1];
  30. }
  31. ll query(ll st,ll en,ll nd,ll qs,ll qe){
  32. if(st>qe||en<qs) return 0;
  33. if(st>=qs&&en<=qe) return tree[nd];
  34. ll mid=(st+en)/2;
  35. ll p=query(st,mid,2*nd,qs,qe);
  36. ll q=query(mid+1,en,2*nd+1,qs,qe);
  37. return p+q;
  38. }
  39. int main()
  40. { ios_base::sync_with_stdio (0), cin.tie (0);
  41. ll test=1,t=1,flag,i,j,k,l,a,b,ans=0,p,q;
  42. cin>>n>>test;
  43. vector<ll> v;
  44. for(i=1;i<=n;i++) cin>>ar[i],ar[i]+=ar[i-1],v.pb(ar[i]);
  45. v.pb(0);
  46. for(i=1;i<=test;i++){
  47. cin>>ql[i]>>qr[i];
  48. for(j=1;j<=n;j++) v.pb(ar[j]-ql[i]),v.pb(ar[j]-qr[i]);
  49. }
  50. sort(v.begin(),v.end());
  51. for(i=1;i<=test;i++){
  52. q=(ll)v.size();
  53. j=lower_bound(v.begin(),v.end(),0)-v.begin();
  54. update(0,q,1,j,1);
  55. ans=0;
  56. for(j=1;j<=n;j++){
  57. a=ar[j]-qr[i]; b=ar[j]-ql[i];
  58. a=lower_bound(v.begin(),v.end(),a)-v.begin();
  59. b=lower_bound(v.begin(),v.end(),b)-v.begin();
  60. ans+=query(0,q,1,a,b);
  61. k=lower_bound(v.begin(),v.end(),ar[j])-v.begin();
  62. update(0,q,1,k,1);
  63. }
  64. j=lower_bound(v.begin(),v.end(),0)-v.begin();
  65. update(0,q,1,j,-1);
  66. for(j=1;j<=n;j++){
  67. k=lower_bound(v.begin(),v.end(),ar[j])-v.begin();
  68. update(0,q,1,k,-1);
  69. }
  70. cout<<ans<<"\n";
  71. }
  72. return 0;
  73. }
Success #stdin #stdout 0s 4352KB
stdin
Standard input is empty
stdout
0