fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define int __int128
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "gen"
  33. /*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */
  34.  
  35. const int MOD = 1e9 + 7;
  36. const int inf = 1e9 + 27092008;
  37. const ll INF = 1e18 + 27092008;
  38. const int N = 2e5 + 5;
  39. const int S = 600;
  40. long long n, q, pref[N];
  41. string s;
  42. int cnt[2 * N];
  43. int sum[2 * N], sumsq[2 * N];
  44.  
  45. struct Query {
  46.     ll l, r, id;
  47.     bool operator < (const Query &other) const {
  48.         if (l / S != other.l / S) return l < other.l;
  49.         return ((l / S) & 1 ? r > other.r : r < other.r);
  50.     }
  51. } Q[N];
  52.  
  53. int calcL(int L) {
  54.     L--;
  55.     int ans = 0;
  56.     ans += L * L * cnt[pref[L]];
  57.     ans -= 2 * L * sum[pref[L]];
  58.     ans += sumsq[pref[L]];
  59.     return ans;
  60. }
  61.  
  62. int calcR(int R) {
  63.     ll ans = 0;
  64.     ans += R * R * cnt[pref[R]];
  65.     ans -= 2 * R * sum[pref[R]];
  66.     ans += sumsq[pref[R]];
  67.     return ans;
  68. }
  69.  
  70. int ans = 0;
  71. int L, R;
  72. void addL(int L, int sign) {
  73.     if (sign == -1) ans -= calcL(L);
  74.     cnt[pref[L-1]] += sign;
  75.     sum[pref[L-1]] += (L-1) * sign;
  76.     sumsq[pref[L-1]] += 1LL * (L-1) * (L-1) * sign;
  77.     if (sign == +1) ans += calcL(L);
  78.  
  79.     if (pref[L-1] == pref[R]) {
  80.         ans += sign * (R - L + 1) * (R - L + 1);
  81.     }
  82. }
  83.  
  84. void addR(int R, int sign) {
  85.     if (pref[L-1] == pref[R]) {
  86.         ans -= sign * (R - L + 1) * (R - L + 1);
  87.     }
  88.     if (sign == -1) ans -= calcR(R);
  89.     cnt[pref[R-1]] += sign;
  90.     sum[pref[R-1]] += (R-1) * sign;
  91.     sumsq[pref[R-1]] += 1LL * (R-1) * (R-1) * sign;
  92.     if (sign == +1) ans += calcR(R);
  93.     if (pref[L-1] == pref[R]) {
  94.         ans += sign * (R - L + 1) * (R - L + 1);
  95.     }
  96. }
  97.  
  98. int res[N];
  99. void MO(int i) {
  100.     int l = Q[i].l, r = Q[i].r;
  101.     while(L > l) addL(--L, +1);
  102.     while(R < r) addR(++R, +1);
  103.     while(L < l) addL(L++, -1);
  104.     while(R > r) addR(R--, -1);
  105. }
  106.  
  107. void print(__int128 x) {
  108.     vector<int> res;
  109.     if (!x) res.pb(0);
  110.     while(x) {
  111.         res.pb((int)(x % 10));
  112.         x /= 10;
  113.     }
  114.     reverse(all(res));
  115.     for(ll t : res) cout << t; 
  116.     cout << '\n';
  117. }
  118.  
  119. void init(void) {
  120.     cin >> n >> q >> s;
  121.     pref[0] = n;
  122.     FOR(i, 1, n) pref[i] = pref[i - 1] + (s[i - 1] == '0' ? -1 : +1);
  123.     FOR(i, 1, q) cin >> Q[i].l >> Q[i].r, Q[i].id = i;
  124. }
  125.  
  126. void process(void) {
  127.     sort(Q + 1, Q + q + 1);
  128.     L = Q[1].l, R = Q[1].r;
  129.     FOR(i, L, R) addR(i, +1);
  130.     res[Q[1].id] = ans;
  131.     FOR(i, 2, q) {
  132.         MO(i);
  133.         res[Q[i].id] = ans;
  134.     }
  135.  
  136.     FOR(i, 1, q) print(res[i]);
  137. }
  138.  
  139. signed main() {
  140.     ios_base::sync_with_stdio(0);
  141.     cin.tie(0); cout.tie(0);
  142.     if (fopen(task".inp", "r")) {
  143.         freopen(task".inp", "r", stdin);
  144.         freopen(task".out", "w", stdout);
  145.     }
  146.     int tc = 1;
  147. //    cin >> tc;
  148.     while(tc--) {
  149.         init();
  150.         process();
  151.     }
  152.     return 0;
  153. }
  154.  
Success #stdin #stdout 0.01s 5704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MrAWzG
language:
C++14 (gcc 8.3)
created:
3 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!