HDU 5875 Function -2016 ICPC 大连赛区网络赛

题目链接

网络赛的水实在太深，这场居然没出线zzz，差了一点点，看到这道题的的时候就剩半个小时了。上面是官方的题意题解，打完了才知道暴力就可以过，暴力我们当时是想出来了的，如果稍稍再优化一下估计就过了zzz。去年有一场现场赛也是n=1000，n^3过了，看来关键时刻实在做不出来就得大胆暴力啊。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+;

int a[maxn],nex[maxn];

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n;

        scanf("%d",&n);

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

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

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

        {

            nex[i]=-;

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

                if(a[j]<=a[i])

                {

                    nex[i]=j;

                    break;

                }

        }

        int q;

        scanf("%d",&q);

        while(q--)

        {

            int l,r;

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

            int ans=a[l];

            for(int i=nex[l]; i<=r; i=nex[i])

            {

                if(i==-)break;

                ans%=a[i];

            }

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

        }

    }

    return ;

}