fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. struct Occ {
  7.     ll x;
  8.     int pos;
  9. };
  10.  
  11. struct Query {
  12.     int l, r, id;
  13. };
  14.  
  15. struct Fenwick {
  16.     int n;
  17.     vector<ll> bit;
  18.  
  19.     Fenwick(int n) : n(n), bit(n + 1, 0) {}
  20.  
  21.     void dodaj(int i, ll v) {
  22.         for (; i <= n; i += i & -i)
  23.             bit[i] += v;
  24.     }
  25.  
  26.     void dodaj_przedzial(int l, int r, ll v) {
  27.         if (l > r) return;
  28.  
  29.         dodaj(l, v);
  30.         dodaj(r + 1, -v);
  31.     }
  32.  
  33.     ll odczytaj(int i) {
  34.         ll wynik = 0;
  35.  
  36.         for (; i > 0; i -= i & -i)
  37.             wynik += bit[i];
  38.  
  39.         return wynik;
  40.     }
  41. };
  42.  
  43. int main() {
  44.     ios_base::sync_with_stdio(0);
  45.     cin.tie(0);
  46.  
  47.     int n, k, q;
  48.     cin >> n >> k >> q;
  49.  
  50.     vector<ll> a(n + 1);
  51.     vector<Occ> wyst(n);
  52.  
  53.     for (int i = 1; i <= n; i++) {
  54.         cin >> a[i];
  55.         wyst[i - 1] = {a[i], i};
  56.     }
  57.  
  58.     // Sortujemy wystąpienia według wartości, a następnie pozycji.
  59.     sort(wyst.begin(), wyst.end(), [](Occ x, Occ y) {
  60.         if (x.x != y.x) return x.x < y.x;
  61.         return x.pos < y.pos;
  62.     });
  63.  
  64.     vector<int> poprzednie(n + 1, 0);
  65.     vector<int> pk(n + 1, 0);
  66.     vector<int> pk1(n + 1, 0);
  67.  
  68.     // Wyznaczamy potrzebne wcześniejsze wystąpienia.
  69.     int start = 0;
  70.  
  71.     while (start < n) {
  72.         int koniec = start + 1;
  73.  
  74.         while (koniec < n &&
  75.                wyst[koniec].x == wyst[start].x) {
  76.             koniec++;
  77.         }
  78.  
  79.         for (int j = start; j < koniec; j++) {
  80.             int i = wyst[j].pos;
  81.             int t = j - start + 1;
  82.  
  83.             // Poprzednie wystąpienie p_(t-1).
  84.             if (t >= 2)
  85.                 poprzednie[i] = wyst[j - 1].pos;
  86.  
  87.             // p_(t-k).
  88.             if (t > k)
  89.                 pk[i] = wyst[j - k].pos;
  90.  
  91.             // p_(t-k-1).
  92.             if (t > k + 1)
  93.                 pk1[i] = wyst[j - k - 1].pos;
  94.         }
  95.  
  96.         start = koniec;
  97.     }
  98.  
  99.     vector<Query> zap(q);
  100.  
  101.     for (int i = 0; i < q; i++) {
  102.         cin >> zap[i].l >> zap[i].r;
  103.         zap[i].id = i;
  104.     }
  105.  
  106.     sort(zap.begin(), zap.end(), [](Query x, Query y) {
  107.         return x.r < y.r;
  108.     });
  109.  
  110.     Fenwick fenwick(n);
  111.     vector<ll> wynik(q);
  112.  
  113.     int j = 0;
  114.  
  115.     for (int i = 1; i <= n; i++) {
  116.         // Usuwamy wkład z lewych końców, które
  117.         // przestały spełniać warunek.
  118.         fenwick.dodaj_przedzial(
  119.             pk1[i] + 1, pk[i], -a[i]
  120.         );
  121.  
  122.         // Dodajemy wkład na nowych lewych końcach.
  123.         fenwick.dodaj_przedzial(
  124.             poprzednie[i] + 1, i, a[i]
  125.         );
  126.  
  127.         // Odpowiadamy na zapytania z prawym końcem i.
  128.         while (j < q && zap[j].r == i) {
  129.             wynik[zap[j].id] =
  130.                 fenwick.odczytaj(zap[j].l);
  131.             j++;
  132.         }
  133.     }
  134.  
  135.     for (int i = 0; i < q; i++)
  136.         cout << wynik[i] << '\n';
  137.  
  138.     return 0;
  139. }
  140.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
9 2 5
1 2 1 3 2 4 1 3 3
1 5
1 7
3 9
2 9
4 6
stdout
copy 
6
9
7
7
9
https://ideone.com/rmtsV4
language:
C++ (gcc 8.3)
created:
11 hours 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!