题意

求区间l~r的a[l]%a[l+1]%……%a[r]的值

思路

因为取模的变化是很快的，所以线段树查找区间内第一个小于等于a[l]的数的位置，更新ans后继续查找即可。

注意查询满足某种条件的位置要这样写：

int query(int L,int R,int l,int r,int rt,int x)

{

if(mi[rt]>x) return inf;

if(l>R||r<L) return inf;

if(lr) return l;

int m=(l+r)>>1;

int ans=inf;

ans=min(ans,query(L,R,l,m,rt<<1,x));

if(ansinf)

ans=min(ans,query(L,R,m+1,r,rt<<1|1,x));

return ans;

}

代码

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

#define ll long long

const int N=1e5+5;

const double eps=1e-8;

const double PI = acos(-1.0);

#define lowbit(x) (x&(-x))

int mi[N<<2],add[N<<2];

int a[N],n;

void pushUp(int rt)

{

    mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);

}

void build(int l,int r,int rt)

{

    if(l==r)

    {

        mi[rt]=a[l];

        return;

    }

    int m=(l+r)>>1;

    build(l,m,rt<<1);

    build(m+1,r,rt<<1|1);

    pushUp(rt);

}

int query(int L,int R,int l,int r,int rt,int x)

{

    // cout<<"gg"<<endl;

    if(mi[rt]>x) return inf;

    if(l>R||r<L) return inf;

    if(l==r) return l;

    int m=(l+r)>>1;

    int ans=inf;

    ans=min(ans,query(L,R,l,m,rt<<1,x));

    if(ans==inf)

        ans=min(ans,query(L,R,m+1,r,rt<<1|1,x));

    return ans;

}

int main()

{

    int n;

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=1; i<=n; i++)

        {

            scanf("%d",&a[i]);

        }

        build(1,n,1);

        int q;

        scanf("%d",&q);

        while(q--)

        {

            int l,r;

            scanf("%d%d",&l,&r);

            int ans=a[l];

            while(l<=r)

            {

                int pos=query(l+1,r,1,n,1,ans);

                if(pos==inf)

                {

                    break;

                }

                ans%=a[pos];

                if(ans==0)

                    break;

                l=pos;

                //   cout<<pos<<endl;

            }

            printf("%d\n",ans);

        }

    }

    return 0;

}

巴特西

2016 ACM-ICPC Asia Regional Dalian Online HDU 5875 Function（线段树）

题意

思路

代码

最新文章

热门文章