HDU 4630 No Pain No Gameセグメントツリーとhdu 3333には共通点があります
19493 ワード
No Pain No Game
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1465 Accepted Submission(s): 631
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
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1465 Accepted Submission(s): 631
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
1 /**
2 ： [ L , R ] max gcd() ;
3
4 ， 。
5 ， >=2 。
6 ， 。
7 [ L , R ] ， ，
8 。 ， 。
9
10 R ， [ L, R ] 。
11
12 r ， 。
13 **/
14 #include<iostream>
15 #include<stdio.h>
16 #include<cstring>
17 #include<cstdlib>
18 #include<algorithm>
19 #include<vector>
20 using namespace std;
21
22 vector<int>yz[50002];
23 struct node
24 {
25 int l,r,len;
26 int maxn;
27 }f[50002*4];
28 struct node2
29 {
30 int st,ed;
31 int i,val;
32 }a[50002];
33 int date[50002];
34 int pre[50002];
35
36 bool cmp(struct node2 n1,struct node2 n2)
37 {
38 return n1.ed<n2.ed;
39 }
40 bool cmp1(struct node2 n1,struct node2 n2)
41 {
42 return n1.i<n2.i;
43 }
44 void init()
45 {
46 for(int i=1;i<=50000;i++)
47 for(int j=i;j<=50000;j=j+i)
48 yz[j].push_back(i);
49 }
50 void build(int l,int r,int n)
51 {
52 int mid = (l+r)/2;
53 f[n].l = l;
54 f[n].r = r;
55 f[n].len = f[n].r-f[n].l +1;
56 f[n].maxn = 0;
57 if(l==r) return;
58 build(l,mid,n*2);
59 build(mid+1,r,n*2+1);
60 }
61 void update(int wz,int num,int n)
62 {
63 int mid=(f[n].l + f[n].r)/2;
64 if(f[n].l == wz && f[n].r == wz)
65 {
66 if(f[n].maxn<num)
67 f[n].maxn = num;
68 return;
69 }
70 if(mid>=wz) update(wz,num,n*2);
71 else if(mid<wz) update(wz,num,n*2+1);
72 f[n].maxn = f[n*2].maxn>f[n*2+1].maxn ? f[n*2].maxn : f[n*2+1].maxn;
73 }
74 int query(int l,int r,int n)
75 {
76 int mid=(f[n].l + f[n].r)/2;
77 if(f[n].l == l && f[n].r == r)
78 {
79 return f[n].maxn;
80 }
81 if(mid>=r) return query(l,r,n*2);
82 else if(mid<l) return query(l,r,n*2+1);
83 else return max(query(l,mid,n*2),query(mid+1,r,n*2+1));
84 }
85 int main()
86 {
87 int T , n , m;
88 init();
89 scanf("%d",&T);
90 while(T--)
91 {
92 scanf("%d",&n);
93 build(1,n,1);
94 for(int i=1;i<=n;i++)
95 scanf("%d",&date[i]);
96 scanf("%d",&m);
97 for(int i=1;i<=m;i++)
98 {
99 scanf("%d%d",&a[i].st,&a[i].ed);
100 a[i].i = i;
101 a[i].val = 0;
102 }
103 sort(a+1,a+1+m,cmp);
104 memset(pre,0,sizeof(pre));
105 int k = 1;
106 for(int i=1;i<=n;i++)
107 {
108 int ans = yz[date[i]].size();
109 for(int j=0;j<ans;j++)
110 {
111 int temp = yz[date[i]][j];
112 if(pre[temp])
113 update(pre[temp],temp,1);
114 pre[temp] = i;
115 }
116 while(a[k].ed == i && k<=m)
117 {
118 a[k].val = query(a[k].st,a[k].ed,1);
119 k++;
120 }
121 }
122 sort(a+1,a+1+m,cmp1);
123 for(int i=1;i<=m;i++) printf("%d
",a[i].val);
124 }
125 return 0;
126 }