HDU 4630 No Pain No Game(2013多校3 1010題オフライン処理+ツリー配列最値を求める)
16901 ワード
No Pain No Game
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 17 Accepted Submission(s): 5
Problem 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
Source
2013 Multi-University Training Contest 3
Recommend
zhuyuanchen520
問題はn個の数を与え,各数の範囲は1~nである.
n<=50000;
次にm回クエリーし、m<=50000
各クエリー[l,r]区間において、2つの数のgcdの最大値.
n個の数、n個の数の約数を全部書けば.クエリ[l,r]間のgcdの最大値は、この数が[l,r]間で少なくとも2つの約数であるように、最大数を探すことに相当する.
1つの数nについて、sqrt(n)内ですべての約数を見つけることができる.
私のやり方はクエリーをオフラインで処理することです.
各クエリーをlの大きいものから小さいものに並べ替えます.
そしてiはn~0から,これらの数を後からどんどん掃くことを示す.
数a[i]については、a[i]のすべての約数を見つける、約数xについては、xが前回出現した位置に値xを加える.
このようなクエリの場合,差分前のr個数の最大値であればよい.
コードを見てください.説明しません.
こんなに水が長い間考えていたなんて、とてもsadです.
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 17 Accepted Submission(s): 5
Problem 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
Source
2013 Multi-University Training Contest 3
Recommend
zhuyuanchen520
問題はn個の数を与え,各数の範囲は1~nである.
n<=50000;
次にm回クエリーし、m<=50000
各クエリー[l,r]区間において、2つの数のgcdの最大値.
n個の数、n個の数の約数を全部書けば.クエリ[l,r]間のgcdの最大値は、この数が[l,r]間で少なくとも2つの約数であるように、最大数を探すことに相当する.
1つの数nについて、sqrt(n)内ですべての約数を見つけることができる.
私のやり方はクエリーをオフラインで処理することです.
各クエリーをlの大きいものから小さいものに並べ替えます.
そしてiはn~0から,これらの数を後からどんどん掃くことを示す.
数a[i]については、a[i]のすべての約数を見つける、約数xについては、xが前回出現した位置に値xを加える.
このようなクエリの場合,差分前のr個数の最大値であればよい.
コードを見てください.説明しません.
こんなに水が長い間考えていたなんて、とてもsadです.
1 /*
2 * Author:kuangbin
3 * 1010.cpp
4 */
5
6 #include <stdio.h>
7 #include <algorithm>
8 #include <string.h>
9 #include <iostream>
10 #include <map>
11 #include <vector>
12 #include <queue>
13 #include <set>
14 #include <string>
15 #include <math.h>
16 using namespace std;
17
18 const int MAXN = 50010;
19 int c[MAXN];
20 int n;
21 int lowbit(int x)
22 {
23 return x&(-x);
24 }
25 void add(int i,int val)
26 {
27 while(i <= n)
28 {
29 c[i] = max(c[i],val);
30 i += lowbit(i);
31 }
32 }
33 int Max(int i)
34 {
35 int s = 0;
36 while(i > 0)
37 {
38 s = max(s,c[i]);
39 i -= lowbit(i);
40 }
41 return s;
42 }
43
44 int a[MAXN];
45 int b[MAXN];
46 int ans[MAXN];
47
48 struct Node
49 {
50 int l,r;
51 int index;
52 }node[MAXN];
53
54 bool cmp(Node a,Node b)
55 {
56 return a.l > b.l;
57 }
58
59 int main()
60 {
61 //freopen("in.txt","r",stdin);
62 //freopen("out.txt","w",stdout);
63 int T;
64 int m;
65 int l,r;
66 scanf("%d",&T);
67 while(T--)
68 {
69 scanf("%d",&n);
70 for(int i = 1;i <= n;i++)
71 scanf("%d",&a[i]);
72 scanf("%d",&m);
73 for(int i = 0;i < m;i++)
74 {
75 scanf("%d%d",&node[i].l,&node[i].r);
76 node[i].index = i;
77 }
78 sort(node,node+m,cmp);
79 int i = n;
80 int j = 0;
81 memset(b,0,sizeof(a));
82 memset(c,0,sizeof(c));
83 while(j < m)
84 {
85 while(i > 0 && i>= node[j].l)
86 {
87 for(int k =1;k*k <= a[i];k++)
88 {
89 if(a[i]%k == 0)
90 {
91 if(b[k]!=0)
92 {
93 add(b[k],k);
94 }
95
96 b[k] = i;
97 if(k != a[i]/k)
98 {
99 if(b[a[i]/k]!=0)
100 {
101 add(b[a[i]/k],a[i]/k);
102 }
103
104 b[a[i]/k]=i;
105 }
106 }
107 }
108 i--;
109 }
110 while(j < m && node[j].l > i)
111 {
112 ans[node[j].index]=Max(node[j].r);
113 j++;
114 }
115 }
116 for(int i = 0;i < m;i++)
117 printf("%d
",ans[i]);
118 }
119 return 0;
120 }