【題目描述】
CodeForces - 641ELittle Artem and Time Machine
【題目分析】
題目的意思大概是有三種操作
1.在時間t加入一個數字x
2.在時間t刪除一個數字x
3.詢問在時間t集合里面x的個數

雖然題目描述很簡單，但是t和x的范圍都是10⁹，我一開始想到的是主席樹，因為之前做過一道類似的題目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; }

總結

以上是生活随笔為你收集整理的CodeForces - 641ELittle Artem and Time Machine——map+树状数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。