[PYTHON] Méthode de la somme cumulée et de la pomme de terre

J'ai implémenté la méthode Imos lorsque je résolvais ABC035-C, donc je la laisserai comme mémo. De plus, nous aimerions la dernière touche pour tout type de look ou si vous l'utilisez à l'époque, y compris la somme cumulée. (Puisque j'ai étudié la méthode Imomosu pour la première fois cette fois, il peut y avoir des erreurs. J'apprécierais que vous le signaliez.)

Méthode Imos et sa mise en œuvre

L'énoncé du problème de ABC035-C est le suivant.

Si vous voulez l'implémenter selon l'énoncé du problème, vous pouvez répéter l'opération consistant à retourner les pièces de $ l $ à $ r $, alors préparez un tableau pour N pièces (initialisez avec True ou False au début), et Q Inversez chaque élément de $ l_i $ à $ r_i $ à chaque fois, et le code sera le suivant.

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

Cependant, la contrainte de n et q est $ 2 \ times {10} ^ 5 , et le pire temps de calcul est O ( nq $), donc nous pouvons voir que la limite de temps n'est pas respectée.

La méthode Imos peut être utilisée ici (une méthode très efficace car vous pouvez penser à l'expansion des dimensions et aux figures spéciales. On pense.). Dans la méthode Imos, l'addition est effectuée à l'entrée et la soustraction est effectuée à la sortie (enregistrement). Ensuite, lorsque l'étape d'enregistrement est terminée, ajoutez-les dans l'ordre depuis l'avant (simuler).

Par conséquent, dans ce problème, lors du passage du lème au rème, le lème élément est +1 et le r + 1er élément est -1. En faisant cela, lors de la simulation après l'enregistrement, les valeurs des éléments précédents sont ajoutées dans l'ordre (la somme cumulée est calculée dans l'ordre à partir de l'élément précédent), de sorte que le nombre de fois que chaque élément est retourné peut être déterminé. Il peut être calculé avec une petite quantité de calcul. (En considérant quand +1 est appliqué au l-ème élément et -1 est appliqué au r + 1-ème élément, si la boucle est tournée avec i: 0 → n, seuls les l-ième à r-ième éléments valent 1 et les autres éléments sont Vous pouvez voir que c'est 0.) Si vous implémentez ce qui précède tel quel, le code sera le suivant (O ($ n + q $)).

De plus, bien que cela n'ait rien à voir avec la méthode Imomosu, changer l'entrée en sys.stdin.readline réduit le temps d'exécution d'environ la moitié, donc je pense que les utilisateurs de Python devraient l'essayer.

answerC2.py

#Méthode Imosu
import sys
#input→sys.stdin.readline en deux fois moins de temps
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))))

Comment utiliser la méthode Imos et la somme cumulée

Puisque je pense avoir expliqué la mise en œuvre de la méthode Imosu dans ABC035 dans la section précédente, je voudrais généraliser quand l'utiliser réellement.

Premièrement, dans le cas de la méthode Imos, elle est considérée comme utilisée lorsque ** la valeur de chaque section est mise à jour plusieurs fois et enfin la valeur totale est calculée collectivement **. Dans un tel cas, le montant du calcul peut être considérablement réduit en ajoutant et en soustrayant chacune des ** uniquement l'entrée et la sortie de la section ** d'abord, puis en calculant la somme cumulée à la fin.

Par contre, dans le cas d'une somme cumulée, ** la valeur de l'intervalle n'est pas mise à jour, et elle est considérée comme utilisée lorsque l'on veut trouver la valeur de plusieurs intervalles à la fin **. Dans un tel cas, considérez ** la somme cumulée de l'élément de référence (dans de nombreux cas, le premier ou le dernier élément) **, et lors du calcul, considérez la différence entre les sommes cumulées jusqu'à chaque élément. La réflexion peut réduire considérablement la quantité de calcul.

Bonus (problème avec la méthode Imos)

ABC014-C

answerC.cc

import sys
#input→sys.stdin.readline3/Dans 4 heures
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)