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;
}