Per mostrare lo spirito delle feste, le mucche vogliono dipingere! Il quadro è una griglia $R$ $\times$ $C$ $(1 \le R \le 50,000; 1 \le C \le 15)$ di quadrati unitari, ciascuno0 o1. Le righe sono numerate $1,\ldots,R$, le colonne $1,\ldots,C$.
Avendo poco tempo, chiedono aiuto ai vicini a nord del confine. Sotto la gentile guida dell’alce Canmuu costruiscono una macchina che getta interi secchi di vernice sul quadro! All’inizio la griglia è tutta0; la macchina colora un rettangolo con0 o1. Canmuu propone $Q$ operazioni $(1 \le Q \le 10,000)$; operazione $i$ ha cinque interi $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$ $(1 \le R1_i \le R2_i \le R; 1 \le C1_i \le C2_i \le C; 0 \le X_{i} \le 1)$ e colora di $X_{i}$ tutte le celle nelle righe fra $R1_{i}$ e $R2_{i}$ e colonne fra $C1_{i}$ e $C2_{i}$, estremi inclusi.
È facile sbagliare così, quindi Canmuu chiede di determinare dopo ogni operazione quanti quadrati hanno il colore giusto.
Limite di memoria:64 MB
Limite di tempo:1.5 secondi
Input
- Riga1: tre interi separati da spazi $R$, $C$, $Q$.
- Righe $2,\ldots,R+1$: riga $i+1$ contiene $C$ caratteri '0' o '1', rappresentando la riga $i$.
- Righe $R+2,\ldots,R+Q+1$: riga $R+i+1$ contiene cinque interi separati da spazi di un’operazione: $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$.
Output
- Righe $1,\ldots,Q$: sulla riga $i+1$ stampa un intero, il numero di celle coincidenti dopo operazione $i$.
Esempi
Input 1
17 15 10 111111101111111 111111000111111 111110000011111 111100000001111 111000000000111 111100000001111 111000000000111 110000000000011 111000000000111 110000000000011 100000000000001 110000000000011 100000000000001 000000000000000 111111000111111 111111000111111 111111000111111 5 8 2 14 1 8 17 3 7 1 4 5 10 15 0 7 16 12 14 1 2 17 13 14 0 2 6 2 3 1 13 14 4 8 1 3 6 6 7 1 1 16 10 11 0 7 16 10 10 0
Output 1
113 94 95 91 87 93 91 87 93 93
Nota
Le mucche vogliono dipingere un albero delle feste.
Dopo la prima operazione la griglia è:
000000000000000 000000000000000 000000000000000 000000000000000 011111111111110 011111111111110 011111111111110 011111111111110 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000
113 quadrati coincidono con quelli corrispondenti nell’albero; sotto sono segnati 'x' (gli altri bit mostrano lo stato dopo il primo lancio di vernice):
0000000x0000000 000000xxx000000 00000xxxxx00000 0000xxxxxxx0000 0xx111111111xx0 0xxx1111111xxx0 0xx111111111xx0 0x11111111111x0 000xxxxxxxxx000 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 xxxxxxxxxxxxxxx 000000xxx000000 000000xxx000000 000000xxx000000
Autori del problema: Brian Hamrick e Neal Wu, 2008