題目鏈接：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、注意查詢的排序方式
上一篇 linux應用開發-進程控制理論
下一篇 單元測試之如何測試模板類
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
