fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
  3. #define fi first
  4. #define se second
  5. #define el "\n"
  6. #define pb push_back
  7. #define sz(a) (int)a.size()
  8. #define FILL(a, x) memset(a, x, sizeof(a))
  9.  
  10. using namespace std;
  11. typedef unsigned long long ll;
  12. typedef pair<int, int> ii;
  13. const int N = (int)1e6+3;
  14.  
  15. struct U128{
  16. ll lo, hi;
  17. U128(ll _lo=0, ll _hi=0):lo(_lo),hi(_hi){}
  18. };
  19. inline void add64(U128 &a, ll v){ ll o=a.lo; a.lo+=v; if(a.lo<o) ++a.hi; }
  20. inline void sub64(U128 &a, ll v){ ll o=a.lo; a.lo-=v; if(o<v) --a.hi; }
  21. inline bool isZero(const U128 &a){ return a.lo==0 && a.hi==0; }
  22. static inline void div10(const U128 &a, U128 &q, unsigned &r){
  23. ll hi=a.hi, lo=a.lo;
  24. unsigned int w3=(unsigned int)(hi>>32), w2=(unsigned int)(hi&0xffffffffu);
  25. unsigned int w1=(unsigned int)(lo>>32), w0=(unsigned int)(lo&0xffffffffu);
  26. ll rem=0, cur;
  27. unsigned int q3,q2,q1,q0;
  28. cur = rem*4294967296ull + w3; q3 = (unsigned int)(cur/10ull); rem = cur%10ull;
  29. cur = rem*4294967296ull + w2; q2 = (unsigned int)(cur/10ull); rem = cur%10ull;
  30. cur = rem*4294967296ull + w1; q1 = (unsigned int)(cur/10ull); rem = cur%10ull;
  31. cur = rem*4294967296ull + w0; q0 = (unsigned int)(cur/10ull); rem = cur%10ull;
  32. q.hi = ( (ll)q3<<32 ) | q2;
  33. q.lo = ( (ll)q1<<32 ) | q0;
  34. r = (unsigned)rem;
  35. }
  36. static inline void printU128(U128 a){
  37. if(isZero(a)){ cout<<0<<el; return; }
  38. char buf[64]; int m=0; unsigned rem;
  39. while(!isZero(a)){ U128 q; div10(a,q,rem); buf[m++] = char('0'+rem); a=q; }
  40. for(int i=m-1;i>=0;--i) cout<<buf[i];
  41. cout<<el;
  42. }
  43.  
  44. struct Query{ int l,r,id,bl; };
  45. static bool cmpQ(const Query& A, const Query& B){
  46. if(A.bl!=B.bl) return A.bl<B.bl;
  47. if(A.bl&1) return A.r>B.r;
  48. return A.r<B.r;
  49. }
  50.  
  51. int main()
  52. {
  53. ios_base::sync_with_stdio(false);
  54. cin.tie(NULL);    cout.tie(NULL);
  55.  
  56. int n,q;
  57. cin>>n>>q;
  58. string s; cin>>s;
  59.  
  60. vector<int> pref(n+1,0);
  61. FOR(i,1,n) pref[i]=pref[i-1]+(s[i-1]=='1'?1:-1);
  62.  
  63. vector<Query> qs(q);
  64. int B = max(1,(int)sqrt(n+1));
  65. FOR(i,0,q-1){
  66.     int u,v; cin>>u>>v;
  67.     qs[i].l=u-1; qs[i].r=v; qs[i].id=i; qs[i].bl=qs[i].l/B;
  68. }
  69. sort(qs.begin(), qs.end(), cmpQ);
  70.  
  71. int BASE = n+5, M = 2*(n+5)+7;
  72. vector<int> cnt(M,0);
  73. vector<ll> s1(M,0), s2(M,0);
  74.  
  75. U128 ans(0,0);
  76. vector<U128> res(q);
  77.  
  78. int L=0, R=-1;
  79. for(int i=0;i<sz(qs);++i){
  80.     int l=qs[i].l, r=qs[i].r;
  81.     while(R<r){
  82.         ++R;
  83.         int t = pref[R] + BASE;
  84.         ll m = (ll)cnt[t];
  85.         ll idx = (ll)R;
  86.         ll delta = s2[t] + m*idx*idx - 2ull*idx*s1[t];
  87.         add64(ans, delta);
  88.         cnt[t]++; s1[t]+=idx; s2[t]+=idx*idx;
  89.     }
  90.     while(R>r){
  91.         int t = pref[R] + BASE;
  92.         ll m = (ll)cnt[t];
  93.         ll idx = (ll)R;
  94.         ll delta = s2[t] + m*idx*idx - 2ull*idx*s1[t];
  95.         sub64(ans, delta);
  96.         cnt[t]--; s1[t]-=idx; s2[t]-=idx*idx;
  97.         --R;
  98.     }
  99.     while(L<l){
  100.         int t = pref[L] + BASE;
  101.         ll m = (ll)cnt[t];
  102.         ll idx = (ll)L;
  103.         ll delta = s2[t] + m*idx*idx - 2ull*idx*s1[t];
  104.         sub64(ans, delta);
  105.         cnt[t]--; s1[t]-=idx; s2[t]-=idx*idx;
  106.         ++L;
  107.     }
  108.     while(L>l){
  109.         --L;
  110.         int t = pref[L] + BASE;
  111.         ll m = (ll)cnt[t];
  112.         ll idx = (ll)L;
  113.         ll delta = s2[t] + m*idx*idx - 2ull*idx*s1[t];
  114.         add64(ans, delta);
  115.         cnt[t]++; s1[t]+=idx; s2[t]+=idx*idx;
  116.     }
  117.     res[qs[i].id]=ans;
  118. }
  119.  
  120. FOR(i,0,q-1) printU128(res[i]);
  121. return 0;
  122.  
  123.  
  124. }
  125.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kBotP4
language:
C++14 (clang 8.0)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!