Codeforces Round #366 Thor

题意：

手机有n个应用，每个应用都能发推送信息。然后推送信息是顺序的。现在有三种操作：1. 应用x发送了一个推送；2. 将应用x的所有推送标为已读；3. 将手机前x个推送标记为已读。已读的推送依然不会被删除，只是已读。

题解：

怎么定义菜呢？我看到这个题的第一反应居然是，对信息队列建个线段树，然后更新点，但是查询区间和。（但显然行这是不通的）

但其实就是个乱搞的水题。维护5个东西：

1. count[x]表示应用x仍然有count[x]条未读消息。
2. maxPos[x]表示应用x最后一个消息是消息队列的第maxPos[x]条
3. invalid[x]表示应用x在invalid[x]之前的所有的消息已经已读。
4. a[i]表示第i条信息属于应用a[i]
5. removedBefore表示removedBefore之前的所有消息都已读。
6. top表示消息总数

太水了，懒得解释直接贴代码

        int n = in.nextInt();
        int q = in.nextInt();

        int removedBefore = 0, top = 0;
        int[] a = new int[q];
        int[] counts = new int[n], maxPos = new int[n], invalid = new int[n];
        for (int i = 0; i < n; i++) {
            invalid[i] = -1;
        }

        int sum = 0;
        for (int cas = 0; cas < q; cas++) {
            int x = in.nextInt();
            int y = in.nextInt();
            if (x == 1) {
                a[top] = y - 1;
                maxPos[y - 1] = top;
                counts[y - 1]++;
                top++;
                sum++;
            } else if (x == 2) {
                sum -= counts[y - 1];
                counts[y - 1] = 0;
                invalid[y - 1] = maxPos[y - 1];
            } else if (x == 3 && y > removedBefore) {
                for (int i = removedBefore; i < y; i++) {
                    if (i > invalid[a[i]]) {
                        counts[a[i]]--;
                        sum--;
                    }
                }

                removedBefore = y;
            }
            out.println(sum);
        }