点击刷新
楼兰图腾
题目
https://ac.nowcoder.com/acm/contest/1032/A
题解
涉及到的是树状数组找出逆序对的知识，步骤如下：
①倒叙扫描序列，wright记录右侧有多少小于他，vright记录右侧有多少大于它的数
②正序扫描序列，求出每个a[i]左侧有几个数比他小，乘上wright[i]，累加后就是^的个数；求出左侧有多少大于它的，乘上vright[i]，累加后就是v的个数
代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+10; int c[N]; int a[N]; int n; int vright[N]; int wright[N]; int lowbit(int x) { return x&-x; } int ask(int x) { int ans=0; for(;x;x-=lowbit(x)) ans+=c[x]; return ans; } void add(int x,int y) { for(;x<N;x+=lowbit(x)) c[x]+=y; } int main() { int i,j; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; } ll vans=0; ll wans=0; for(i=n;i;i--) { wright[i]=ask(a[i]-1);//右侧有多少小于他的 vright[i]=ask(n)-ask(a[i]);//右侧有多少大于他的 add(a[i],1); } memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { wans+=(ll)wright[i]*ask(a[i]-1);//左侧有多少小于的 vans+=(ll)vright[i]*(ask(n)-ask(a[i]));//左侧有多少大于的 add(a[i],1); } cout<<vans<<" "<<wans<<endl; return 0; }
A Tiny Problem with intergers
题目
https://ac.nowcoder.com/acm/contest/1032/B
题解
用树状数组做区间增加，而他支持“单点增加”和“单点查询”，如何做区间增加呢？
用差分的思想来做：例如C l r d
1.把b[l]加上d
2.把b[r+1]-d;
就可以做到只增加[l,r]，单点求和即所求：a[x]+ask(x)
代码
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],b[N]; int lowbit(int x) { return x&-x; } int ask(int x) { int ans=0; for(;x;x-=lowbit(x)) { ans+=b[x]; } return ans; } void add(int x,int y) { for(;x<N;x+=lowbit(x)) b[x]+=y; } int main() { int i,j,n,q; cin>>n>>q; for(i=1;i<=n;i++) cin>>a[i]; while(q--) { char c; int l,r,d; cin>>c; if(c=='C') { cin>>l>>r>>d; add(l,d); add(r+1,-d); } else { cin>>l; cout<<a[l]+ask(l)<<endl; } } return 0; }
A Simple Problem with Integers
题目
https://ac.nowcoder.com/acm/contest/1032/C
题解
此题用树状数组求区间和，这下可有点子难度：
代码
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],n,m; typedef long long ll; ll c[2][N],sum[N]; int lowbit(int x) { return x&-x; } ll ask(int k,int x) { ll ans=0; for(;x;x-=lowbit(x)) ans+=c[k][x]; return ans; } void add(int k,int x,int y) { for(;x<=n;x+=lowbit(x)) c[k][x]+=y; } int main() { int i,j; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a[i]; sum[i]=sum[i-1]+a[i]; } while(m--) { char s; int a,b,c; cin>>s; if(s=='C') { cin>>a>>b>>c; add(0,a,c); add(0,b+1,-c); add(1,a,a*c); add(1,b+1,-(b+1)*c); } else { cin>>a>>b; ll ans=sum[b]+(b+1)*ask(0,b)-ask(1,b); ans-=sum[a-1]+a*ask(0,a-1)-ask(1,a-1); cout<<ans<<endl; } } return 0; }
Lost Cows
题目
https://ac.nowcoder.com/acm/contest/1032/D
题解
建立一个全1数组b，然后从n到1倒叙遍历每个Ai，对每个Ai执行一下两个操作：
1.查询b数组中第Ai+1个1在什么位置，只个位置就是第i头牛的身高Hi
2.把b[Hi]减1（从1到0）
用树状数组维护前缀和，每次查询二分时的答案，通过ask(mid)即可得到前面有多少个1，与t比较大小，即可确定二分的边界（注意：要找前缀和中第一个符合要求的下标）
代码
#include<bits/stdc++.h> using namespace std; const int N=8e4+10; int a[N]; int b[N]; int n; int lowbit(int x) { return x&-x; } void add(int x,int y) { for(;x<=n;x+=lowbit(x)) b[x]+=y; } int ask(int x) { int ans=0; for(;x;x-=lowbit(x)) ans+=b[x]; return ans; } int main() { int i,j; cin>>n; for(i=1;i<=n-1;i++) { cin>>a[i]; add(i,1); } add(n,1); int ans[N]; int len=n; for(i=n-1;i>=0;i--) { int t=a[i]+1; int l=1,r=n; int mid; while(l<r) { mid=(l+r)/2; int res=ask(mid); if(res<t) l=mid+1; else r=mid; } ans[len--]=l; add(l,-1); } for(i=1;i<=n;i++) cout<<ans[i]<<endl; return 0; }
© 著作权归作者所有
举报
发表评论
0/200
