HDU 5875 Function（简单线段树）

曾经终败给现在 2022-07-16 04:21 212阅读 0赞

题目链接：  
[http://acm.hdu.edu.cn/showproblem.php?pid=5875][http_acm.hdu.edu.cn_showproblem.php_pid_5875]

题目大意：（补题解中先把思路码上）

解题思路：  
因为余数逐渐递减，所以我们就要快速找到一段数小于等于x的第一个数，线段树结点维护区间最小值，当我们查询的时候，优先查左子树，当找到我们要的数的在某个区间时，在深入此区间进行查找，依旧优先查找左子树，找到直接返回即可。

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9+7;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    
    struct P
    {
        int val;
        int poi;
        P (int x,int y)
        {
            val=x;
            poi=y;
        }
        P() {}
    };
    
    int p[400005];
    
    int a[100005];
    
    void pushup(int rt)
    {
        p[rt]=p[rt<<1]<p[rt<<1|1]?p[rt<<1]:p[rt<<1|1];
    }
    
    void build(int l,int r,int rt)
    {
        if(l==r)
        {
            RI(p[rt]);
            a[l]=p[rt];
            return ;
        }
        int m=(l+r)>>1;
        build(l,m,rt<<1);
        build(m+1,r,rt<<1|1);
        pushup(rt);
    }
    
    
    
    P query2(int l,int r,int rt,int x)
    {
        if(l==r)
        {
            P p1(p[rt],l);
            return p1;
        }
        int m=(l+r)>>1;
        if(p[rt<<1]<=x) return query2(l,m,rt<<1,x);
        return query2(m+1,r,rt<<1|1,x);
    }
    
    P query(int l,int r,int rt,int L,int R,int x)
    {
        P p1(inf,inf),p2(inf,inf);
        if(L<=l&&r<=R)
        {
            if(p[rt]<=x)
            {
                return query2(l,r,rt,x);
            }
            else   return p1;
        }
    
        int m=(l+r)>>1;
        if(m>=L) p1=query(l,m,rt<<1,L,R,x);
        if(p1.val<=x) return p1;
        if(m<R)  p2=query(m+1,r,rt<<1|1,L,R,x);
        return p2;
    }
    
    int main()
    {
        int T,q,n;
        RI(T);
        while(T--)
        {
            RI(n);
            build(1,n,1);
            RI(q);
            for(int i=1; i<=q; i++)
            {
                int x,y;
                RII(x,y);
                int ans=a[x];
                if(x!=y)
                {
                    x++;
                    while(x<=y)
                    {
                        P p1=query(1,n,1,x,y,ans);
                        if(p1.poi==inf) break;
                        ans=ans%p1.val;
                        x=p1.poi+1;
                    }
                }
                printf("%d\n",ans);
            }
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5875]: http://acm.hdu.edu.cn/showproblem.php?pid=5875