HDU5875 Function

**题意：**给定序列，有m个区间的询问，求每个询问a[l]%a[l+1]...%a[r]后的值。（N<=10^5） **思路：**这题如果使用线段树，可能会由于姿势和卡常数原因TLE，由于数据好像比较奇怪（？），可以使用比较蠢的方法水过。可知一个数x被不大于它的数模后一定会小于x/2的，故可以先对原序列处理出每个数下一个小于等于它的数的位置，每次进行跳转即可。 其实更好的做法是SparseTable+二分或者使用离线维护set求解。

/** @Date    : 2016-11-19-16.07

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version :

  */

#include <stdio.h>

#include <iostream>

#include <string.h>

#include <algorithm>

#include <utility>

#include <vector>

#include <map>

#include <set>

#include <string>

#include <stack>

#include <queue>

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

#define LL long long

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;



const int INF = 0x3f3f3f3f;

const int N = 1e5+2000;




int a[N];

int np[N];



int main()

{

    int T;

    int n, q;

    while(~scanf("%d", &T))

    {

        while(T--)

        {



            scanf("%d", &n);

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

                scanf("%d", a + i);

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

            {

                np[i] = -1;

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

                {

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

                    {

                        np[i] = j;

                        break;

                    }

                }

            }

            scanf("%d", &q);

            int l, r;



            while(q--)

            {

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

                int ans = a[l];

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

                {

                    if(i == -1 || ans == 0)

                        break;

                    ans %= a[i];

                }

                printf("%d
", ans);

            }

        }

    }

    return 0;

}