HDU3333(线段树/数状数组+hash)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3333

 

题意:数轴上的区间和问题,有一些变化就是要求的是不同元素的和,线段树or数状数组可以解决.

 

 

刚开始时竟然给线段树的每人结点维护了一个set 来标记是否有重复,那个复杂度弄的比暴力都高了吧,汗一个~

 

后来看了下别人的思路,采用离线操作,对Q所要求的区间以右端点递增排序,从左至右插入新的元素,如果该元素已经插入了线段树中,就删掉旧位置的,在新位置插入该元素,并对以该元素位置为右端点的区间进行查询求和,即为结果.

 

记录元素是否已插入线段树可用离散化+二分来实现,也可用hash来记录.这里用的是hash表.

 

首先用线段树写了,可是一直RE的很悲状,后来才发现ans[]数组竟然开小了,这鬼~

 

数状数组实现很简单,甚至效率也高了线段树很多.

 

线段树:

#include<stdio.h>#include<string.h>#include<stdlib.h>#define M 30007#define N 100048#define L(x) (x<<1)#define R(x) ((x<<1)|1)#define Mid(x,y) ((x+y)>>1)typedef struct{int lt,rt;__int64 sum;}SegT;typedef struct talHash{int ix,v;talHash *next;}HashN;typedef struct{int r,l,ix;}Pair;SegT tr[M*4];HashN *hash[M];HashN MEM[M];Pair pair[N];int a[M],e;__int64 ans[N],anst;int Cmp(const void *a,const void *b){return *(int *)a-*(int *)b;}int Key(int value){value+=value;while(value>=M) value-=M;return value;}int AtHash(int value){HashN *cur;for(cur=hash[Key(value)];cur;cur=cur->next)if(cur->v==value) break;return cur?cur->ix:0;}void HashInsert(int value,int ix){HashN *cur=&MEM[e++];cur->ix=ix;cur->v=value;cur->next=hash[Key(value)];hash[Key(value)]=cur;}void Create(int ix,int l,int r){tr[ix].lt=l;tr[ix].rt=r;tr[ix].sum=0;if(l==r) return ;int mid=Mid(l,r);Create(L(ix),l,mid);Create(R(ix),mid+1,r);}void Updata(int ix,int pos,int delta){int mid;if(tr[ix].lt==tr[ix].rt){tr[ix].sum+=delta;return ;}mid=Mid(tr[ix].lt,tr[ix].rt);if(pos<=mid)Updata(L(ix),pos,delta);else Updata(R(ix),pos,delta);tr[ix].sum=tr[L(ix)].sum+tr[R(ix)].sum;}void Query(int ix,int l,int r){int mid;if(tr[ix].lt==l&&tr[ix].rt==r){ anst+=tr[ix].sum;return ;}mid=Mid(tr[ix].lt,tr[ix].rt);if(r<=mid) Query(L(ix),l,r);else if(l>mid) Query(R(ix),l,r);else{Query(L(ix),l,mid);Query(R(ix),mid+1,r);}}int main(){int n,t,i,j,q;int preix;scanf("%d",&t);while(t--){memset(hash,NULL,sizeof(hash));scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",a+i);scanf("%d",&q);for(i=0;i<q;i++){scanf("%d%d",&pair[i].l,&pair[i].r);pair[i].ix=i;}qsort(pair,q,sizeof(pair[0]),Cmp);Create(1,1,n);for(i=1,j=e=0;i<=n;i++){preix=AtHash(a[i]);if(preix)Updata(1,preix,-a[i]);HashInsert(a[i],i);Updata(1,i,a[i]);for(;j<q&&pair[j].r==i;j++){anst=0;Query(1,pair[j].l,pair[j].r);ans[pair[j].ix]=anst;}}for(j=0;j<q;j++)printf("%I64d/n",ans[j]);}return 0;} 

数状数组:

#include<stdio.h>#include<string.h>#include<stdlib.h>#define M 30007#define N 100048#define LowBit(x) (x&(-x))typedef struct talHash{int ix,v;talHash *next;}HashN;typedef struct{int r,l,ix;}Pair;HashN *hash[M];HashN MEM[M];Pair pair[N];__int64 C[M];int a[M],e;__int64 ans[N],anst;int Cmp(const void *a,const void *b){return *(int *)a-*(int *)b;}int Key(int value){value+=value;while(value>=M) value-=M;return value;}int AtHash(int value){HashN *cur;for(cur=hash[Key(value)];cur;cur=cur->next)if(cur->v==value) break;return cur?cur->ix:0;}void HashInsert(int value,int ix){HashN *cur=&MEM[e++];cur->ix=ix;cur->v=value;cur->next=hash[Key(value)];hash[Key(value)]=cur;}void Insert(int ix,int delta){for(;ix<M;ix+=LowBit(ix)) C[ix]+=delta;}__int64 Sum(int ix){__int64 ret=0;for(;ix>0;ix-=LowBit(ix)) ret+=C[ix];return ret;}int main(){int n,t,i,j,q;int preix;scanf("%d",&t);while(t--){memset(hash,NULL,sizeof(hash));scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",a+i);scanf("%d",&q);for(i=0;i<q;i++){scanf("%d%d",&pair[i].l,&pair[i].r);pair[i].ix=i;}qsort(pair,q,sizeof(pair[0]),Cmp);memset(C,0,sizeof(C));for(i=1,j=e=0;i<=n;i++){preix=AtHash(a[i]);if(preix)Insert(preix,-a[i]);HashInsert(a[i],i);Insert(i,a[i]);for(;j<q&&pair[j].r==i;j++)ans[pair[j].ix]=Sum(pair[j].r)-Sum(pair[j].l-1);}for(j=0;j<q;j++)printf("%I64d/n",ans[j]);}return 0;}