（暴力记录）Camellia的难题 -- zzuli -- 1784

http://acm.zzuli.edu.cn/problem.php?id=1784

Camellia的难题

Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 119 Solved: 25

Submit Status Web Board

Description

Camellia遇到了一个问题，她无法解决所以来求助豆子，以下是豆子所理解的问题：给定1000万个点，编号1-1000万。每个点都有一个值，初始的时候均为-1，有n个操作，操作有以下五种。

1 x 代表将x点更新为i，i为第几次操作。

2 x 代表将x点更新为-1。

3 代表把所有的点变为-1。

4 x 查询x点的值。

5 查询1000万个点里有多少个点不是-1。

亲爱的同学，你能帮助他们解决这个问题么？

Input

首先输入一个t(t<10)代表t组数组，接下来每组数据首先输入一个n(n<100万)代表n次操作，接下来n行每行一种操作。

Output

对于4、5操作来言，输出它们的答案。

Sample Input

1 20

1 15

4 20

2 15

Sample Output

只需要在改变值的时候记录一下所改变的值，存一下，在3的时候只需要将改变过的值再改变回来就OK了，做题做多了都做傻了，这样的题比赛的时候居然都想不到

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

using namespace std;

const int N = ;

int v[N], pre[N];

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int n, i, sum=, k=, x, p;

        scanf("%d", &n);

        memset(v, -, sizeof(v));

        for(i=; i<=n; i++)

        {

            scanf("%d", &p);

            if(p==)

            {

                scanf("%d", &x);

                if(v[x]==-) sum++;

                v[x] = i;

                pre[k++] = x;

            }

            else if(p==)

            {

                scanf("%d", &x);

                if(v[x]!=-) sum--;

                v[x] = -;

            }

            else if(p==)

            {

                for(int j=; j<k; j++) v[pre[j]]=-;

                sum = ;

                k=;

            }

            else if(p==)

            {

                scanf("%d", &x);

                printf("%d\n", v[x]);

            }

            else

            {

                printf("%d\n", sum);

            }

        }

    }

    return ;

}

Camellia