首页 > 代码库 > BZOJ 4627 回转寿司
BZOJ 4627 回转寿司
学用vim写的第一道题。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100500 using namespace std; long long n,l,r,a[maxn],b[maxn],hash[maxn],tot=0,ans=0; long long ls[maxn*40],rs[maxn*40],sum[maxn*40],root[maxn],cnt=0; void build(long long last,long long &now,long long left,long long right,long long pos) { now=++tot;sum[now]=sum[last]+1; if (left==right) return; long long mid=(left+right)>>1; ls[now]=ls[last];rs[now]=rs[last]; if (pos<=mid) build(ls[last],ls[now],left,mid,pos); else build(rs[last],rs[now],mid+1,right,pos); sum[now]=sum[ls[now]]+sum[rs[now]]; } long long ask(long long last,long long now,long long left,long long right,long long l,long long r) { if ((left==l) && (right==r)) return sum[now]-sum[last]; long long mid=(left+right)>>1; if (r<=mid) return ask(ls[last],ls[now],left,mid,l,r); else if (l>=mid+1) return ask(rs[last],rs[now],mid+1,right,l,r); else return ask(ls[last],ls[now],left,mid,l,mid)+ask(rs[last],rs[now],mid+1,right,mid+1,r); } int main() { scanf("%lld%lld%lld",&n,&l,&r); for (long long i=1;i<=n;i++) { scanf("%lld",&a[i]); a[i]+=a[i-1];b[i]=a[i];hash[++cnt]=a[i]; } sort(hash+1,hash+cnt+1);cnt=unique(hash+1,hash+cnt+1)-hash-1; for (long long i=1;i<=n;i++) a[i]=lower_bound(hash+1,hash+cnt+1,a[i])-hash; for (long long i=1;i<=n;i++) build(root[i-1],root[i],1,n,a[i]); for (long long i=1;i<=n;i++) { long long lb=b[i-1]+l,rb=b[i-1]+r; lb=lower_bound(hash+1,hash+cnt+1,lb)-hash; rb=lower_bound(hash+1,hash+cnt+1,rb)-hash; if (hash[rb]!=b[i-1]+r) rb--; if (lb>rb) continue; ans+=ask(root[i-1],root[n],1,n,lb,rb); } printf("%lld\n",ans); return 0; }
BZOJ 4627 回转寿司
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。