2 条题解
-
0
树状数组打错了还有救吗?
#include<bits/stdc++.h> using namespace std; #define int long long const int N=2e5+10; struct BIT { int c[N],n; void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;} int get(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;} }tr; int a[N],b[N],blen,ans[N],n,m,B,sum,len; struct node{int l,r,id;}q[N]; bool cmp(node n1,node n2){return n1.l/B!=n2.l/B?n1.l<n2.l:(n1.l/B)&1?n1.r<n2.r:n1.r>n2.r;} void add(int x,int op) { int s=op?tr.get(x-1):len-tr.get(x); len++,sum+=s;tr.add(x,1); } void del(int x,int op) { int s=op?tr.get(x-1):len-tr.get(x); len--,sum-=s;tr.add(x,-1); } signed main() { cin>>n>>m;B=sqrt(n); for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i]; sort(b+1,b+n+1);blen=unique(b+1,b+n+1)-b-1;tr.n=blen; for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+blen+1,a[i])-b; for(int i=1;i<=m;i++)cin>>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1,cmp); for(int i=1,l=1,r=0;i<=m;i++) { while(l>q[i].l)add(a[--l],1); while(r<q[i].r)add(a[++r],0); while(l<q[i].l)del(a[l++],1); while(r>q[i].r)del(a[r--],0); ans[q[i].id]=sum; } for(int i=1;i<=m;i++)cout<<ans[i]<<'\n'; return 0; }
信息
- ID
- 483
- 时间
- 10000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 7
- 已通过
- 3
- 上传者