hdu7724

题意

题目链接

一条链，每个点上有一个数 ，每条边上有一个质数 。一开始在某个点上，有一个空背包，走到一个点上可以把它的质因子放进背包，一条边如果背包里有那个质数就可以走。多组询问求从 x 出发能否走到 y（即求每个点能走到的最大范围）。

题解

因为存在多组询问，可以求出每个点作为起点能访问的区间段$[l_i, r_i]$。

从左到右进行考虑，假设已经求出了前i个点能访问的区间段，思考如何利用前i个点的区间信息辅助求出i+1个点的区间。

结论：假设x点可以访问y点，那么x的访问区间一定包含（或等于）y的访问区间。

证明：显然，x可以访问y，则背包含有y的所有因子，相当于从y出发且可能含有更多质因子，访问区间一定不会劣于从y出发。

利用以上结论，可以根据$l_1,l_2…l_i$扩展$l_{i+1}$，如果从$i+1$出发能够达到$l_{i + 1} - 1$，则$l[i + 1] = l[l[i + 1]- 1]$，可以快速跳区间。因为所有区间都是不相交的，如果某个点跳过这个区间，后面的点只会利用这个点往前跳，也就是说每个区间只会被跳一次，总复杂度均摊下来为$O(n)$。

还剩一个问题就是根据当前确定的区间$[l_i,r_i]$，判断$l_i$是否可以再往旁边扩展？假设最左边那条边上的质数为p，只要判断$[l_i,r_i]$区间内是否存在这个质因子。最开始想到的是主席树，后来想到一个好写的做法：20000以内只有18000多质数，可以开质因子个数的vector存下每个质因子出现的位置，因为每个点的值不超过200000，最多提供6个质因子，所以总数不会太大。之后判断的时候只要在vector上upper_bound即可。

解决了左端点扩展的问题，再来看右端点扩展。每次左端点跳完后，再来看右端点能够跳到哪。假设每条边都是向右的单向边，根据每条边上的质数，可以在vector上lower_bound知道至少要到达前面哪个点才能通过这条边，再利用ST表计算出从i号点向右走$2^j$步，至少需要到达哪个点才能通行。利用ST表可以$O(\log n)$判断$r_i$能扩展到的位置。

因为左端点扩展，可以帮助右端点扩展；右端点扩展后，又能促进左端点扩展。所以两边依次扩展，单次扩展都是$O(\log n)$。左端点最多跳$O(n)$次数，右端点扩展次数等同于左端点扩展次数，所以总时间复杂度为$O(n \log n)$。

代码

/*************************************************************************
> File Name: 1.cpp
> Author: Knowledge_llz
> Mail: 925538513@qq.com
> Blog: https://www.cnblogs.com/Knowledge-Pig/ 
************************************************************************/

#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 2e5 + 5;
int n, m, cnt, pri[maxx], id[maxx], l[maxx], r[maxx], b[maxx], pre[maxx][18];
bool vis[maxx];
int p[maxx][6], num[maxx];
vector<int> pos[20000];
void init(){
    for(int i = 2; i <= 200000; ++i){
        if(!vis[i]){ pri[++cnt] = i; id[i] = cnt; }
        for(int j = 1; j <= cnt; ++j){
            if(1ll * i * pri[j] > 200000) break;
            vis[i * pri[j]] = 1;
        }
    }
    for(int i = 1; i <= cnt; ++i)
        for(int j = pri[i]; j <= 200000; j += pri[i])
            p[j][num[j]++] = i;
}
int query(int ll, int rr, int k){
    int x = upper_bound(pos[k].begin(), pos[k].end(), rr) - lower_bound(pos[k].begin(), pos[k].end(), ll);
    return x;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt","w", stdout);
#endif
    init();
    int T; cin >> T;
    while(T--){
        cin >> n >> m;
        for(int i = 1; i <= cnt; ++i) pos[i].clear();
        for(int i = 1, u; i <= n; ++i){
            cin >> u;
            l[i] = r[i] = i;
            for(int j = 0; j < num[u]; ++j){
                pos[p[u][j]].push_back(i);
            }
        }
        for(int i = 1; i < n; ++i){
            cin >> b[i];
            b[i] = id[b[i]];
            pre[i][0] = upper_bound(pos[b[i]].begin(), pos[b[i]].end(), i) - pos[b[i]].begin() - 1;
            if(pre[i][0] != -1) pre[i][0] = pos[b[i]][pre[i][0]];
        }
        for(int i = 1; i < 18; ++i)
            for(int j = 1; j + (1 << i - 1) < n; ++j)
                pre[j][i] = min(pre[j][i - 1], pre[j + (1 << i - 1)][i - 1]);
        for(int i = 1; i <= n; ++i){
            int flag = 1;
            while(flag){
                flag = 0; 
                while(l[i] > 1 && query(l[i], r[i], b[l[i] - 1]) >= 1){
                    l[i] = l[l[i] - 1]; 
                    flag = 1;
                }
                for(int j = 17; j >= 0; --j){
                    if(r[i] + (1 << j) <= n && l[i] <= pre[r[i]][j]){
                        r[i] += (1 << j);
                        flag = 1;
                    }
                }
            }
        }
        for(int i = 1; i <= m; ++i){
            int x, y;
            cin >> x >> y;
            if(y >= l[x] && y <= r[x]) cout << "Yes\n";
            else cout << "No\n";
        }
    }
    return 0;
}