Hdu 3603
12730 ワード
Coach Yehr’s punishment
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 397 Accepted Submission(s): 114
Problem Description
During the Mult-University Trainging,Coach Yehr asks all the ACM teammates to jog at 6:30AM.But 6:30 is too early,there are always somebody might be late.Coach Yehr likes AC sequence very much,the AC sequence is a number sequence with all the elements different.A sequence (S1 ,S2 ,S3 ……Sn ) is a AC sequence if S1 ,S2 ,S3 ……Sn are all different. There are N teammates,the time(in second time) every teammate’arrival make a number sequence with length N. In order to punish the laters,Coach Yehr give them a puzzle,Coach Yehr choose a subsequence from Sa to Sb ,the laters must tell Coach Yehr the longest length of AC sequence in the subsequence as soon as possible.
Input
There are multiply text cases.You must deal with it until the end of file.
The first line of each test case is an interger N,indicates the number of ACM teammates;
The second line have N intergers,the i-th number indicates the i-th teammate’s arrival time.
The third line is an interger M indicates Coach Yehr will ask M times;
The follow M lines,each line have two intergers a and b,indicate the interval of the sequence.
Output
For each query,you have to print the longest length of AC sequence in the subsequence in a single line.
Sample Input
8 3 2 5 6 8 3 2 6 2 2 4 1 8 6 5 3 1 2 3 4 1 6 3 3
Sample Output
3 5 4 2
二分+RMQ、特にx>yのクエリがあることに注意します.
Accepted Code:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 397 Accepted Submission(s): 114
Problem Description
During the Mult-University Trainging,Coach Yehr asks all the ACM teammates to jog at 6:30AM.But 6:30 is too early,there are always somebody might be late.Coach Yehr likes AC sequence very much,the AC sequence is a number sequence with all the elements different.A sequence (S1 ,S2 ,S3 ……Sn ) is a AC sequence if S1 ,S2 ,S3 ……Sn are all different. There are N teammates,the time(in second time) every teammate’arrival make a number sequence with length N. In order to punish the laters,Coach Yehr give them a puzzle,Coach Yehr choose a subsequence from Sa to Sb ,the laters must tell Coach Yehr the longest length of AC sequence in the subsequence as soon as possible.
Input
There are multiply text cases.You must deal with it until the end of file.
The first line of each test case is an interger N,indicates the number of ACM teammates;
The second line have N intergers,the i-th number indicates the i-th teammate’s arrival time.
The third line is an interger M indicates Coach Yehr will ask M times;
The follow M lines,each line have two intergers a and b,indicate the interval of the sequence.
Output
For each query,you have to print the longest length of AC sequence in the subsequence in a single line.
Sample Input
8 3 2 5 6 8 3 2 6 2 2 4 1 8 6 5 3 1 2 3 4 1 6 3 3
Sample Output
3 5 4 2
二分+RMQ、特にx>yのクエリがあることに注意します.
Accepted Code:
1 /************************************************************************* 2 > File Name: 3603.cpp 3 > Author: Stomach_ache 4 > Mail: [email protected] 5 > Created Time: 2014 07 10 21 17 41 6 > Propose: 7 ************************************************************************/
8
9 #include <cmath>
10 #include <string>
11 #include <cstdio>
12 #include <fstream>
13 #include <cstring>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std; 17
18 const int MAX_N = 300002; 19
20 int n, m; 21 int vis[MAX_N], len[MAX_N], rmq[MAX_N][25]; 22
23 void rmq_init() { 24 for (int i = 1; i <= n; i++) rmq[i][0] = len[i]; 25 for (int j = 1; (1<<j) <= n; j++) { 26 for (int i = 1; i+(1<<(j-1))-1 <= n; i++) { 27 rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]); 28 } 29 } 30 } 31
32 int RMQ(int L, int R) { 33 int k = (int)(log(R - L + 1.0) / log(2.0)); 34 return max(rmq[L][k], rmq[R-(1<<k)+1][k]); 35 } 36
37 int solve(int x, int y) { 38 int = x, R = y, ans = -1; 39 while (L <= R) { 40 int M = (L + R) / 2; 41 if (len[M] >= M - x + 1) { 42 L = M + 1; 43 } else { 44 ans = M; 45 R = M - 1; 46 } 47 } 48 if (ans == -1) return y - x + 1; 49 return max(ans - x, RMQ(ans, y)); 50 } 51
52 int
53 main(void) { 54 while (~scanf("%d", &n)) { 55 memset(vis, 0, sizeof(vis)); 56 memset(len, 0, sizeof(len)); 57 int begin = 1; 58 for (int i = 1; i <= n; i++) { 59 int tmp; 60 scanf("%d", &tmp); 61 len[i] = min(i-begin+1, i-vis[tmp]); 62 begin = max(begin, vis[tmp]+1); 63 vis[tmp] = i; 64 } 65 //for (int i = 1; i <= n; i++) printf("%d
", len[i]);
66 rmq_init(); 67 scanf("%d", &m); 68 while (m--) { 69 int x, y; 70 scanf("%d %d", &x, &y); 71 // x > y
72 if (x > y) swap(x, y); 73 printf("%d
", solve(x, y)); 74 } 75
76 } 77
78 return 0; 79 }