fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. struct Fenwick {
  6.     int n;
  7.     vector<ll> bit;
  8.     Fenwick(int _n=0){ init(_n); }
  9.     void init(int _n){
  10.         n = _n;
  11.         bit.assign(n+1, 0);
  12.     }
  13.     void add(int idx, ll val){
  14.         for(; idx<=n; idx += idx&-idx) bit[idx] += val;
  15.     }
  16.     ll sumPrefix(int idx){
  17.         ll r=0;
  18.         for(; idx>0; idx -= idx&-idx) r += bit[idx];
  19.         return r;
  20.     }
  21.     ll rangeSum(int l, int r){
  22.         if(r < l) return 0;
  23.         return sumPrefix(r) - sumPrefix(l-1);
  24.     }
  25. };
  26.  
  27. int main(){
  28.     ios::sync_with_stdio(false);
  29.     cin.tie(nullptr);
  30.     int n, q;
  31.     if(!(cin >> n >> q)) return 0;
  32.     vector<int> a(n+1);
  33.     for(int i=1;i<=n;i++) cin >> a[i];
  34.  
  35.     // compress values
  36.     vector<int> vals(a.begin()+1, a.end());
  37.     sort(vals.begin(), vals.end());
  38.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  39.     for(int i=1;i<=n;i++){
  40.         a[i] = int(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin());
  41.     }
  42.     int V = vals.size();
  43.  
  44.     // positions per value
  45.     vector<vector<int>> pos(V);
  46.     for(int i=1;i<=n;i++){
  47.         pos[a[i]].push_back(i);
  48.     }
  49.  
  50.     int B = max(320, (int)sqrt(n)); // threshold, tweakable
  51.  
  52.     vector<int> isHeavy(V, 0);
  53.     vector<int> heavyList;
  54.     for(int v=0; v<V; ++v){
  55.         if((int)pos[v].size() > B){
  56.             isHeavy[v] = 1;
  57.             heavyList.push_back(v);
  58.         }
  59.     }
  60.  
  61.     // prefix arrays for each value: prefPos (sum p) and prefJP (sum j*p where j is 0-based index in pos)
  62.     // We'll store prefP0[i] = sum_{t=0..i-1} pos[t], prefJP[i] = sum_{t=0..i-1} t*pos[t]
  63.     vector<vector<ll>> prefP0(V), prefJP(V);
  64.     for(int v=0; v<V; ++v){
  65.         int m = pos[v].size();
  66.         prefP0[v].assign(m+1, 0);
  67.         prefJP[v].assign(m+1, 0);
  68.         for(int t=0; t<m; ++t){
  69.             prefP0[v][t+1] = prefP0[v][t] + pos[v][t];
  70.             prefJP[v][t+1] = prefJP[v][t] + 1LL * t * pos[v][t];
  71.         }
  72.     }
  73.  
  74.     // Read queries, store and group by r for offline processing for light values
  75.     struct Query { int l, r, idx; };
  76.     vector<vector<Query>> qryAtR(n+1);
  77.     vector<ll> ans(q, 0);
  78.     for(int i=0;i<q;i++){
  79.         int l,r; cin >> l >> r;
  80.         qryAtR[r].push_back({l,r,i});
  81.     }
  82.  
  83.     // Prepare events for light-values: for each pair (i<j) of same light-value, we push i into events[j]
  84.     // Then when sweep r from 1..n, for each i in events[r] we add updates at position i:
  85.     // BIT_count.add(i, 1); BIT_sum.add(i, j);
  86.     vector<vector<int>> events(n+1);
  87.     ll totalPairsLight = 0;
  88.     for(int v=0; v<V; ++v){
  89.         if(isHeavy[v]) continue;
  90.         auto &P = pos[v];
  91.         int m = P.size();
  92.         // generate all pairs i<j
  93.         for(int i=0;i<m;i++){
  94.             for(int j=i+1;j<m;j++){
  95.                 events[P[j]].push_back(P[i]);
  96.                 totalPairsLight++;
  97.             }
  98.         }
  99.     }
  100.     // cerr << "totalPairsLight = " << totalPairsLight << "\n";
  101.  
  102.     // Fenwick trees: one for count of pairs (indexed by i), one for sum of j values
  103.     Fenwick bitCnt(n), bitSum(n);
  104.  
  105.     // Sweep r = 1..n
  106.     for(int r=1; r<=n; ++r){
  107.         // apply all events at r (these correspond to all pairs (i,r) where value is light and i < r)
  108.         for(int iPos : events[r]){
  109.             bitCnt.add(iPos, 1);
  110.             bitSum.add(iPos, r);
  111.         }
  112.  
  113.         // answer queries with this right endpoint r: contribution from light-values
  114.         for(auto &Q : qryAtR[r]){
  115.             int l = Q.l;
  116.             int idx = Q.idx;
  117.             ll cnt = bitCnt.rangeSum(l, r);          // number of pairs with i in [l,r] and j <= r
  118.             ll sumJ = bitSum.rangeSum(l, r);         // sum of j over those pairs
  119.             ll eq_light = (r + 1LL) * cnt - sumJ;
  120.             ans[idx] = eq_light; // we store EQ_light for now; will subtract from TOTAL and add heavy later
  121.         }
  122.     }
  123.  
  124.     // Now for each query we need TOTAL(l,r) and EQ_heavy(l,r) and combine:
  125.     // Precompute nothing else: compute heavy contributions per query directly.
  126.     // We'll process queries again in original order.
  127.     for(int r=1; r<=n; ++r){
  128.         // nothing here; heavy handled per query below
  129.     }
  130.  
  131.     // For convenience, gather queries in a vector with original order to compute final answers
  132.     // We need to re-read queries? We stored queries only grouped by r; but we need (l,r) for each index.
  133.     // Let's reconstruct array of queries by scanning qryAtR.
  134.     vector<pair<int,int>> queries(q);
  135.     for(int r=1; r<=n; ++r){
  136.         for(auto &Q : qryAtR[r]){
  137.             queries[Q.idx] = {Q.l, Q.r};
  138.         }
  139.     }
  140.  
  141.     // Function to compute TOTAL(l,r)
  142.     auto computeTotal = [&](int l, int r)->ll {
  143.         if(l >= r) return 0LL;
  144.         ll m = r - l;
  145.         // total = (m+1) * (m*(m+1)/2) - (m*(m+1)*(2*m+1)/6)
  146.         ll term1 = (m + 1) * (m * (m + 1) / 2);
  147.         ll term2 = (m * (m + 1) * (2*m + 1) / 6);
  148.         return term1 - term2;
  149.     };
  150.  
  151.     // For each query compute heavy contribution and finalize answer
  152.     for(int idx=0; idx<q; ++idx){
  153.         int l = queries[idx].first;
  154.         int r = queries[idx].second;
  155.         ll total = computeTotal(l, r);
  156.         ll eq = ans[idx]; // from light
  157.         // add heavy contributions
  158.         for(int v : heavyList){
  159.             auto &P = pos[v];
  160.             // find L0 = first index in P with >= l, R0 = last index <= r
  161.             int L0 = int(lower_bound(P.begin(), P.end(), l) - P.begin());
  162.             int R0 = int(upper_bound(P.begin(), P.end(), r) - P.begin()) - 1;
  163.             if(L0 <= R0){
  164.                 int cnt = R0 - L0 + 1;
  165.                 if(cnt >= 2){
  166.                     // sum_k = cnt*(cnt-1)/2
  167.                     ll sumk = 1LL * cnt * (cnt - 1) / 2;
  168.                     // Spos = sum_{j=L0+1..R0} (j-L0) * P[j]
  169.                     // = (sum j*P[j]) - L0*(sum P[j]) over j=L0+1..R0 where j is 0-based index in P
  170.                     // Using pref arrays prefP0 and prefJP:
  171.                     int left = L0 + 1; // inclusive index in pref arrays (since pref arrays are prefix up to t-1)
  172.                     int right = R0 + 1; // exclusive indexing for pref arrays usage
  173.                     // sum P[j] for j = L0+1..R0 = prefP0[right] - prefP0[left]
  174.                     ll sumP = prefP0[v][right] - prefP0[v][left];
  175.                     // sum j*P[j] for j = L0+1..R0 = prefJP[right] - prefJP[left]
  176.                     ll sumJP = prefJP[v][right] - prefJP[v][left];
  177.                     ll Spos = sumJP - 1LL * L0 * sumP;
  178.                     ll termv = (r + 1LL) * sumk - Spos;
  179.                     eq += termv;
  180.                 }
  181.             }
  182.         }
  183.         ll res = total - eq;
  184.         cout << res << '\n';
  185.     }
  186.  
  187.     return 0;
  188. }
  189.  
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
4 4
1 2 1 3
1 1
2 3
2 4
1 4
stdout
copy 
0
1
4
8
https://ideone.com/CVCpVw
language:
C++14 (gcc 8.3)
created:
4 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!