CodeForces - 356A Knight Tournament

http://codeforces.com/problemset/problem/356/A
まず題意を理解する 
lとrが与えられるたびに l-rの間に資格のある選手の中で勝者を出した.
暴力的な考え方:
まずは資格のある選手の集合を守る 
この選手が誰に負かされたかを配列で表す.
l-rを巡回するたびに勝者ではなく集合中の選手を蹴り出してその選手の配列値を更新する
最終的にこの配列を出力すればよい
これでTLE 
1、この集合を配列で維持すると毎回遍歴するのがO(n^2)-->>だからsetで維持する
2、setを使うたびにl-rから集合中の要素を探してfindに行くと、(l,r)の区間の両端に無駄な演算がありますl,rが1,nのたびに無駄になります
　　 だからset::lower_bound()は、lより大きい最初の要素O(logn)を直接得る.
このように最適化すればよい

 1 #include 
 2 #include 
 3 #include <set>
 4 using namespace std;
 5 
 6 
 7 int Par[300007];
 8 int tmp[300007];
 9 set<int> s;
10 
11 int find(int x)
12 {
13     if (Par[x] == x) return x;
14     else return find(Par[x]);
15 }
16 
17 int main()
18 {
19     int n, m;
20     freopen("in.txt", "r", stdin);
21     scanf("%d%d", &n, &m);
22     for (int i = 0; i <= n; i++)
23     {
24         Par[i] = i;
25         s.insert(i);//  set 
26     }
27     for(int i = 0; i < m; i++)
28     {
29         int l, r, x;
30         scanf("%d%d%d", &l, &r, &x);
31         set<int> :: iterator pit = s.lower_bound(l);//     >= l   
32         int num = 0;
33         while (pit != s.end() && (*pit) <= r )
34         {
35             if ((*pit) != x)
36             {
37                 Par[*pit] = x;
38                 //s.erase(*pit);              set       pit    
39                 tmp[num++] = *pit;
40             }
41             pit++;
42         }
43         for (int j = 0; j < num; j++) s.erase(tmp[j]);
44     }
45     for (int i = 1; i <= n; i++)
46     {
47         if (Par[i] == i) printf("0 ");
48         else printf("%d ", Par[i]);
49     }
50     putchar('
');
51 }

 
転載先:https://www.cnblogs.com/oscar-cnblogs/p/6390217.html