Escrito por Pedro Racchetti
Conhecimento prévio necessário:
A ideia para resolvermos esse problema, é perceber que se estamos analisando a soma do prefixo de 
, e já encontramos algum outro prefixo com valor igual a esse, então temos que adicionar um novo valor, já que entre esse outro prefixo e , os números com certeza somam a 
. Como esse valor pode ser arbitrariamente grande, podemos adicionar um valor muito grande, tal que nenhum intervalo que passe por ele terá soma 0. Portanto, podemos passar a ignorar todos os prefixos até então, e recomeçar a soma dos prefixos. Para isso, precisamos apenas de uma variável, 
que guardará o prefixo atual, e um 
para guarda todos os prefixos que estão sendo analisados.
Segue o código, comentado, para melhor compreensão do problema:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; //Os valores das somas podem passar de 2*10^9, | |
| //então usaremos essa abreviação pra long long | |
| const int MAXN = 2e5 + 10; | |
| set<ll> s; | |
| ll t[MAXN]; | |
| int main(){ | |
| int n; | |
| scanf("%d", &n); | |
| for(int i = 1; i <= n; i++){ | |
| scanf("%lld", &t[i]); | |
| //lemos os valores das transições | |
| } | |
| s.insert(0); | |
| //iniciaremos o set com valor 0 | |
| //para não testarmos se o prefixo é igual a 0 | |
| //podendo então usar o algoritmo descrito normalmente | |
| int ans = 0; | |
| ll pref = 0; | |
| for(int i = 1; i <= n; i++){ | |
| pref += t[i]; | |
| if(s.find(pref) != s.end()){ | |
| //se existe algum valor no set igual a soma atual, | |
| //sabemos que existe um intervalo de soma 0 | |
| //portanto, inserimos uma nova transação e reiniciamos o set | |
| ans++; | |
| s.clear(); | |
| s.insert(0); | |
| pref = t[i]; | |
| } | |
| //adicionamos o prefixo atual | |
| s.insert(pref); | |
| } | |
| printf("%d\n",ans ); | |
| } |