http://acm.hdu.edu.cn/showproblem.php?pid=5869
题意：给定一个数组，然后给出若干个询问，询问[L, R]中，有多少个子数组的gcd是不同的。
就是[L, R]中不同区间的gcd值，有多少个是不同的。
给个样例
3 3
7 7 7
1 2
1 3
3 3
数学背景：
一个数字和若N个数字不断GCD，其结果只有loga[i]种，为什么呢？因为可以把a[i]质因数分解，其数目最多是loga[i]个数字相乘。（最小的数字是2，那么loga[i]个2相乘也爆了a[i]了）
所以，考虑以a[i]为结尾的序列，有多少个不同的gcd，可以记录下。
比如样例。括号里的依次是gcd值和a[i]这个数字最早与那个位置gcd，其值是val、
1、 3、 4、 6、 9
(1, 1) (3, 2) (4, 3) (6, 4) (9, 5)
(1, 1) (1, 2) (2, 3) (3, 4)
(1, 2) (1, 3) //9这个数字在[3, 5]中一路gcd，就能得到1
这里其实已经维护了左端点了，要求左端点尽量大。
1、为什么要维护左端点，因为答案给出的是[L, R]这段区间的不同gcd，如果你预处理的时候，R和L - 1得到的gcd是不能算进去的。
2、要求左端点尽量大，那是因为我后来要对R排序，尽量往R靠，结果是最优的，（可以参考下求区间不同数字个数的方法。后面再写。）
然后就是套路了。把得到的gcd往左端点里塞。♥，这是重点，一开始的时候我把不同的gcd往右端点塞了，这是不对的，因为往又端点塞的话，R与L - 1的gcd就会被你算进去了，所以会wa。
book[x]表示x这个值出现的最右的那个位置。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 1000000 + 20; const int N = 1000000 + 20; int c[maxn]; int lowbit(int x) { return x & (-x); } void upDate(int pos, int val) { while (pos <= N - 20) { c[pos] += val; pos += lowbit(pos); } } int query(int pos) { int ans = 0; while (pos) { ans += c[pos]; pos -= lowbit(pos); } return ans; } int n, q; int a[maxn]; struct node { int L, R; int id; bool operator < (const struct node & rhs) const { return R < rhs.R; } }b[maxn]; int book[maxn]; int ans[maxn]; void work() { memset(book, 0, sizeof book); memset(c, 0, sizeof c); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } for (int i = 1; i <= q; ++i) { scanf("%d%d", &b[i].L, &b[i].R); if (b[i].L > b[i].R) swap(b[i].L, b[i].R); b[i].id = i; } sort(b + 1, b + 1 + q); int cur = 1; // for (int i = 1; i <= q; ++i) { // cout << b[i].L << " " << b[i].R << endl; // } for (int i = 1; i <= q; ++i) { for (int j = cur; j <= b[i].R; ++j) { int x = a[cur]; for (int k = cur; k >= 1; k--) { if (book[x] < k) { //左端点只能尽量右靠，左边的不管,样例：7 7 7 if (book[x]) { //树状数组不能从0开始 upDate(book[x], -1); } book[x] = k; //不同的gcd，压到左端点 upDate(book[x], 1); } // if (book[x] > k) while(1); // book[x] = k; // upDate(book[x], 1); if (k == 1) break; if (x == 1) break; x = __gcd(x, a[k - 1]); } cur++; } ans[b[i].id] = query(b[i].R) - query(b[i].L - 1); } for (int i = 1; i <= q; ++i) { printf("%d ", ans[i]); } } int main() { #ifdef local freopen("data.txt","r",stdin); #endif while (scanf("%d%d", &n, &q) != EOF) work(); return 0; }
关于树状数组
3.1、求逆序对：首先先把数据离散化，因为树状数组覆盖的区间是1—max这样的，不离散的话开不到那么大的数组。例如离散后是：5、2、1、4、3、思路是：插入5，add(5,1)，把pos为5的地方设置为1，然后ans += i - get_sum(5); i的意思是当前插入了i个数，然后get_sum()是当前有多少个数比5少，其实就是问1—5之间存在多少个数，那当然是比5小的啦。一减，就是关于5逆序对个数。eg:关于2的逆序对个数是1对。
LL get_inversion (int a[],int lena) //求逆序对个数
{
LL ans = 0;//逆序对一般都很多，需要用LL
for (int i=1;i<=lena;++i) // a[]={5,2,1,4,3} ans=6;
{ // a[]={5,5,5,5,5} ans=0; 逆序对严格大于
add(a[i],1); ans += i-get_sum(a[i]);
}
return ans;
}
关于数据离散化，可以开一个结构体，保存val和pos，然后根据val排序一下，根据pos从小到大赋值即可。for (int i=1;i<=n;++i) a[book[i].pos]=i; //从小到大离散。a[3]=1,a[1]=2等等
{9,1,0,5,4} 离散化后 {5,2,1,4,3}
3.2、求解区间不同元素个数，离线算法。复杂度O（q + nlog(n)）
设树状数组的意义是：1--pos这个段区间的不同元素的种类数。怎么做？就是add(pos,1);在这个位置中+1，就是说这个位置上元素种类+1。然后先把询问按R递增的顺序排序。因为这里是最优的，我每次尽量往R靠，使得查询不重不漏。什么意思呢？就是假如有：2、1、3、5、1、7的话。一开始的[1,4]这段数字全部压进树状数组，用个数组book[val]，表示val这个元素出现的最右的位置，因为我们需要删除重复的，也是要尽量往右靠。到达pos=5这个位置的时候，注意了，因为1是出现过的book[1] = 2，所以我们要做的是把2这个位置出现元素的种类数-1，就是add(book[1], -1)。然后把第五个位置出现的元素种类数+1，就是add(5,1)。为什么呢？因为你尽量把种类往右靠，因为我们的R是递增的，这样，你使得查询[4,6]成为可能，因为我那个1加入来了，而不是一直用pos=2那个位置的1，再者，查询[4,7]的话，一样的意思，因为中间的1进来了。所以我们因为尽量往右靠，毕竟我们都把query按R排序了。还有这个只能离线，一直预处理ans[i]表示第i个询问的ans。更新到[4,7]后，查询[1,2]已经不可能了，因为很明显，pos=2这个位置已经被删除了。
void work ()
{
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
int q; scanf("%d",&q);
for (int i=1;i<=q;++i)
{
scanf("%d%d",&query[i].L,&query[i].R);
query[i].id = i; //记录ans
}
sort(query+1,query+1+q);
int cur = 1;
for (int i=1;i<=q;++i)
{
for (int j=cur;j<=query[i].R;++j)
{
if (book[a[j]])
add(book[a[j]],-1); //del 这个位置
book[a[j]]=j; //更新这个位置的最右值
add(j,1); //这个位置出现了新元素
}
cur = query[i].R+1; //表示现在预处理到这个位置了。不能往回查，而且也不会往回
ans[query[i].id] = get_sum(query[i].R) - get_sum(query[i].L-1); //区间减法
}
for (int i=1;i<=q;++i)
printf ("%d ",ans[i]);
}