#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pii pair<int, int> #define all(a) a.begin(), a.end() using namespace std; #ifdef LOCAL #include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h" #else #define debug(...) 42 #endif const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9; int n, q, k = 0, a[mn], ans[mn], on[mn]; struct SegmentTree { int st[mn << 2]; void update(int id, int l, int r, int u, int val){ if(l > u || r < u) return; if(l == r){ st[id] += val; return; } int mid = (l + r) >> 1; update(id << 1, l, mid, u, val); update(id << 1 | 1, mid + 1, r, u, val); st[id] = st[id << 1] + st[id << 1 | 1]; } int walk(int id, int l, int r, int val){ debug(st[id], l, r, val); if(l == r) return l; int mid = (l + r) >> 1; if(st[id << 1] < val) return walk(id << 1 | 1, mid + 1, r, val); return walk(id << 1, l, mid, val); } int get(int id, int l, int r, int u){ if(l > u) return 0; if(r <= u) return st[id]; int mid = (l + r) >> 1; return get(id << 1, l, mid, u) + get(id << 1 | 1, mid + 1, r, u); } } st_val, st_cnt; vector <int> comp; vector <tuple <int, int, int>> line[mn]; void solve() { cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; comp.push_back(a[i]); } sort(all(comp)); comp.erase(unique(all(comp)), comp.end()); cin >> q; for(int i = 1; i <= q; i++){ int t; cin >> t; k += (t == 1); on[i] = (t == 2); if(t == 2){ int l, r; cin >> l >> r; line[min(l + k - 1, n)].push_back({i, l - 1, - 1}); line[min(r + k, n)].push_back({i, r, 1}); } } for(int i = 1; i <= n; i++){ int val = lower_bound(all(comp), a[i]) - comp.begin() + 1; st_cnt.update(1, 1, n, val, 1); st_val.update(1, 1, n, val, a[i]); debug(val, a[i]); for(auto [id, sz, hs] : line[i]){ int pos = st_cnt.walk(1, 1, n, sz); int cnt = st_cnt.get(1, 1, n, pos); int val = st_val.get(1, 1, n, pos) - (cnt - sz) * comp[pos - 1]; debug(i, id, sz, hs, pos, cnt, st_val.get(1, 1, n, pos), val); ans[id] += hs * val; } } for(int i = 1; i <= q; i++){ if(on[i]) cout << ans[i] << '\n'; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define task "Kawabata" if (fopen(task".INP", "r")) { freopen(task".INP", "r", stdin); freopen(task".OUT", "w", stdout); } int t = 1; // cin >> t; while (t--) solve(); return 0; } // Don't wanna lose anymore T_T // Never let me go - Kazuo Ishiguro

bubble.cpp: In function 'int main()':
bubble.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bubble.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~