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.

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>