|
id=45786" style="color:blue; text-decoration:none">HDU - 4630
|
Time Limit: 2000MS |
|
Memory Limit: 32768KB |
|
64bit IO Format: %I64d & %I64u |
Submit Status
Description
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 a 1, a 2, ..., a n.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.
Input
First 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 a 1, a 2, ..., a n.
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.
Output
For each test cases,for each query print the answer in one line.
Sample Input
1
10
8 2 4 9 5 7 10 6 1 3
5
2 10
2 4
6 9
1 4
7 10
Sample Output
题意：求解给予[i , j]区间内随意两个值的最大gcd，而且输出它
因为数据一一去处理，复杂度肯定很大，所以要进行离线处理
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid + 1, r
#define root 1, 1, N
const int MAXN = 5e4 + 5;
int T, N, A[MAXN], Q, pre[MAXN], Sum[MAXN << 2], ans[MAXN];
struct qeu {
int l, r, id;
bool operator < (const qeu & a) const {
return r < a.r;
}
} QS[MAXN];
vector<int>G[MAXN];
void init() {
for(int i = 1; i < MAXN; i ++) {
for(int j = i ; j < MAXN; j += i) {
G[j].push_back(i);
}
}
}
void pushup(int rt) {
Sum[rt] = max(Sum[rt << 1], Sum[rt << 1|1]);
}
void build(int rt, int l, int r) {
Sum[rt] = 0;
if(l == r) return ;
int mid = (l + r) >> 1;
build(lson);
build(rson);
}
void update(int p, int v, int rt, int l, int r) {
if(l == r) {
Sum[rt] = max(Sum[rt], v);
return;
}
int mid = (l + r) >> 1;
if(p <= mid) update(p, v, lson);
else update(p, v, rson);
pushup(rt);
}
int query(int L, int R, int rt, int l, int r) {
if(L <= l && r <= R) {
return Sum[rt];
}
int mid = (l + r) >> 1;
int ret = 0;
if(L <= mid) ret = max(ret, query(L, R, lson));
if(R > mid) ret = max(ret, query(L, R, rson));
return ret;
}
int main() {
init();
//freopen("D://imput.txt", "r", stdin);
scanf("%d", &T);
while(T --) {
scanf("%d", &N);
build(root);
for(int i = 1; i <= N; i ++) {
scanf("%d", &A[i]);
}
scanf("%d", &Q);
for(int i = 1; i <= Q; i ++) {
scanf("%d%d", &QS[i].l, &QS[i].r);
QS[i].id = i;
}
memset(pre, -1, sizeof(pre));
sort(QS + 1, QS + Q + 1);
for(int i = 1, j = 1; i <= N && j <= Q; i ++) {
for(int k = 0 ; k < G[A[i]].size(); k ++) {
int tmp = G[A[i]][k];
if(pre[tmp] != -1) {
update(pre[tmp], tmp, root);
}
pre[tmp] = i;
}
while(j <= Q && QS[j].r == i) {
ans[QS[j].id] = query(QS[j].l, QS[j].r, root);
j ++;
}
}
for(int i = 1; i <= Q; i ++) {
printf("%d\n", ans[i]);
}
}
return 0;
}
|
