HDU - 4630 No Pain No Game (线段树 + 离线处理)

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

5
2
2
4
3
题意:求解给予[i , j]区间内随意两个值的最大gcd,而且输出它
因为数据一一去处理,复杂度肯定很大,所以要进行离线处理
详细内容,提供一个大牛博客:http://m.blog.csdn.net/blog/u010033217/38156507
HDU - 4630 No Pain No Game (线段树 + 离线处理)
#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;
}




上一篇:14.10.3 InnoDB Checkpoints InnoDB 检查点:


下一篇:14.6.7?Limits on InnoDB Tables InnoDB 表的限制