首页 > 代码库 > HDU4417 (Super Mario)
HDU4417 (Super Mario)
题目链接:传送门
题目大意:一个大小为 n 的数组,m组询问,每组询问[x,y]内<=v的数的数量。
题目思路:主席树(注意询问时数组下标越界问题)
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <algorithm> 6 #include <cstring> 7 #include <stack> 8 #include <cctype> 9 #include <queue>10 #include <string>11 #include <vector>12 #include <set>13 #include <map>14 #include <climits>15 #define lson rt<<1,l,mid16 #define rson rt<<1|1,mid+1,r17 #define fi first18 #define se second19 #define ping(x,y) ((x-y)*(x-y))20 #define mst(x,y) memset(x,y,sizeof(x))21 #define mcp(x,y) memcpy(x,y,sizeof(y))22 using namespace std;23 #define gamma 0.577215664901532860606512024 #define MOD 100000000725 #define inf 0x3f3f3f3f26 #define N 10000527 #define maxn 3001028 typedef pair<int,int> PII;29 typedef long long LL;30 LL read(){31 LL x=0,f=1;char ch=getchar();32 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}33 while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}34 return x*f;35 }36 37 int n,m,flag,L,R,sz;38 struct Seg{int l,r,v;}seg[N*25];39 int a[N],b[N],root[N];40 void init(){41 root[0]=sz=0;42 mst(seg,0);43 }44 void update(int &rot,int rt,int l,int r){45 seg[++sz]=seg[rot],rot=sz;46 ++seg[rot].v;47 if(l==r)return;48 int mid=l+r>>1;49 if(L<=mid)update(seg[rot].l,lson);50 else update(seg[rot].r,rson);51 }52 int query(int L,int R,int rt,int l,int r,int v){53 if(l==r)return seg[R].v-seg[L].v;54 int mid=l+r>>1,temp=0;55 if(v<=mid)temp+=query(seg[L].l,seg[R].l,lson,v);56 else{57 temp+=seg[seg[R].l].v-seg[seg[L].l].v;58 temp+=query(seg[L].r,seg[R].r,rson,v);59 }60 return temp;61 }62 int main(){63 int i,j,group,x,y,v,Case=0;64 group=read();65 while(group--){66 init();67 n=read(),m=read();68 for(i=1;i<=n;++i)a[i]=read(),b[i]=a[i];69 sort(b+1,b+n+1);int _n=unique(b+1,b+n+1)-b-1;70 for(i=1;i<=n;++i){71 L=lower_bound(b+1,b+_n+1,a[i])-b;72 update(root[i]=root[i-1],1,1,_n);73 }74 printf("Case %d:\n",++Case);75 while(m--){76 x=read(),y=read(),v=read();77 ++x,++y;78 L=root[x-1],R=root[y];79 v=upper_bound(b+1,b+_n+1,v)-b-1;80 if(v) printf("%d\n",query(L,R,1,1,_n,v));81 else printf("0\n");82 }83 }84 return 0;85 }
HDU4417 (Super Mario)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。