[PYTHON] Kumulative Summen- und Kartoffelmethode

Ich habe die Imos-Methode implementiert, als ich ABC035-C gelöst habe, daher werde ich sie als Memo belassen. Darüber hinaus möchten wir die letzte Berührung für jede Art von sieht gut aus oder wenn Sie zu der Zeit verwenden, einschließlich der kumulierten Summe. (Da ich dieses Mal zum ersten Mal die Imomosu-Methode studiert habe, kann es einige Fehler geben. Ich würde es begrüßen, wenn Sie darauf hinweisen könnten.)

Imos-Methode und ihre Implementierung

Die Problemstellung von ABC035-C lautet wie folgt.

Wenn Sie es gemäß der Problemstellung implementieren möchten, können Sie den Vorgang des Spiegelns der Teile von $ l $ auf $ r $ wiederholen. Bereiten Sie also ein Array für N Teile vor (initialisieren Sie zuerst mit True oder False) und Q. Invertieren Sie jedes Element zu jedem Zeitpunkt von $ l_i $ zu $ r_i $, und der Code lautet wie folgt.

answerC1.py

def int2(k):
    return int(k)-1
n,q=map(int,input().split())
lr=[list(map(int2,input().split())) for i in range(q)]
x=[False]*n
for i in range(q):
    for j in range(lr[i][0],lr[i][1]+1):
        x[j]=not x[j]
print("".join(list(map(str,map(int,x)))))

Die Einschränkung von n und q ist jedoch $ 2 \ times {10} ^ 5 , und die schlechteste Berechnungszeit ist O ( nq $), sodass wir sehen können, dass das Zeitlimit nicht eingehalten wird.

Hier kann die Imos-Methode verwendet werden (eine sehr effektive Methode, da Sie über Dimensionserweiterungen und spezielle Zahlen nachdenken können. Man glaubt.). Bei der Imos-Methode wird die Addition am Eingang und die Subtraktion am Ausgang durchgeführt (Aufzeichnung). Wenn die Aufnahmephase beendet ist, fügen Sie sie in der Reihenfolge von vorne hinzu (simulieren).

Daher ist in diesem Problem beim Umschalten vom l-ten zum r-ten das l-te Element +1 und das r + 1-Element -1. Auf diese Weise werden bei der Simulation nach der Aufzeichnung die Werte der vorherigen Elemente der Reihe nach addiert (die kumulative Summe wird in der Reihenfolge des vorherigen Elements berechnet), sodass bestimmt werden kann, wie oft jedes Element umgedreht wird. Sie kann mit geringem Rechenaufwand berechnet werden. (Berücksichtigt man, wenn +1 auf das l-te Element und -1 auf das r + 1-te Element angewendet wird, sind nur die l-ten bis r-ten Elemente 1 und die anderen Elemente 1, wenn die Schleife mit i: 0 → n gedreht wird Sie können sehen, dass es 0 ist.) Wenn Sie das oben Gesagte so implementieren, lautet der Code wie folgt (O ($ n + q $)).

Auch wenn es nichts mit der Imomosu-Methode zu tun hat, verkürzt das Ändern der Eingabe in sys.stdin.readline die Ausführungszeit um etwa die Hälfte, daher denke ich, dass Python-Benutzer es versuchen sollten.

answerC2.py

#Imosu-Methode
import sys
#input→sys.stdin.Readline in der Hälfte der Zeit
input=sys.stdin.readline
n,q=map(int,input().split())
x=[0]*n
for i in range(q):
    l,r=map(int,input().split())
    x[l-1]+=1
    if r<n:
        x[r]-=1
for i in range(n-1):
    x[i+1]+=x[i]
    x[i]%=2
x[n-1]%=2
print("".join(list(map(str,x))))

Verwendung der Imos-Methode und der kumulierten Summe

Da ich die Implementierung der Imosu-Methode in ABC035 im vorherigen Abschnitt erläutert habe, möchte ich verallgemeinern, wann sie tatsächlich verwendet werden soll.

Erstens wird im Fall der Imos-Methode davon ausgegangen, dass sie verwendet wird, wenn ** der Wert jedes Abschnitts viele Male aktualisiert wird und schließlich der Gesamtwert kollektiv berechnet wird **. In einem solchen Fall kann der Rechenaufwand erheblich reduziert werden, indem zuerst nur ** der Eingang und der Ausgang des Abschnitts ** addiert und subtrahiert werden und dann am Ende die kumulative Summe berechnet wird.

Andererseits wird im Fall einer kumulativen Summe ** der Wert des Intervalls nicht aktualisiert und gilt als verwendet, wenn Sie den Wert mehrerer Intervalle am Ende ** ermitteln möchten. Berücksichtigen Sie in einem solchen Fall ** die kumulative Summe aus dem Referenzelement (in vielen Fällen das erste oder letzte Element) ** und berücksichtigen Sie bei der Berechnung die Differenz zwischen den kumulierten Summen bis zu jedem Element. Denken kann den Rechenaufwand erheblich reduzieren.

Bonus (Problem mit der Imos-Methode)

ABC014-C

answerC.cc

import sys
#input→sys.stdin.readline3/In 4 Stunden
input=sys.stdin.readline
n=int(input())
x=[0]*1000001
for i in range(n):
    a,b=map(int,input().split())
    x[a]+=1
    if b+1<1000001:
        x[b+1]-=1
ans=x[0]
for i in range(1000000):
    x[i+1]+=x[i]
    ans=max(ans,x[i+1])
print(ans)