HDU 4777 Rabbit Kingdom(树状数组离线处理)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4777

题目大意: 一个兔子王国，有N只兔子，每只兔子有一个重量，如果两只兔子的重量不互质，那么就会干架，现在国王想将l r之间的兔子关进监狱，它想知道会有多少只兔子不会和别的兔子干架。也就是求l到r这个区间内有多少个数与所有数都互质

题目解析: 这题的思路真感觉是山路十八弯呀。后面学习了kuangbin大大的题解，才懂得怎么处理后面。

题目要求判断l到r内有多少个数与所有数都互质，那么我们可以求反面就是l，r内与其他数不互质的个数，可以想到先求每一个数num[i]到其左边和右边第一个与其不互质的数的我位置l[i],r[i]。=》 这里我们可以预处理，通过求出每一个数的因子，然后标记每一个因子的最大的位置，来求出某个数的因子中因子坐标最大的位置，即为l[i]。 对于r[i]则正好相反。

然后就是处理询问，将询问按照右区间排序，碰到i，则L位置+1，碰到R，则i位置+1，L位置-1。（如果L ≤ l && r ≤ R，那么兔子在这个l，r询问中是不会与其他兔子冲突）

这样l~r区间统计的即为会打架的兔子。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int maxn = 200020;
vector<int>V[maxn];
vector<int>vec[maxn];
int num[maxn];
int l[maxn], r[maxn];
int Hash1[maxn];
int Hash2[maxn];
struct Node
{
    int l, r, index;
}query[maxn];
void init()
{
    for(int i = 2;i <= 200010; i++)
        for(int j=i;j<200010;j+=i)
            V[j].push_back(i);
}

int cmp(Node a, Node b)
{
    if(a.r == b.r) return a.l < b.l;
    return a.r < b.r;
}
int c[maxn], a[maxn];
int lowbit(int x)
{
    return x & -x;
}

int sum(int x)
{
    int ret = 0;
    while(x > 0)
    {
        ret += c[x];
        x -= lowbit(x);
    }
    return ret;
}

void add(int x, int d)
{
    if(!x) return ;
    while(x < maxn)
    {
        c[x] += d;
        x += lowbit(x);
    }
}

int ans[maxn];
int main ()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int n, m;
    init();
    while(scanf("%d %d", &n, &m), n&&m)
    {
        memset(Hash1, 0, sizeof(Hash1));
        memset(Hash2, 0x3f, sizeof(Hash2));

        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &num[i]);
            int Min = 0;
            for(int j = 0; j < V[num[i]].size(); j++)
            {
                int tmp = V[num[i]][j];
                Min = max(Hash1[tmp], Min);
                Hash1[tmp] = max(Hash1[tmp], i);
            }
            l[i] = Min;
        }

        for(int i = n; i >= 1; i--)
        {
            int Max = n+1;
            for(int j = 0; j < V[num[i]].size(); j++)
            {
                int tmp =  V[num[i]][j];
                Max = min(Hash2[tmp], Max);
                Hash2[tmp] = min(Hash2[tmp], i);
            }
            r[i] = Max;
        }

        //for(int i = 1; i <= n; i++)
            //printf("l[%d] = %d, r[%d] = %d\n", i,l[i],i,r[i]);

        for(int i = 1; i <= m; i++)
        {
            scanf("%d %d", &query[i].l, &query[i].r);
            query[i].index = i;
        }

        sort(query+1, query+m+1, cmp);
        memset(c, 0, sizeof(c));
        for(int i = 1; i <= n; i++) vec[i].clear();
        for(int i = 1; i <= n;i++)  vec[r[i]].push_back(i);

        int id = 1;
        for(int i = 1; i <= m; i++)
        {
            while(id <= n && id <= query[i].r)
            {
                add(l[id]+1, 1);
                int  tmp = vec[id].size();
                for(int j = 0; j < tmp; j++)
                {
                    int v = vec[id][j];
                    add(l[v]+1, -1);
                    add(v+1, 1);
                }
                id++;
            }
            ans[query[i].index] = query[i].r - query[i].l + 1 - (sum(query[i].r+1) - sum(query[i].l-1+1));
        }
        for(int i = 1; i <= m; i++)
            printf("%d\n", ans[i]);
     }
    return 0;
}