hdu 4777 Rabbit Kingdom - c++编程基础

对于每个兔子的重量质分解，分别看它所有质因子的左右最早出现的位置就是该数到左右两边能互质的范围。然后就很容易更新出l[i]，r[i]了（l[i],r[i]是和wi不互质的）。

关键是解决查询。对于查询，要是直接做的话会感到无从下手的，于是我们考虑能否通过离线把所有查询处理出来。这样的话我们就可以考虑这样一个问题，对于一个区间，我们要求的就是这个区间中满足数的左右范围大于区间范围的点的个数。对于这道题，采用的通过把不满足的点数求出来，然后总数一减就可以了。

那么我们要怎么求不满足的情况呢？对于一个区间，其中不满足情况的点我们可以分作两种情况：

1、点左边界比区间左边界大的点的个数。

2、点右边界比区间右边界小的点的个数。

显然会有点即满条件1，也满足条件2。对于这种点我们只需要记录第二种情况的时候把在第一种情况中计数删去就可以了（这也是这道题的关键之处，即怎么离线处理）。

先说一下离线处理的大致思路吧，我们先把询问按右边界排序，然后再看每个点对于询问的影响。首先我们应该注意到，一个点的右边界一定是大于这个点的下标大小的（1），于是我们可以预先把，所有点的右边界为r的点存入vector中，即vt[r].PB(i) 表示i点的右边界是r。这样我们在枚举右边界的同时可以把该点的左边界l[i]到n都+1（由（1），该点右边界一定满足当前的右边界），表示该点左边界的影响范围。然后对于枚举的右边界ri，如果ri比当前询问的q[i].r小于或等于的话，我们就把vt[ri]中的所有点的左边界l[i]到n都-1，同时该点的位置id到n都+1。这样的话就可以保证了我们求不满足的情况时:用l[i]，更新的点都是右边界满足情况的点，用点位置id更新的都是右边界不满足情况的点，操作l[i]到n-1，就是去重操作，即统计2、的时候把满足1、的删去。以上操作都是在树状数组中进行的，相信大家都懂得。。。

于是不满足的情况就是getsum(q[i].r) - getsum(q[i].l - 1])。到此问题就解决了。

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define REP(i, n) for(int i=0; i=b; i--)  
#define LL long long  
#define PB push_back  
#define CLR(a, b) memset(a, b, sizeof(a))  
using namespace std;  
const int N = 200100;  
  
int p[N], cnt;  
bool isp[N];  
int l[N], r[N], fir[N];  
vector hav[N];  
int n, m, w[N];  
  
struct Query  
{  
    int l, r, id;  
    bool operator < (const Query& rhs) const  
    {  
        return r < rhs.r;// || (r == rhs.r && l 




 1 && p[j] * p[j] <= tmp; j ++)  
        {  
            if(tmp % p[j] == 0)  
            {  
                hav[i].PB(p[j]);  
                while(tmp % p[j] == 0)  
                {  
                    tmp /= p[j];  
                }  
            }  
        }  
        if(tmp > 1) hav[i].PB(tmp);  
    }  
}  
  
int sum[N];  
  
void add(int x, int ad)  
{if(!x) return;  
    while(x <= n)  
    {  
        sum[x] += ad;  
        x += x & (-x);  
    }  
}  
  
int getsum(int x)  
{  
    int ret = 0;  
    while(x > 0)  
    {  
        ret += sum[x];  
        x -= x & (-x);  
    }  
    return ret;  
}  
  
void init()  
{  
    for(int i = 1; i <= n; i ++)  
    {  
        scanf("%d", &w[i]);  
    }  
    CLR(fir, 0);  
    for(int i = 1; i <= n; i ++)  
    {  
        l[i] = 1;  
        for(int j = 0; j < hav[w[i]].size(); j ++)  
        {  
            int idx = hav[w[i]][j];  
            l[i] = max(fir[idx] + 1, l[i]);  
            fir[idx] = i;  
        }  
        l[i] --;  
    }  
    for(int i = 0; i < N; i ++) fir[i] = n + 1;  
    for(int i = n; i > 0; i --)  
    {  
        r[i] = n;  
        for(int j = 0; j < hav[w[i]].size(); j ++)  
        {  
            int idx = hav[w[i]][j];  
            r[i] = min(fir[idx] - 1, r[i]);  
            fir[idx] = i;  
        }  
        r[i] ++;  
    }  
}  
  
vector vt[N];  
int ans[N];  
  
void solve()  
{  
    for(int i = 0; i < m; i ++)  
    {  
        scanf("%d%d", &q[i].l, &q[i].r);  
        q[i].id = i;  
    }  
    sort(q, q + m);  
    for(int i = 1; i <= n; i ++)  
    {  
        sum[i] = 0;  
        vt[i].clear();  
    }  
    for(int i = 1; i <= n + 1; i ++) vt[r[i]].PB(i);  
    int ri = 1;  
    for(int i = 0; i < m; i ++)  
    {  
        while(ri <= n && ri <= q[i].r)  
        {  
            add(l[ri], 1);///把ri点加进去  
            int sz = vt[ri].size();  
            for(int j = 0; j < sz; j ++)  
            {  
                int id = vt[ri][j];  
                add(l[id], -1);///删去id点  
                add(id, 1);///标记右边界到达不了q[i].r的点  
            }  
            ri ++;  
        }  
        int tmp = getsum(q[i].r) - getsum(q[i].l - 1);///表示的是右边界到达不到q[i].r，和左边界大于q[i].l的点的个数  
        ans[q[i].id] = q[i].r - q[i].l + 1 - tmp;  
    }  
    for(int i = 0; i < m; i ++)  
    {  
        printf("%d\n", ans[i]);  
    }  
}  
  
int main()  
{  
    get_P();get_hav();  
    while(scanf("%d%d", &n, &m), n + m)  
    {  
        init();  
        solve();  
    }  
}