运维开发网
广告位招商联系QQ:123077622
 
广告位招商联系QQ:123077622

【树状数组】2019徐州网络赛 query

运维开发网 https://www.qedev.com 2020-07-21 08:57 出处:网络 作者:运维开发网整理
(2)首先成倍数对的数量是nlogn级别的,考虑每一对【xL,xR】(下标的位置,xL < xR)会对那些询问做出贡献,如果qL <= xL && qR >= xR,那么这一对就会对询问【qL,qR】贡献1;现在把它们看成平面上的点,那么对于每一个询问【qL,qR】,就相当于计算这个点右下角有多少个点,这个就可以通过排序+树状数组解决————————————————大致就是,我们可以先处理出区间内

(2)首先成倍数对的数量是nlogn级别的,考虑每一对【xL,xR】(下标的位置,xL < xR)会对那些询问做出贡献,如果qL <= xL && qR >= xR,那么这一对就会对询问【qL,qR】贡献1;现在把它们看成平面上的点,那么对于每一个询问【qL,qR】,就相当于计算这个点右下角有多少个点,这个就可以通过排序+树状数组解决————————————————大致就是,我们可以先处理出区间内每一对(i,j)倍数对,然后按i从大到小排序排序介绍:按i排序,从大到小,再让添加在前,询问在后,例如,我们区间(1,2,4,6)然后倍数对就有(1 2,1 3 ,1 4,2 4)我们让2 4排前边,这样就可以一个个当成点来使用树状数组,这样保证先询问到就是刚加进去的#include <bits/stdc++.h> using namespace std;typedef long long LL;const int maxn = 1e5+15;const int maxm = 2e6+26;int n,m,a[maxn],pos[maxn];struct node{ //f标记是倍数对还是询问,id标识询问的编号 int f,l,r,id;}p[maxm];bool cmp(node a,node b){ if(a.l == b.l) return a.f < b.f; return a.l > b.l;}inline int lowbit(int x){ return x & (-x);}LL tr[maxn],ans[maxn];void updata(int x,int val){ while(x <= n){tr[x] += val; x += lowbit(x);}}LL query(int x){ LL res = 0; while(x){res += tr[x]; x -= lowbit(x);} return res;}int main(){ scanf("%d %d",&n,&m); int cnt = m; for(int i = 1;i <= n; ++i) scanf("%d",a+i),pos[a[i]] = i; for(int i = 0;i < m; ++i) scanf("%d %d",&p[i].l,&p[i].r),p[i].f=1,p[i].id=i; for(int i = 1;i <= n; ++i){ for(int j = a[i]*2;j <= n; j+=a[i]){ if(pos[a[i]] < pos[j]) p[cnt++] = (node){0,pos[a[i]],pos[j],0}; else p[cnt++] = (node){0,pos[j],pos[a[i]],0}; } } sort(p,p+cnt,cmp); for(int i = 0;i < cnt; ++i){ if(p[i].f == 1) ans[p[i].id] = query(p[i].r); else updata(p[i].r,1); } for(int i = 0;i < m; ++i) cout << ans[i] << ‘\n‘; return 0;}

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消