1) Criminal Damage for destroying property of another person; the class of felony is set by the amount of damage - ie the value of the thing destroyed. (ARS 13-1602)

2) Arson - if in blowing up the public toilet you caused a fire or explosion that caused the damage. If the structure was occupied by any person at the time that you blew it up, then it is a class 2 felony. (ARS 13-1703 and 13-1704)

3) If you used an 'explosive' to blow up the public toilet, such as dynamite, nitroglycerine, black powder, or something similar, including plastic explosives, and you also intended to hurt or scare anyone you could also be charged with 'Depositing explosives' because you put the explosives in a place frequented by people, which a public toilet is; this is a class 4 felony. (ARS 13-3104)