1784: Camellia的难题
Time Limit: 2 Sec Memory Limit: 128 MB Submit: 67 Solved: 14
SubmitStatusWeb 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 8 1 20 1 15 4 20 5 2 15 5 3 5
Sample Output
1 2 1 0
题解：这个题就是给一系列操作，其中4和5是询问。。。
暴力，以前一直用memset，想怎么用就怎么用，谁知道这次就挂挂了，原来memset很慢的，运行时间是sizeof(dt)；这次的时间就是n*sizeof(dt)所以会超时，所以，想着用一个数组保存不是-1的数，当操作3的时候只需要将不是-1的数改成-1就可以了。。。刚开始还用树状数组真是多此一举，那样更慢了。。。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
typedef long long LL;
const int MAXN=1e7+;
int dt[MAXN],v[MAXN];
/*int lowbit(int x){return x&(-x);}
void update(int x,int y){
while(x<MAXN){
tree[x]+=y;
x+=lowbit(x);
}
}
int Q(int x){
int sum=0;
while(x>0){
sum+=tree[x];
x-=lowbit(x);
}
return sum;
}*/
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
mem(dt,-);
int flot=,ans=;
int gg,x,cc=;
while(n--){
flot++;
scanf("%d",&gg);
if(gg==){
scanf("%d",&x);
if(dt[x]==-)ans++;
dt[x]=flot;
v[cc++]=x;
continue;
}
if(gg==){
scanf("%d",&x);
if(dt[x]!=-)ans--;
dt[x]=-;
continue;
}
if(gg==){
for(int kk=;kk<cc;kk++)dt[v[kk]]=-;
cc=;
ans=;
continue;
}
if(gg==){
scanf("%d",&x);
printf("%d\n",dt[x]);
continue;
}
if(gg==){
printf("%d\n",ans);
continue;
}
}
}
return ;
}