Editing 3108 - Dss

== Enunt ==
Se dau N numere naturale s[1], s[2], …, s[N] și Q interogări de forma a b.
== Cerinţa ==
Să se determine pentru fiecare interogare [a;b] numărul de subșiruri formate din elemente distincte ale secvenței s[a], s[a+1], s[a+2], …, s[b].
Prin secvență a șirului s se înțelege orice succesiune de elemente aflate pe poziții consecutive s[a], s[a+1], …, s[b], cu 1 ≤ a ≤ b ≤ N.
Prin subșir al șirului s se înțelege orice succesiune de elemente aflate pe poziții în ordine strict crescătoare, dar nu neapărat consecutive, sa1, sa2, …, sak cu 1 ≤ a1 < a2 < ... < ak ≤ N.
== Date de intrare ==
Fișierul de intrare dss.in conține pe primul rând numerele N și Q. Pe linia a doua sunt scrise N numere naturale separate prin câte un spațiu. Pe următoarele Q rânduri sunt scrise câte două numere naturale a b@, separate prin spațiu, reprezentând capetele intervalelor de interogare date.
== Date de ieșire ==
În fișierul de ieșire dss.out pe fiecare dintre primele Q rânduri este scris câte un număr natural reprezentând numărul tuturor subșirurilor formate din elemente distincte conținute în secvența din interogarea corespunzătoare.
== Restricţii şi precizări ==
* '''1 ≤ N ≤ 400.000'''
* '''1 ≤ Q ≤ 10.000'''
* '''1 ≤ s[k] ≤ N'''
* '''1 ≤ a ≤ b ≤ N'''
Numărul de subșiruri pentru fiecare interogare vor fi calculate modulo 1.000.000.007
== Exemplul 1 ==
; dss.in

  5 3 
  1 2 3 2 3
  1 4
  2 5
  1 3
; dss.out

  11
  8
  7
== Explicație  ==
* - Subșirurile formate din elemente distincte din secvența s[1..4]=(1 2 3 2) sunt 1, 2, 3, 2, 1 2, 1 3, 1 2, 2 3, 3 2, 1 2 3, 1 3 2, deci în total 11 subșiruri.
* - Subșirurile formate din elemente distincte din secvența s[2..5]=(2 3 2 3) sunt 2, 3, 2, 3, 2 3, 2 3, 3 2, 2 3, deci 8 subșiruri.
* - Subșirurile formate din elemente distincte din secvența s[1..3]=(1 2 3) sunt 1, 2, 3, 1 2, 1 3, 2 3, 1 2 3, deci 7 subșiruri.
<br>


== Rezolvare ==
<syntaxhighlight lang="python" line>
def count_subsequences(s, a, b):
    MOD = 1000000007
    n = len(s)
    dp = [0] * (n + 1)
    last_seen = [-1] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        dp[i] = (dp[i - 1] * 2) % MOD
        if last_seen[s[i - 1]] != -1:
            dp[i] = (dp[i] - dp[last_seen[s[i - 1]] - 1] + MOD) % MOD
        last_seen[s[i - 1]] = i
    return (dp[b] - dp[a - 1] + MOD) % MOD

def main():
    with open("dss.in", "r") as fin:
        N, Q = map(int, fin.readline().split())
        s = list(map(int, fin.readline().split()))
        queries = [list(map(int, line.split())) for line in fin]

    with open("dss.out", "w") as fout:
        for a, b in queries:
            fout.write(str(count_subsequences(s, a, b)) + "\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>