【題目描述】
CodeForces - 641ELittle Artem and Time Machine
【題目分析】
題目的意思大概是有三種操作
1.在時間t加入一個數字x
2.在時間t刪除一個數字x
3.詢問在時間t集合里面x的個數
雖然題目描述很簡單，但是t和x的范圍都是109，我一開始想到的是主席樹，因為之前做過一道類似的題目HDU - 4348To the moon——主席樹+區間修改，然后我就開始興沖沖的開始離散化，然后正準備寫主席樹的維護的時候才發現因為這個時間是跳躍的，所以我們很不容易用到之前的數據，也不容易修改，所以卡住了。
在網上找其他大佬的博客發現用map以后就不用進行離散化了，而且代碼量非常少，仔細一看發現他用的是樹狀數組，大概的思想就是對于每一個x都用一個樹狀數組維護時間區間，每次修改都在時間軸上進行修改，每次查詢也只是針對這個數字在時間軸上進行查詢。我覺得對每一個數字用一個線段樹進行維護應該也可以做，就是得把每個數字的修改的時間進行離散化，然后再分別建樹可能復雜度會有點高，但應該也是可做的吧，反正我是懶得那樣做了，這個map+樹狀數組真的好爽啊，什么離散化什么的完全不需要啊。
【AC代碼】
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;const int MAXN=100005;
const int INF=1e9+5;
map<int,int> mp[MAXN];
map<int,int> vis;
int cnt=0;int lowbit(int t)
{return t&(-t);
}void update(int pos,int t,int val)
{while(t<INF){mp[pos][t]+=val;t+=lowbit(t);}
}int sum(int pos,int t)
{int ans=0;while(t){ans+=mp[pos][t];t-=lowbit(t);}return ans;
}int main()
{int n,cmd,t,x;while(~scanf("%d",&n)){cnt=0;vis.clear();while(n--){scanf("%d%d%d",&cmd,&t,&x);if(cmd==1){if(!vis[x]){vis[x]=++cnt; mp[cnt].clear();}update(vis[x],t,1);}else if(cmd==2){update(vis[x],t,-1);}else if(cmd==3){printf("%d\n",sum(vis[x],t));}}}return 0;
}
