fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. using namespace __gnu_pbds;
  7.  
  8. template<class T> using oset = 
  9.             tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  10.  
  11. #define int long long
  12. #define ld long double
  13. #define ar array
  14. #define vi vector<int>
  15. #define vii vector<vector<int>>
  16. #define pii pair<int, int>
  17. #define pb push_back
  18. #define all(x) x.begin(), x.end()
  19. #define f first
  20. #define s second
  21. #define endl "\n"
  22.  
  23. const int MOD = 1e9+7;
  24. const int inf = 1e9;
  25. const int linf = 1e18;
  26.  
  27. const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
  28. const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
  29.  
  30.  
  31. // -------------------------------------------------- Main Code --------------------------------------------------
  32.  
  33. const int N = 2e5+5;
  34. int bsize = sqrt(N)+1;
  35.  
  36. int arr[N], pref[N];
  37.  
  38. void sol() {
  39.     int n, q; cin >> n >> q;
  40.     for (int i = 1; i <= n; i++) cin >> arr[i];
  41.     for (int i = 1; i <= n; i++) pref[i] += arr[i]+pref[i-1];
  42.  
  43.     auto sum = [&](int x) {return x*(x+1)/2;};
  44.     auto get = [&](int x, int y, int l, int r) {
  45.         // calculating effect of l-r in x-y segment
  46.         if (x > r || y < l) return 0ll;
  47.         r = min(r, y);
  48.         int res = sum(r-l+1) - (l<x)*sum(x-l);
  49.         return res;
  50.     };
  51.  
  52.     vector<pii> pending;
  53.     for (int i = 0; i < q; i++) {
  54.         int t, a, b; cin >> t >> a >> b;
  55.         if (t == 1) pending.pb({a, b});
  56.         else {
  57.             int ans = pref[b]-pref[a-1];
  58.             for (auto i : pending) {
  59.                 int l = i.f, r = i.s;
  60.                 ans += get(a, b, l, r);
  61.             }
  62.             cout << ans << endl;
  63.         }
  64.  
  65.         if (pending.size() == bsize) {
  66.             vi positive(n+2), negative(n+2);
  67.             for (auto i : pending) {
  68.                 positive[i.f]++;
  69.                 positive[i.s+1]--;
  70.                 negative[i.s+1] += -(i.s-i.f+1);
  71.             }
  72.             int sum = 0, ct = 0;
  73.             for (int i = 1; i <= n; i++) {
  74.                 ct += positive[i];
  75.                 sum += ct+negative[i];
  76.                 positive[i] = sum;
  77.                 arr[i] += positive[i];
  78.                 pref[i] = arr[i]+pref[i-1];
  79.             }
  80.             pending.clear();
  81.         }
  82.     }
  83. }
  84.  
  85. signed main () {
  86.     ios_base::sync_with_stdio(false);
  87.     cin.tie(NULL);
  88.     int t = 1;
  89.     // cin >> t; 
  90.     while (t--) {
  91.         sol();
  92.     }
  93.     return 0;
  94. }
Success #stdin #stdout 0.01s 5532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/00r35V
language:
C++14 (gcc 8.3)
created:
1 year 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!