#!/usr/bin/python
# -*- coding: utf-8 -*-

# Používáme knihovnu pybst pro vyhledávací stromy, viz https://pypi.python.org/pypi/pybst/1.0
import pybst.avltree

# Ovšem trochu si ji musíme rozšířit, aby uměla hledat předchůdce
class MyBST(pybst.avltree.AVLTree):

    # Předchůdce x, tedy největší z hodnot ve stromu, které jsou menší než x
    def pred(self, x):
        return self.pred2(x, self.Root, None)

    # Interní funkce: hledáme předchůdce x, momentálně jsme ve vrcholu node
    # a zatím nejlepší kandidát je pr
    def pred2(self, x, node, pr):
        if not node:
	    return pr;
	if node.key < x:
	    return self.pred2(x, node.right, node)
	else:
	    return self.pred2(x, node.left, pr)

# Strom, který udržuje všechny nalezené linie. Klíče jsou délky linií,
# hodnoty ve vrcholech udávají, kolik linií dané délky existuje. Snadno
# by ho šlo upravit, aby udržoval i polohy linií na hracím plánu.
class SumTree:

    def __init__(self):
	self.tree = MyBST()

    # Vloží novou linii
    def insert(self, i):
	n = self.tree.get_node(i)
	if not n:
	    self.tree.insert(i, 0)
	    n = self.tree.get_node(i)
	n.value = n.value + 1

    # Smaže linii
    def delete(self, i):
        n = self.tree.get_node(i)
	n.value = n.value - 1
	if n.value == 0:
	    self.tree.delete(i)

    # Vrátí aktuální nejdelší linii, nebo 0, pokud žádná není
    def max(self):
	m = self.tree.get_max()
	if m:
	    return m.key
	else:
	    return 0

# Základní verze úlohy: 1 rozměr, 1 druh symbolů
class Pish:

    def __init__(self, n, sumtree):
	self.left = [0] * (n+1)		# Pokud je na pozici i levý okraj intervalu, left[i] říká, kde je pravý
	self.right = [0] * (n+1)	# Analogicky right[i] přiřazuje k pravému okraji intervalu ten levý
	self.starts = MyBST()		# Vyhledávací strom obsahující pozice všech levých okrajů
	self.sumtree = sumtree		# Odkaz na souhrnný strom všech linií

    # Přidá značku na pozici i
    def add(self, i):
	i = i+1				# Pozice číslujeme od 1 (pozice 0 je rezervovaná)
	l = self.right[i-1]		# Podíváme se, zda je těsně před námi konec, případně těsně za námi začátek intervalu
	r = self.left[i+1]
	if l>0 and r>0:			# Spojujeme interval před námi s intervalem za námi
	    self.right[i-1] = 0
	    self.left[i+1] = 0
	    self.left[l] = r
	    self.right[r] = l
	    self.starts.delete(i+1)
	    self.sumtree.delete(i-l)
	    self.sumtree.delete(r-i)
	    self.sumtree.insert(r-l+1)
	elif l>0:			# Rozšiřujeme doprava interval před námi
	    self.right[i-1] = 0
	    self.right[i] = l
	    self.left[l] = i
	    self.sumtree.delete(i-l)
	    self.sumtree.insert(i-l+1)
	elif r>0:			# Rozšiřujeme doleva interval za námi
	    self.left[i+1] = 0
	    self.left[i] = r
	    self.right[r] = i
	    self.starts.delete(i+1)
	    self.sumtree.delete(r-i)
	    self.sumtree.insert(r-i+1)
	else:				# Vzniká nový jednoprvkový interval
	    self.left[i] = i
	    self.right[i] = i
	    self.starts.insert(i, 0)
	    self.sumtree.insert(1)

    # Odstraní značku z pozice i
    def rm(self, i):
	i = i+1				# Pozice číslujeme od 1
	l = self.right[i]		# Leží naše značka na začátku nebo konci intervalu?
	r = self.left[i]
	if r > 0:			# Jsme na začátku intervalu, posouváme tedy jeho začátek doprava
	    self.left[i] = 0
	    self.right[i] = 0
	    self.starts.delete(i)
	    self.sumtree.delete(r-i+1)
	    if r > i:			# Zbylo z něj ještě něco?
	        self.left[i+1] = r
		self.right[r] = i+1
		self.starts.insert(i+1, 0)
		self.sumtree.insert(r-i)
	elif l > 0:			# Jsme na konci intervalu, posouváme tedy konec doleva
	    self.right[i] = 0
	    self.sumtree.delete(i-l+1)
	    self.right[i-1] = l
	    self.left[l] = i-1
	    self.sumtree.insert(i-l)
	else:				# Jsme uvnitř intervalu, takže ho budeme dělit na dva
	    l = self.starts.pred(i).key	# Kde interval začíná a končí?
	    r = self.left[l]
	    self.right[i-1] = l
	    self.left[l] = i-1
	    self.left[i+1] = r
	    self.right[r] = i+1
	    self.sumtree.delete(r-l+1)
	    self.sumtree.insert(i-l)
	    self.sumtree.insert(r-i)
	    self.starts.insert(i+1, 0)

# 1D verze úlohy se dvěma druhy symbolů
class Pish1D:

    def __init__(self, n, sumtree):
	# Pamatujeme si, kde je která značka, a pak pro každou značku její intervalovou strukturu
	self.marks = [' '] * n
	self.parts = { 'x': Pish(n, sumtree), 'o': Pish(n, sumtree) };

    # Zapíše na pozici i značku x (křížek, kolečko, nebo mezeru)
    def set(self, i, x):
	(old, self.marks[i]) = (self.marks[i], x)
	if old != ' ':
	    self.parts[old].rm(i)
	if x != ' ':
	    self.parts[x].add(i)

# 2D verze úlohy se dvěma druhy symbolů
class Pish2D:

    def __init__(self, n):
	self.n = n
	# Souhrnný strom se všemi nalezenými liniemi
	self.sumtree = SumTree()
	# 1D struktury pro jednotlivé řádky, sloupce a oba druhy úhlopříček
	self.horiz = [ Pish1D(n, self.sumtree) for x in range(n) ]
	self.vert  = [ Pish1D(n, self.sumtree) for x in range(n) ]
	self.diag  = [ Pish1D(n, self.sumtree) for x in range(2*n) ]
	self.gaid  = [ Pish1D(n, self.sumtree) for x in range(2*n) ]

    # Zapíše na pozici (i,j) značku x (křížek, kolečko, nebo mezeru)
    def set(self, i, j, x):
	self.horiz[i].set(j, x)
	self.vert[j].set(i, x)
	self.diag[i+j].set((i+self.n-j)//2, x)
	self.gaid[i+self.n-j].set((i+j)//2, x)

    # Vrátí délku nejdelší linie (nebo 0, pokud žádná neexistuje)
    def max(self):
	return self.sumtree.max()

# Příklad použití
p = Pish2D(20)
p.set(5, 5, 'x')
print p.max()
p.set(6, 5, 'x')
print p.max()
p.set(7, 5, 'x')
print p.max()
p.set(6, 5, 'o')
print p.max()
p.set(7, 6, 'o')
p.set(5, 4, 'o')
p.set(4, 3, 'o')
print p.max()