第四届山东省赛 J Boring Counting [主席树]【数据结构】
题目链接 http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2054 Description Input For each case,the first line contains two numbers N and M (1 <= N,M <= 50000),the size of sequence P,the number of queries. The second line contains N numbers Pi(1 <= Pi <= 10^9),the number sequence P. Then there are M lines,each line contains four number L,R,A,B(1 <= L,R <= n,1 <= A,B <= 10^9) Output Sample Input Sample Output —————————————————————————————————————————— 解题思路: 其实就是一个简单的主席树入门,奈何练习赛的时候刚学主席树不到2天,还没理解主席树.于是GG了 其实仔细想想啊,其实 和 SPOJ DQUERY 一样,而且更简单一点, 只需要离散化后,一次向树上更新即可, 但要注意查询的时候, 附本题代码 #include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
/************************************************/
const int N = 5e4+7;
int a[N],b[N],sz;
int rt[N],ls[N*40],rs[N*40],sum[N*40],tot;
void build(int &rt,int l,int r){
rt=++tot;
sum[rt]=0;
if(l>=r)return;
int m=((r-l)>>1)+l;
build(ls[rt],l,m);
build(rs[rt],m+1,r);
}
void update(int &rt,int r,int last,int pos){
rt=++tot;
ls[rt]=ls[last];
rs[rt]=rs[last];
sum[rt]=sum[last]+1;
if(l>=r)return;
int m=((r-l)>>1)+l;
if(pos<=m) update(ls[rt],m,ls[last],pos);
else update(rs[rt],r,rs[last],pos);
}
int query(int rt,int L,int R){
if(L>R)return 0;
if(L<=l&&r<=R)return sum[rt]-sum[last];
int m=((r-l)>>1)+l;
int ans=0;
if(L<=m) ans+=query(ls[rt],L,R);
if(R> m) ans+=query(rs[rt],R);
return ans;
}
int lb(int x){
return lower_bound(b+1,b+sz+1,x)-b;
}
map<int,int>mmp;
int main(){
int _ = 1,kcase = 0,flag;
scanf("%d",&_);
while(_--){
tot=0;mmp.clear();
int n=read(),m=read();
for(int i=1;i<=n;i++) b[i]=a[i]=read(),mmp[a[i]]=1;
sort(b+1,b+n+1);
sz = unique(b+1,b+n+1)-(b+1);
// printf("sz = %dn",sz);
// for(int i=1;i<=sz;i++) printf("b[%d]=%d ",i,b[i]);puts("");
build(rt[0],1,sz);
for(int i=1;i<=n;i++)a[i]=lb(a[i]);
for(int i=1;i<=n;i++)update(rt[i],sz,rt[i-1],a[i]);
// printf("%dn",lb(0));
printf("Case #%d:n",++kcase);
while(m--){
l=read(),r=read(),L=read(),R=read();
if(L>R){puts("0");continue; }
flag=0;
if(!mmp[R])flag=1;
if(R<b[1]) R=-1; else R = lb(R)-flag;
if(L>b[sz])L=1e9+77;else L = lb(L);
// printf("%d %dn",R);
printf("%dn",query(rt[r],rt[l-1],R));
}
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |