题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5875
题意：有n个数，m个查询，每个查询有一个区间[L, R], 求ans, ans = a[L]%a[L+1]%a[L+2]%...%a[R];
方法一：算是暴力吧，只能说数据太水；
用pos[i] = j 表示第 i 个元素后面的一个<= a[i]的下标是 j ；
然后直接跳到当前位置即可，（我感觉如果数中有10e5个严格递减或者严格递增的序列是会TLE吧）但是这个还是过了，我想应该是数据太弱了吧
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define met(a, b) memset(a, b, sizeof(a))
#define N 100005
#define INF 0x3f3f3f3f
typedef long long LL;
#define Lson r<<1
#define Rson r<<1|1 int n, a[N], pos[N], m; int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i=; i<=n; i++)
scanf("%d", &a[i]); a[] = INF; for(int i=; i<=n; i++)
{
for(int j=i+; j<=n; j++)
{
if(a[j] <= a[i])
{
pos[i] = j;
break;
}
}
}
scanf("%d", &m);
for(int i=; i<=m; i++)
{
int L, R;
scanf("%d %d", &L, &R);
int ans = a[L];
while(ans && pos[L]<=R && L)
{
ans = ans%a[pos[L]];
L = pos[L];
}
printf("%d\n", ans);
}
}
return ;
}
方法二：在每个查询的时候，用线段树查找，当在区间[L, R]中找到第一个<=num的位置即可；
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define met(a, b) memset(a, b, sizeof(a))
#define N 400005
#define INF 0x3f3f3f3f
typedef long long LL;
#define Lson r<<1
#define Rson r<<1|1 struct node
{
int L, R, Min;
int mid() {return (L+R)/;}
}a[N]; int n, t[N]; void Build(int r, int L, int R)
{
a[r].L = L, a[r].R = R; if(L == R)
{
scanf("%d", &a[r].Min);
t[L] = a[r].Min;
return ;
} Build(Lson, L, a[r].mid());
Build(Rson, a[r].mid()+, R); a[r].Min = min(a[Lson].Min, a[Rson].Min);
} int Query(int r, int L, int R, int num)
{
if(a[r].Min > num)
return n+;
if(a[r].L >= L && a[r].R <= R)
{
if(a[r].L == a[r].R) return a[r].L;
if(a[Lson].Min <= num)
return Query(Lson, L, R, num);
else
return Query(Rson, L, R, num);
}
else
{
if(L <= a[r].mid())
{
int pos = Query(Lson, L, R, num);
if(pos <= R)
return pos;
}
if(R > a[r].mid())
{
int pos = Query(Rson, L, R, num);
if(pos <= R)
return pos;
}
}
return n+;
} int main()
{
int T, m;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n); Build(, , n); scanf("%d", &m); for(int i=; i<=m; i++)
{
int L, R;
scanf("%d %d", &L, &R);
int pos = L, ans = t[L];
while(pos <= R && ans)
{
pos = Query(, pos+, R, ans);
if(pos<=R) ans = ans%t[pos];
}
printf("%d\n", ans);
}
}
return ;
}
/*
15
6
4 6 5 3 2 8
15
1 6
*/