POJ 2867 - Where Are My Genes

http://poj.org/problem?id=2867

概要

1, 2, ..., N と並んでいる N 個の要素からなる数列がある． その数列に対して，R 個の「i 番目から j 番目までの要素を反転させろ」という命令が与えられる．

それら操作を行った後の数列に対して，Q 個の「i 番目の要素は何か」というクエリが与えられるので，それらに答える．

制約

• 1 <= N <= 50000
• 0 <= R <= 1000
• 0 <= Q <= 100

解法

R 個の操作を覚えておき，クエリがくる度にそのインデックスについて逆算して答える． O(Q * R)．

また反転の操作は順番に依存しないので，逆算といっても R 個の操作を先頭からやっても同じ．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int Ti = 0;
 8   int N;
 9   while (scanf("%d", &N) != EOF && N != 0) {
10     int R;
11     scanf("%d", &R);
12     vector<pair<int,int> > rs(R);
13     for (int i = 0; i < R; i++) {
14       scanf("%d %d", &rs[i].first, &rs[i].second);
15     }
16     int Q;
17     scanf("%d", &Q);
18     printf("Genome %d\n", ++Ti);
19     for (int i = 0; i < Q; i++) {
20       int q;
21       scanf("%d", &q);
22       for (vector<pair<int,int> >::const_iterator it = rs.begin(); it != rs.end(); ++it) {
23         if (it->first <= q && q <= it->second) {
24           q = it->first + (it->second - q);
25         }
26       }
27       printf("%d\n", q);
28     }
29   }
30   return 0;
31 }