首页 > 代码库 > hdu 3333 树状数组+离线处理
hdu 3333 树状数组+离线处理
http://acm.hdu.edu.cn/showproblem.php?pid=3333
不错的题,想了很久不知道怎么处理,而且答案没看懂,然后找个例子模拟下别人的代码马上懂了---以后看不懂的话就拿个例子模拟下别人的代码
举个例子:1 3 3 5 3 5
查询
a, 2 4
b, 2 5
最初是这么想的:对于a查询,倘若把第二个数第三个数变成1个3,那么到b查询,又出现了两个3,再做处理似乎还是O(n),而且如果先出现2,5查询,后出现2,4查询,那么还需要把删除的数补回来.....o(╯□╰)o,然后就陷入迷茫啊.......
题解:
1、把查询按区间右端点由小到大排列,就避免了“需要把删除的数补回来”,如上面的例子,a查询的时候删除的3,在b查询的时候仍需要删除,但是如果先b查询后a查询,b查询需要删除第二个数第三个数,a查询需要把第三个数补回来....
2、每查询到一个区间,确保以右端点为结束为止的前缀没有重复的数
具体看代码-----拿例子模拟下,,回头我一定重写一遍
#include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> #include <cmath> #include <map> #include <set> #include <queue> using namespace std; #define ls(rt) rt*2 #define rs(rt) rt*2+1 #define ll long long #define ull unsigned long long #define rep(i,s,e) for(int i=s;i<e;i++) #define repe(i,s,e) for(int i=s;i<=e;i++) #define CL(a,b) memset(a,b,sizeof(a)) #define IN(s) freopen(s,"r",stdin) #define OUT(s) freopen(s,"w",stdout) const int MAXN = 50000+100; struct Query { int l,r; int id; bool operator < (const Query &c)const { return r<c.r; } }q[100000 + 100]; ll c[MAXN],ans[100000 + 100]; ll num[MAXN],bi[MAXN]; int last[MAXN]; int N; inline int lowbit(int i){return i&(-i);} void add(int x, int v) { while(x<=N) { c[x]+=v; x+=lowbit(x); } } ll sum(int i) { ll ret=0; while(i>0) { ret+=c[i]; i-=lowbit(i); } return ret; } int main() { //IN("hdu3333.txt"); int ncase,Q; scanf("%d",&ncase); while(ncase--) { CL(c,0);CL(last,0); scanf("%d",&N); for(int i=1;i<=N;i++) { scanf("%I64d",&num[i]); bi[i]=num[i]; } scanf("%d",&Q); for(int i=1;i<=Q;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+1+Q); sort(bi+1,bi+1+N); int qu=1; for(int i=1;i<=N;i++) { int pos=lower_bound(bi+1,bi+1+N,num[i])-bi; if(!last[pos]) { add(i,num[i]); last[pos]=i; } else { add(last[pos],-num[i]); add(i,num[i]); last[pos]=i; } while(q[qu].r == i && qu<=Q) { ans[q[qu].id]=sum(i)-sum(q[qu].l-1); qu++; } } for(int i=1;i<=Q;i++) printf("%I64d\n",ans[i]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。