Codeforces Persistent Bookcase Solution in Java

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.Scanner;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Swatantra
 */
public class TaskC {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        static int shelf[];
        static int cases[][];
        static int res[];
        static List<Node> l[];
        int total = 0;
        int n;
        int m;

        public void solve(int testNumber, Scanner in, PrintWriter out) {


            int q;
            n = in.nextInt();
            m = in.nextInt();
            q = in.nextInt();
            int i;
            shelf = new int[n];
            cases = new int[n][m];
            res = new int[q];
            l = new ArrayList[q + 1];
            for (i = 0; i <= q; i++) {
                l[i] = new ArrayList<Node>();
            }
            //System.out.print("Resting");
            for (i = 0; i < q; i++) {
                int qu = in.nextInt();

                if (qu == 1 || qu == 2) {
                    int x = in.nextInt() - 1;
                    int y = in.nextInt() - 1;
                    l[i].add(new Node(i + 1, qu, x, y));
                } else if (qu == 3) {
                    int x = in.nextInt() - 1;
                    l[i].add(new Node(i + 1, qu, x));
                } else {
                    int x = in.nextInt();
                    //System.out.println("x is="+x);
                    l[x].add(new Node(i + 1, qu, x));

                }
            }
            dfs(0);

            for (i = 0; i < q; i++) {
                out.println(res[i]);
            }


        }

        void dfs(int v) {
            for (Node u : l[v]) {

                int type = u.t;

                //out.println("Next Node is="+(u.next));
                if (type == 1) {
                    // out.println("Entered 1");
                    boolean modi = false;
                    int i = u.x;
                    int j = u.y;

                    if (cases[i][j] != 1) {
                        cases[i][j] = 1;
                        shelf[i]++;
                        total++;
                        modi = true;
                    }
                    res[u.next - 1] = total;
                    //out.println("Entering "+u.next);
                    dfs(u.next);
                    if (modi) {
                        shelf[i]--;
                        cases[i][j] = 0;
                        total--;
                    }
                } else if (type == 2) {
                    //out.println("Entered 2");
                    boolean modi = false;
                    int i = u.x;
                    int j = u.y;
                    if (cases[i][j] != 0) {
                        cases[i][j] = 0;
                        shelf[i]--;
                        total--;
                        modi = true;
                    }
                    res[u.next - 1] = total;
                    //out.println("Entering "+u.next);
                    dfs(u.next);

                    if (modi) {
                        shelf[i]++;
                        cases[i][j] = 1;
                        total++;

                    }
                } else if (type == 3) {
                    //out.println("Entered 3");
                    int i = u.x;
                    int p;
                    for (p = 0; p < m; p++) {
                        cases[i][p] ^= 1;
                    }

                    total = total - shelf[i];
                    shelf[i] = m - shelf[i];
                    total += shelf[i];
                    //out.print("total is="+total);
                    res[u.next - 1] = total;
                    //out.println("Entering "+u.next);
                    dfs(u.next);
                    total = total - shelf[i];
                    shelf[i] = m - shelf[i];
                    total += shelf[i];
                    //out.print("total is="+total);
                    for (p = 0; p < m; p++) {
                        cases[i][p] ^= 1;
                    }


                } else {
                    //out.println("Entered 4");
                    res[u.next - 1] = total;
                    // out.println("Entering "+u.next);
                    dfs(u.next);
                }

            }
        }

        class Node {
            int t;
            int next;
            int x;
            int y;

            Node(int next, int t, int x, int y) {
                this.t = t;
                this.next = next;
                this.x = x;
                this.y = y;

            }

            Node(int next, int t, int x) {
                this.t = t;
                this.next = next;
                this.x = x;
            }

        }

    }
}