E - No Pain No Game HDU 4630 线段树

小咪咪 2021-11-02 09:38 155阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
Life is a game,and you lose it,so you suicide.  
But you can not kill yourself before you solve this problem:  
Given you a sequence of number a 1, a 2, …, a n.They are also a permutation of 1…n.  
You need to answer some queries,each with the following format:  
If we chose two number a,b (shouldn’t be the same) from interval \[l, r\],what is the maximum gcd(a, b)? If there’s no way to choose two distinct number(l=r) then the answer is zero.  
Input  
First line contains a number T(T <= 5),denote the number of test cases.  
Then follow T test cases.  
For each test cases,the first line contains a number n(1 <= n <= 50000).  
The second line contains n number a 1, a 2, …, a n.  
The third line contains a number Q(1 <= Q <= 50000) denoting the number of queries.  
Then Q lines follows,each lines contains two integer l, r(1 <= l <= r <= n),denote a query.  
Output  
For each test cases,for each query print the answer in one line.  
Sample Input

1  
10  
8 2 4 9 5 7 10 6 1 3  
5  
2 10  
2 4  
6 9  
1 4  
7 10

Sample Output  
5  
2  
2  
4  
3

分析：现在觉得线段树的题目不是代码量多了。我已经感觉这是思维题呀。真心难，虽然直觉我就感觉是线段树，但奈何太菜，无法写出来。  
参考博客：[https://www.cnblogs.com/EchoZQN/p/10829367.html][https_www.cnblogs.com_EchoZQN_p_10829367.html]  
[https://blog.csdn.net/u010033217/article/details/38156507][https_blog.csdn.net_u010033217_article_details_38156507]

说下我的理解吧。  
离线化的概念并不难理解，是把所有的查询先保存下来，然后通过分析查询之间的关系，已达到降低复杂度的目的。最后在统一输出。

那么，这个题我们采用离线化来求。  
我们如何分析查询之间的关系，并达到降低复杂度的目的呢。

题目目的是给定m个区间，要你从区间内找到任意两个数的最大公约数。  
公约数的求法一般都是辗转相除法了。  
在这里，我们可以求出每个数的因子，如果第1个数和第2个数的因子都是5.那么5是可以作为备选答案来考虑的。

至此说一下整体思路吧。  
1，我们把m次查询用结构体保存，并且按照右端点的值从小到大排序。  
2，我们从左到有扫描a数组，对于a\[i\]，我们要进行的操作就是把a\[i\]的因子的前一个位置的最大gcd不断更新。（更新的原因在于，使查询的时候能查询到的是最优解）。  
3，在扫描的时候，满足查询条件就要马上查询。所以，我们之前更新因子前一个位置，这里建议画下数轴啥的模拟一下就秒懂了。

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    typedef struct Node
    {
        int l,r,id;
    }Node;
    
    int T,n,m,a[50010];
    Node node[5 * 50010];
    vector<int> Q[50010];
    int max_val[5 * 50010];
    int pre[50010];
    int ans[50010];
    
    void init()
    {
        for(int i = 1; i <= 50000; i ++)
        {
            for(int j = i;j <= 50000; j += i)
                Q[j].push_back(i);
        }
    }
    
    int cmp(Node a,Node b)
    {
        return a.r < b.r;
    }
    
    void Update(int id,int L,int R,int x,int val)
    {
        if(L == R)
            {
                max_val[id] = max(val,max_val[id]); return ;
            }
        int mid = (L + R) >> 1;
        if(x <= mid) Update(id << 1,L,mid,x,val);
        else Update(id << 1 | 1,mid + 1,R,x,val);
        max_val[id] = max(max_val[id << 1],max_val[id << 1 | 1]);
    }
    
    int Query(int id,int L,int R,int l,int r)
    {
        if(l <= L && r >= R) return max_val[id];
        int mid = (L + R) >> 1;
        int ans = 0;
        if(l <= mid) ans = max(ans,Query(id << 1,L,mid,l,r));
        if(r > mid) ans = max(ans,Query(id << 1 | 1,mid + 1,R,l,r));
        return ans;
    }
    
    void init_1()
    {
        memset(pre,0,sizeof(pre));
        for(int i = 1; i < 5 * 50010; i ++)
            max_val[i] = 0;
    }
    int main()
    {
        init();
        scanf("%d",&T);
        while(T --)
        {
            scanf("%d",&n);
            init_1();
            for(int i = 1; i <= n; i ++)
            {
                scanf("%d",&a[i]);
            }
            scanf("%d",&m);
            for(int i = 1; i <= m; i ++)
            {
                scanf("%d%d",&node[i].l,&node[i].r);
                node[i].id = i;
            }
            sort(node + 1,node + 1 + m,cmp);
            for(int i = 1,j = 1; i <= n;i ++)
            {
                if(j > m) break;
                for(int k = 0; k < Q[a[i]].size(); k ++)
                {
                    int tmp = Q[a[i]][k];
                  //  printf("for tmp = %d\n",tmp);
                    if(pre[tmp] != 0)
                    {
                       // printf("while:  %d %d %d\n",pre[tmp],tmp,i);
                        Update(1,1,n,pre[tmp],tmp);
                    }
                    pre[tmp] = i;
                }
                while(j <= m && i == node[j].r)
                {
                    int val = Query(1,1,n,node[j].l,node[j].r);
                    //printf("%d %d %d\n",i,j,val);
                    ans[node[j].id] = val;
                    j ++;
                }
            }
            for(int i = 1; i <= m; i ++)
                printf("%d\n",ans[i]);
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/
[https_www.cnblogs.com_EchoZQN_p_10829367.html]: https://www.cnblogs.com/EchoZQN/p/10829367.html
[https_blog.csdn.net_u010033217_article_details_38156507]: https://blog.csdn.net/u010033217/article/details/38156507