RebecaBud: Pagină nouă: == 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 a...

2024-06-03T16:37:52Z

Pagină nouă: == 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 a...

New page

== 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>

3108 - Dss - Revision history