题目：
Life is a game,and you lose it,so you suicide.
But you can not kill yourself before you solve this problem:
Given you a sequence of number a1, a2, ..., an.They are also a permutation of 1...n.
You need to answer some queries,each with the following format:
If we chose two number a,b (shouldn't be the same) from interval [l, r],what is the maximum gcd(a, b)? If there's no way to choose two distinct number(l=r) then the answer is zero.
InputFirst line contains a number T(T <= 5),denote the number of test cases.
Then follow T test cases.
For each test cases,the first line contains a number n(1 <= n <= 50000).
The second line contains n number a1, a2, ..., an.
The third line contains a number Q(1 <= Q <= 50000) denoting the number of queries.
Then Q lines follows,each lines contains two integer l, r(1 <= l <= r <= n),denote a query.OutputFor each test cases,for each query print the answer in one line.Sample
| Inputcopy | Outputcopy |
|---|---|
1 10 8 2 4 9 5 7 10 6 1 3 5 2 10 2 4 6 9 1 4 7 10 |
5 2 2 4 3 |
题意：出一个长度为n的1到n的排列 ，求区间中里两个数的最大公约数的最大值
思路：公约数就是两个数的约数的交集，最大公约数自然就是其中最大的。
有Q个查询，如果单独计算一个区间的最大公约数，最快也是O(n)，Q个查询时间复杂度就是O(n^2)；
所以需要用到离线技巧，即将查询全部读入后，再处理（因为每次查询原来的东西并没有发生变化，所以可以离线）。
但我们写的数状数组的代码只能求[1，n] 的最值, 而不能求[l,r]的最值，且[1,l] 、[1.r]的最值与[l,r]的最值并没有联系，所以需要一点处理。
我们将所有的询问[ L , R ]按左端点L从大到小排序，从最大的L开始算，并用query(R)返回答案 (因为先更新大的L, 但 L 之前的数都没修改，即都为0，所以query(r) 求的 [1, R ] 的最大值其实就等价于[L , R]的最大值) ，下一步再从第二大的L下手。 在这个过程中，先计算的区间能用于后计算的区间，从而提高了效率。
代码：
点击查看代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<algorithm>
#include<fstream>
#include<iostream>
#include<cstdio>
#include<deque>
#include<string>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<unordered_map>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 310000
#define N 200010
#define endl '\n'
#define exp 1e-8
#define lc p << 1
#define rc p << 1|1
#define lowbit(x) ((x)&-(x))
const double pi = acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
inline ULL read() {
ULL x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch>'9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void print(ULL x) {
if (x > 9)print(x / 10);
putchar(x % 10 ^ 48);
}
int tree[N], t, arr[N], ans[N], last[N]; //tree[]就是树状数组，t表样例数，ans[]存答案，last[]用来求公约数
void update(int x, int d) //将标准的树状数组改写成这样来求最大值
{
while (x <= N)
{
tree[x] = max(tree[x], d);
x += lowbit(x);
}
}
int query(int x)
{
int ans = 0;
while (x)
{
ans = max(tree[x], ans);
x -= lowbit(x);
}
return ans;
}
struct node
{
int l, r, i;
bool operator < (const node& a)const
{
return l > a.l; //按L从大到小排序
}
}qu[N];
int main()
{
cin >> t;
while (t--)
{
memset(tree, 0, sizeof(tree));
memset(last, 0, sizeof(last));
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
int m;
cin >> m;
for (int i = 1; i <= m; i++)
{
int l, r;
cin >> l >> r;
qu[i].l = l;
qu[i].r = r;
qu[i].i = i; //读入数据
}
sort(qu + 1, qu + 1 + m);
int j = 1;
for (int i = n; i >= 1; i--) //因为L是从大到小，所以需要反向遍历
{ //以达到L前面的区间比L晚更新
for (int k = 1; k * k <= arr[i]; k++) //求约数的过程
{
if (arr[i] % k == 0)
{
if (last[k]) //分析这个过程，只有当约数出现两次时才能进行更新最大值
update(last[k], k);
if (last[arr[i] / k]) //k是arr[i]的约数，arr[i]/k自热也是arr[i]的约数
update(last[arr[i] / k], arr[i] / k);
last[k] = i; //last[k]中存储arr[i]的下标
last[arr[i] / k] = i;
}
}
while (qu[j].l >= i) //此时才可以更新答案(>= 和 == 都一样)
{
if (j > m)break;
ans[qu[j].i] = query(qu[j].r);
j++;
}
}
for (int i = 1; i <= m; i++)
{
cout << ans[i] << endl;
}
}
return 0;
}