程序员人生 网站导航

CodeForces 301D(树状数组)

栏目:php教程时间:2015-06-27 08:32:37

题目链接:codeforces 301D

题意分析:
给你n , m两个数,1?≤?n,?m?≤?2e5,n代表n个不同数字,且这些数字都在区间[ 1 , n ]之间,这就说明1~n每一个数出现1次。m代表m次查询,查询格式为两个整数x , y,问你区间[ x , y ]之间有多少对数a , b满足a%b==0。

解题思路:
考察点是区间的频繁访问,马上想到线段树和树状数组,线段树太难写了没斟酌过,就说说树状数组的思路吧。
1)离线处理:把所有的插叙全部读进来再按特定顺序处理。为了让树状数组求的和确确切实的是属于这个区间的,没有别的区间的干扰,我们按区间的左侧界给区间排1次序,左侧界大的先处理:

bool cmp(query a,query b){ return a.x>b.x; }

2)预处理:找到跟ai的所有可整除的数,根据索引大小保存在1个vector里面:

for(int i=1;i<=n;i++) { for(int j=a[i];j<=n;j+=a[i]) { if(p[j]>=i) vec[i].push_back(p[j]); else vec[p[j]].push_back(i); } }

3)树状数组处理:有1个虚拟数组cnt
首先有1个maxx变量,来记录当前已处理到哪了(从右到左处理,初始值为n+1),来到达避免重复计算的效果。把所有该加上的值先加上,在求和;如果之前已加过了,不用加了,这里就需要maxx来判断了:

int maxx=n+1; for(int i=0;i<m;i++) { int x=q[i].x,y=q[i].y,len; for(int j=x;j<maxx;j++) { len=vec[j].size(); for(int k=0;k<len;k++) add(vec[j][k],1); } ans[q[i].id]=sum(y); //求和 maxx=x; }

AC代码:

#include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n,m,a[200005],p[200005],bit[200005],ans[200005]; vector<int> vec[200005]; struct query{ int id,x,y; }q[200005]; bool cmp(query a,query b){ return a.x>b.x; } int lowbit(int num){ return num&(-num); } int sum(int index) { int res=0; for(int i=index;i>0;i-=lowbit(i)) res+=bit[i]; return res; } void add(int index,int delta){ for(int i=index;i<=n;i+=lowbit(i)) bit[i]+=delta; } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); p[a[i]]=i; } for(int i=1;i<=n;i++) { for(int j=a[i];j<=n;j+=a[i]) { if(p[j]>=i) vec[i].push_back(p[j]); else vec[p[j]].push_back(i); } } for(int i=0;i<m;i++) { scanf("%d %d",&q[i].x,&q[i].y); if(q[i].y<q[i].x) swap(q[i].x,q[i].y); q[i].id=i; } sort(q,q+m,cmp); int maxx=n+1; for(int i=0;i<m;i++) { int x=q[i].x,y=q[i].y,len; for(int j=x;j<maxx;j++) { len=vec[j].size(); for(int k=0;k<len;k++) add(vec[j][k],1); } ans[q[i].id]=sum(y); maxx=x; } for(int i=0;i<m;i++) printf("%d ",ans[i]); return 0; }

总结:
1、离线处理+树状数组
2、注意查询的排序方式

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐