HDU 5875 Function 2016 ACM/ICPC Asia Regional Dalian Online

时间：2022-08-27 01:07:46

N个数(N<=100000)，M个询问，每次询问L,R，求F(L,R)。

F(L,R)=F(L,R-1)%A[R] , L<R

这道题数据比较鶸 可以直接用递减爆 正确做法应该是倍增

用倍增的思想，对于位置i右侧的最长下降子序列，next[i][j]表示位置i右边第2j个的位置，预处理出每个位置的next数组

每次做的时候尽量远跳，直到找到next[j][0]恰好小于当前的值z，则z对A[next[j][0]]取模，移动左标记，继续查找，直到超出R或者没有更小的数

//

//by coolxxx

//#include<bits/stdc++.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<iomanip>

#include<map>

#include<stack>

#include<queue>

#include<set>

#include<bitset>

#include<memory.h>

#include<time.h>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

//#include<stdbool.h>

#include<math.h>

#define min(a,b) ((a)<(b)?(a):(b))

#define max(a,b) ((a)>(b)?(a):(b))

#define abs(a) ((a)>0?(a):(-(a)))

#define lowbit(a) (a&(-a))

#define sqr(a) ((a)*(a))

#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))

#define mem(a,b) memset(a,b,sizeof(a))

#define eps (1e-10)

#define J 10000

#define mod 1000000007

#define MAX 0x7f7f7f7f

#define PI 3.14159265358979323

#pragma comment(linker,"/STACK:1024000000,1024000000")

#define N 100004

#define M 18

using namespace std;

typedef long long LL;

double anss;

LL aans;

int cas,cass;

int n,m,lll,ans;

int a[N],s[N];

int nextt[N][M];

void init()

{

    int i,j,k,top;

    s[top=]=n;

    for(i=;i<M;i++)nextt[n][i]=n+;

    for(i=n-;i;i--)

    {

        while(top && a[i]<a[s[top]])top--;

        if(!top)nextt[i][]=n+;

        else nextt[i][]=s[top];

        s[++top]=i;

    }

    for(j=;j<M;j++)

    {

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

        {

            k=nextt[i][j-];

            nextt[i][j]=nextt[k][j-];

        }

    }

}

int work(int l,int r)

{

    int i,j,z=a[l];

    if(l==r)return z;

    while(l<r)

    {

        if(!z)return z;

        for(i=;i<M-;i++)

        {

            if(a[nextt[l][]]<=z || nextt[l][i]>r)break;

            if(a[nextt[l][i+]]<=z || nextt[l][i+]>r)

            {

                l=nextt[l][i];

                i=-;

                continue;

            }

        }

        if(i==M || nextt[l][i]>r || !a[nextt[l][i]])return z;

        z%=a[nextt[l][]];l=nextt[l][];

    }

    return z;

}

int main()

{

    #ifndef ONLINE_JUDGE

//    freopen("1.txt","r",stdin);

//    freopen("2.txt","w",stdout);

    #endif

    int i,j,k;

    int x,y,z;

//    init();

    for(scanf("%d",&cass);cass;cass--)

//    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)

//    while(~scanf("%s",s))

//    while(~scanf("%d",&n))

    {

        scanf("%d",&n);

        for(i=;i<=n;i++)scanf("%d",a+i);

        init();

        scanf("%d",&m);

        for(i=;i<=m;i++)

        {

            scanf("%d%d",&x,&y);

            printf("%d\n",work(x,y));

        }

    }

    return ;

}

/*

//

//

*/

相关文章