班级网站html代码,没有备案的网站,wordpress时间轴模版,手机商城软件下载【题目描述】 CodeForces - 641ELittle Artem and Time Machine 【题目分析】 题目的意思大概是有三种操作 1.在时间t加入一个数字x 2.在时间t删除一个数字x 3.询问在时间t集合里面x的个数
虽然题目描述很简单#xff0c;但是t和x的范围都是109#xff0c;我一开始想到的是主…【题目描述】 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代码】
#includecstdio
#includealgorithm
#includemap
using namespace std;const int MAXN100005;
const int INF1e95;
mapint,int mp[MAXN];
mapint,int vis;
int cnt0;int lowbit(int t)
{return t(-t);
}void update(int pos,int t,int val)
{while(tINF){mp[pos][t]val;tlowbit(t);}
}int sum(int pos,int t)
{int ans0;while(t){ansmp[pos][t];t-lowbit(t);}return ans;
}int main()
{int n,cmd,t,x;while(~scanf(%d,n)){cnt0;vis.clear();while(n--){scanf(%d%d%d,cmd,t,x);if(cmd1){if(!vis[x]){vis[x]cnt; mp[cnt].clear();}update(vis[x],t,1);}else if(cmd2){update(vis[x],t,-1);}else if(cmd3){printf(%d\n,sum(vis[x],t));}}}return 0;
}
