poj 1442 Black Box

acは長い間考えていた問題を本当に喜んで、運行は少し遅いが、cで自分で書いたスタックで、コードは短い.
構想:2つのスタックを維持し、1つの小さなスタックは与えられた数列の最大の一部を格納し、1つの大きなスタックは与えられた数列の残りの最小の一部を格納する.
プロセスの実行:
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
1を入力すると、大きな値を格納している小さなスタックに3を押し込み、小さな値を格納している大きなスタックがNULLであると判断すると、直接3を小さなスタックから取り出し、大きなスタックに押し込み、2つのスタックを更新し、大きなスタックの値を出力します.
2を入力すると、大きな値を格納する小さなスタックに1を押し込み、小さな値を格納する大きなスタックが空ではないと判断し、小さなスタックのスタック1<3であれば、1と3を交換し、小さなスタックが常に大きなものを格納し、大きなスタックが常に小さいものを格納することを保証します.区間尾に着くと、ループから飛び出して、小さな天井の天井を取り出して大きな天井に挿入し、大きな天井の天井が私たちが要求するn番目の小さな値であることを保証します.
6を入力すると2と同じで、ループに小さな天井のいくつかの数値を多く挿入します.具体的には、コードを参照してください.

 1 #include<stdio.h>

 2 #define INF 2000000000 + 1000000

 3 #define MAXN 31000

 4 

 5 int pmax, pmin, m, n, D;

 6 int a[MAXN],amin[MAXN<<1],amax[MAXN<<1],treemax[MAXN<<2],treemin[MAXN<<2];

 7 

 8 void updatemax(int cur)

 9 {

10     for(int i = cur; i^1; i >>= 1)

11     treemax[i>>1] = (amax[treemax[i]]>amax[treemax[i^1]]?treemax[i^1]:treemax[i]);    

12 }

13 

14 void updatemin(int cur)

15 {

16     for(int i = cur; i^1; i >>= 1)

17     treemin[i>>1] = (amin[treemin[i]]>amin[treemin[i^1]]?treemin[i]:treemin[i^1]);

18 }

19 

20 void build()

21 {

22     for(D = 1; D < m + 2; D <<= 1);

23     for(int i = 0; i <= D; i ++){treemax[D+i] = i; treemin[D+i] = i;}

24     for(int i = 0; i <= D; i ++){amax[i] = INF; amin[i] = -INF;}

25 }

26 

27 void init()

28 {

29     while(~scanf("%d%d",&m,&n))

30     {

31         for(int i = 0; i < m; i ++)

32             scanf("%d",&a[i]);

33         build();

34         int u;

35         for(int i = 0, j = 0; i < n; i ++)

36         {

37             scanf("%d",&u);

38             for( ; j < u; j ++)

39             {

40                 amax[pmax++] = a[j];

41                 updatemax(D+pmax-1);

42                 if(amin[treemin[1]] != -INF && amax[treemax[1]] < amin[treemin[1]])

43                 {

44                     int t;

45                     t = amax[treemax[1]];

46                     amax[treemax[1]] = amin[treemin[1]];

47                     amin[treemin[1]] = t;

48                     updatemax(D+treemax[1]);

49                     updatemin(D+treemin[1]);

50                 }

51             }

52             amin[pmin++] = amax[treemax[1]];

53             updatemin(pmin+D-1);

54             amax[treemax[1]] = INF;

55             updatemax(D+treemax[1]);

56             printf("%d
",amin[treemin[1]]);

57         }

58     }     

59 }

60 

61 int main()

62 {

63     pmax = 1;

64     pmin = 1;

65     init();

66     return 0;

67 }