ACM-ICPC 2018 徐州賽區網絡預賽 I. query 樹狀數組

I. query

題目鏈接：

Problem Description

Given a permutation \(p\) of length \(n\), you are asked to answer \(m\) queries, each query can be represented as a pair \((l ,r )\), you need to find the number of pair \((i ,j)\) such that \(l \le i < j \le r\) and \(\min(p_i,p_j) = \gcd(p_i,p_j )\).

Input

There is two integers \(n(1 \le n \le 10^5)\), \(m(1 \le m \le 10^5)\) in the first line, denoting the length of \(p\) and the number of queries.

In the second line, there is a permutation of length \(n\), denoting the given permutation \(p\). It is guaranteed that \(p\) is a permutation of length \(n\).

For the next \(m\) lines, each line contains two integer \(l_i\) and \(r_i(1 \le l_i \le r_i \le n)\), denoting each query.

Output

For each query, print a single line containing only one integer which denotes the number of pair \((i,j)\).

樣例輸入

3 2
1 2 3
1 3
2 3

樣例輸出

2
0

題意

給你一個序列,求很多段子區間\((l ,r )\)滿足\(l \le i < j \le r\) and \(\min(p_i,p_j) = \gcd(p_i,p_j )\) 的個數。

題解

１．轉化一下就是求一個區間有多少對滿足一個是另一個的倍數。

２．我們會發現這個是一個排列,每個數x的倍數個數為\(\frac{n}{x}\),那么所有的倍數個數即為\(\sum_{i=1}^{n}\frac{n}{i})(\le nlog_{2}{n+1})\)

３．我們將所有倍數點對預處理出來，問題就變成了問一個區間有多少倍數點對同時存在。

４．是不是很熟悉啦（不知道也沒關系），我來細細講解一下：

• 先將區間按右端點從小到大排序，保證右端點單調遞增
• 那么起作用的就是左端點，這是我們碰到一個點就將它左邊的所有是它約數以及倍數的位置權值全部+1,這樣如果左邊這個點在區間里，右端點必然也在區間里因為右端點單調遞增。

如果真的理解了的話想想按左端點從大到小也可以做，想想怎么做？

其實這題是cf原題，網絡賽時我不會做，然后竟然搜到了原題(還是有極其微小的差異)，然后現學啦，哈哈哈。

cf鏈接：codeforces 301D

代碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x7f7f7f7f
#define N 100050
template<typename T>void read(T&x)
{ll k=0; char c=getchar();x=0;while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();if (c==EOF)exit(0);while(isdigit(c))x=x*10+c-'0',c=getchar();x=k?-x:x;
}
void read_char(char &c)
{while(!isalpha(c=getchar())&&c!=EOF);}
int n,m,a[N],p[N],c[N],ans[N];
vector<int>vec[N];
struct Query
{int l,r,id;bool operator <(const Query b)const{return r<b.r;}
}que[N];
void change(int x){while(x<=n)c[x]++,x+=x&-x;}
int ask(int x){int ans=0;while(x)ans+=c[x],x-=x&-x;return ans;}
void work()
{read(n); read(m);for(int i=1;i<=n;i++) read(a[i]),p[a[i]]=i;for(int i=1;i<=m;i++) read(que[i].l),read(que[i].r),que[i].id=i;for(int i=1;i<=n;i++){for(int j=a[i]+a[i];j<=n;j+=a[i])if (i<p[j])vec[p[j]].push_back(i);else vec[i].push_back(p[j]);}sort(que+1,que+m+1);int r=0;for(int i=1;i<=m;i++){for(int j=r+1;j<=que[i].r;j++)for(int k=0;k<vec[j].size();k++)change(vec[j][k]);r=que[i].r;ans[que[i].id]=ask(que[i].r)-ask(que[i].l-1);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("aa.in","r",stdin);
#endifwork();
}