# PBinfo #4168 – secvente6 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Notăm cu [x, y], o secvență de numere naturale nenule x, x + 1, x + 2, ..., y, cu x ≤ y.

Considerăm că secvența [p, q] include secvența [a, b] dacă are loc relația p ≤ a ≤ b ≤ q.

Se dau N secvențe speciale de forma [a, b] și apoi T secvențe de interogare [L,R]. Orice secvență care include cel puțin o secvență specială va fi numită secvență super-specială. Numărul de secvențe super-speciale pe care o secvență [L, R] le include va fi denumit capacitatea secvenței [L, R]. 

Cerința
Pentru fiecare secvență de interogare, să se determine capacitatea sa.

Date de intrare
Fișierul de intrare secvente.in conține pe prima linie numărul natural N, reprezentând numărul de secvențe speciale. Pe următoarele N linii se află câte două numere naturale nenule a și b, separate printr-un spațiu, reprezentând secvențele speciale. Pe linia N+2 se află numărul natural T, reprezentând numărul de secvențe de interogare, iar pe următoarele T linii se află câte două numere naturale nenule L și R, separate printr-un spațiu, reprezentând secvențele de interogare.

Date de ieșire
Fișierul de ieșire secvente.out va conține T linii. Pe cea de a i-a linie din fișier se va scrie un singur număr natural, reprezentând capacitatea celei de a i-a secvențe de interogare, în ordinea din fișierul de intrare.

Restricții și precizări

1 ≤ N ≤ 100.000
1 ≤ a ≤ b ≤ 1.000.000.000
1 ≤ T ≤ 100.000
1 ≤ L ≤ R ≤ 1.000.000.000

Exemplu:
secvente.in

2
2 4
3 3
3
2 4
1 5
2 5
secvente.out

4
9
6
Explicație
Secvența de interogare [2,4] conține secvențele super-speciale [2,3], [2,4], [3,3] și [3,4]. Se observă că [2, 2] nu este o secvență super-specială deoarece nu include pe niciuna dintre cele două secvențe speciale ([2, 4] și [3, 3]).

Secvența de interogare [1,5] conține secvențele super-speciale [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,3], [3,4] și [3,5]. 

Secvența de interogare [2,5] conține secvențele super-speciale [2,3], [2,4], [2,5], [3,3], [3,4] și [3,5].

## Cod sursă C++

```cpp
///O(N+T*log(N)); solutia nu depinde de plaja de valori
#include <fstream>
#include <algorithm>
using namespace std;
ifstream  fin("secvente.in");
ofstream fout("secvente.out");
int N,T,k,L,R,p,q,p1,p2,mij;
long long t,sp[100005];
struct secventa{
    int x,y;
}v[100005];
int cmp(secventa a, secventa b){
    if((a.x<b.x) || (a.x==b.x && a.y<b.y))return 1;
    return 0;
}
int main(){
    fin>>N;
    for(int i=1;i<=N;i++){
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+1+N,cmp);
    k=1;
    for(int i=2;i<=N;i++){
        if(v[k].x<v[i].x){
            while(k>0 && v[k].y>=v[i].y)
            {
                k--;
            }
            k++;
            v[k]=v[i];
        }
    }
    N=k;
    ///acum ar trebui sa nu mai existe doua intervale cu includere
    v[N+1]={v[N].y+1,1000001};
    for(int i=1;i<=N;i++){
        sp[i]=sp[i-1]+(long long)(v[i+1].y-v[i].y)*v[i].x;
        ///am adaugat toate secventele care includ secventa v[i]
        ///acestea sunt cele care au capat dreapta in intervalul
        ///[v[i].y;v[i+1].y-1] si capatul stang in intervalul
        ///[1;v[i].x]
    }
    fin>>T;
    for(int i=1;i<=T;i++){
        if(i==5){
            int test=0;
        }
        fin>>L>>R;
        ///cautare binara; O(log(N))
        p1=0;p2=N;p=0;
        while(p1<=p2){
            mij=(p1+p2)/2;
            if(v[mij].x<L){
                p1=mij+1;
            }
            else{
                p=mij;
                p2=mij-1;
            }
        }
        if(p==0 || v[p].y>R){
            fout<<0<<"\n";
        }
        else{
            ///cautare binara; O(log(N))
            p1=p;p2=N;q=0;
            while(p1<=p2){
                mij=(p1+p2)/2;
                if(v[mij].y>R){
                    p2=mij-1;
                }
                else{
                    q=mij;
                    p1=mij+1;
                }
            }
            t=sp[q]-sp[p-1];
            ///avem acum toate secventele cu capat drept
            ///in intervalul [v[p].y;v[q+1].y-1]
            ///si capatul stang corespunzator
            t=t-(long long)(v[q+1].y-R-1)*v[q].x;
            ///am eliminat capetele drepte din zona [v[q+1].y-1;R+1]
            t=t-(long long)(R-v[p].y+1)*(L-1);
            ///am eliminat pentru capetele drepte din [v[p].y;R]
            ///capetele stangi din intervalul [1;L-1]
            fout<<t<<"\n";
        }
    }
    fout.close(); fin.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4168)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4168/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4168/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)