Această problemă se numește Calafat pentru că a fost compusă în timpul excursiei la Calafat de mâine.

Cerința

Se dă un șir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvență cuprinsă între 2 indici st si dr considerăm distanța dintre indicii primei și ultimei apariții ale acesteia în cadrul subsecvenței. Dându-se M subsecvențe de forma [st,dr], se cere să se calculeze suma distanțelor corespunzătoare tuturor valorilor distincte din subsecvență.

Date de intrare

Fișierul de intrare calafat.in conține pe prima linie două numere natural N și M. Pe a doua linie se vor afla cele N numere din șirul dat. Pe următoarele M linii se vor afla câte două numere st și dr, cu semnificația că vrem să calculăm suma menționată mai sus pentru subsecvența [st,dr].

Date de ieșire

Fișierul de ieșire calafat.out va conține M numere naturale, câte unul pe fiecare linie, reprezentând cele M sume cerute.

Restricții și precizări

1 ≤ N, M ≤ 200000
1 ≤ st ≤ dr ≤ N
Valorile din șir se vor afla în intervalul [1, N]
Pentru 20% din teste se garantează că N, M ≤ 1000
Pentru alte 25% din teste se garantează că N, M ≤ 35 000 iar numărul de elemente distincte din șir este maxim 100.
Pentru alte 25% din teste se garantează că N, M ≤ 70 000

Exemplu

calafat.in

7 3
1 3 1 2 2 1 3
2 4
2 7
3 6

calafat.out

0
9
4

Explicație

În prima subsecvență fiecare valoare apare o singură dată, deci suma diferențelor este 0.

În a doua subsecvență:

Valoarea 3 apare la indicii 2 și 7 rezultând diferența 7-2=5
Valoarea 1 apare la indicii 3 și 6 => diferența 6–3=3
Valoarea 2 apare la indicii 4 și 5 => diferența 5-4=1

Suma diferențelor este 9.

În a treia subsecvență:

Valoarea 1 apare la indicii 3 și 6 => diferența 6–3=3
Valoarea 2 apare la indicii 4 și 5 => diferența 5-4=1

Suma diferențelor este 4.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Calafat:

#include <fstream>
#include <cassert>
#include <vector>

using namespace std;

ifstream f("calafat.in");
ofstream g("calafat.out");

const int Nmax = 200000;
const int Qmax = 200000;

const int Q = Qmax + 10;
const int N = Nmax + 10;

vector<pair<int, int> > qr[N];
pair<int, int> upd[N];
long long sol[Q], A[N];
int last[N], n, q, l, r, x;

void update(int p, int x) {
    for(; p <= n; p += p & -p) {
        A[p] += x;
    }
}

long long find(int p) {
    long long sum = 0;
    for (; p; p -= p & -p) {
        sum += A[p];
    }
    return sum;
}

int main () {
    f >> n >> q;
    assert(n >= 1 && n <= Nmax);
    assert(q >= 1 && q <= Qmax);
    for (int i = 1; i <= n; ++i) {
        f >> x;
        assert(x >= 1 && x <= Nmax);
        if (!last[x]) {
            last[x] = i;
        } else {
            upd[i] = make_pair(last[x], i - last[x]);
            last[x] = i;
        }
    }
    for (int i = 1; i <= q; ++i) {
        f >> l >> r;
        assert(l <= r && 1 <= l && l <= n && 1 <= r && r <= n);
        qr[r].push_back(make_pair(l, i));
    }
    for (int i = 1; i <= n; ++i) {
        if (upd[i].first) {
            update(upd[i].first, upd[i].second);
        }
        for (auto &it : qr[i]) {
            sol[it.second] = find(i) - find(it.first - 1);
        }
    }
    for (int i = 1; i <= q; ++i) {
        g << sol[i] << "
";
    }
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1692 Calafat

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1692 Calafat de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1692 Calafat