題目鏈接：codeforces 301D
題意分析：
給你n , m兩個(gè)數(shù)，1?≤?n,?m?≤?2e5，n代表n個(gè)不同數(shù)字，且這些數(shù)字都在區(qū)間[ 1 , n ]之間，這就說明1~n每一個(gè)數(shù)出現(xiàn)1次。m代表m次查詢，查詢格式為兩個(gè)整數(shù)x , y，問你區(qū)間[ x , y ]之間有多少對(duì)數(shù)a , b滿足a%b==0。
解題思路：
考察點(diǎn)是區(qū)間的頻繁訪問，馬上想到線段樹和樹狀數(shù)組，線段樹太難寫了沒斟酌過，就說說樹狀數(shù)組的思路吧。
1）離線處理：把所有的插敘全部讀進(jìn)來再按特定順序處理。為了讓樹狀數(shù)組求的和確確切實(shí)的是屬于這個(gè)區(qū)間的，沒有別的區(qū)間的干擾，我們按區(qū)間的左側(cè)界給區(qū)間排1次序，左側(cè)界大的先處理：
bool cmp(query a,query b){
return a.x>b.x;
}2）預(yù)處理：找到跟ai的所有可整除的數(shù)，根據(jù)索引大小保存在1個(gè)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）樹狀數(shù)組處理：有1個(gè)虛擬數(shù)組cnt
首先有1個(gè)maxx變量，來記錄當(dāng)前已處理到哪了（從右到左處理，初始值為n+1），來到達(dá)避免重復(fù)計(jì)算的效果。把所有該加上的值先加上，在求和；如果之前已加過了，不用加了，這里就需要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;
}總結(jié)：
1、離線處理+樹狀數(shù)組
2、注意查詢的排序方式
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
