hdu 3015 树状数组+离散化

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <algorithm>
  4. using namespace std;
  7. struct data
  8. {
  9. 	__int64 order;
  10. 	__int64 orign;
  11. 	__int64 rank;
  12. };
  14. data heigh[100100], coor[100100];
  16. int cmp(const void *a, const void *b)
  17. {
  18. 	return ( (*(data *)a).order - (*(data *)b).order );
  19. }
  21. int cmp1(const void *a, const void *b)
  22. {
  23. 	return (*(data *)a).orign - (*(data *)b).orign;
  24. }
  26. /*__int64 cmp1(const void *a, const void *b)
  27. {
  28. 	
  29. }*/
  31. int main()
  32. {
  33. 	freopen("read.txt", "r", stdin);
  35. 	__int64 n;
  36. 	while(~scanf("%d", &n) )
  37. 	{
  38. 		for(int i=1; i<=n; i++)
  39. 		{
  40. 			scanf("%I64d", &coor[i].orign);
  41. 			scanf("%I64d", &heigh[i].orign);
  42. 			coor[i].order = i;
  43. 			heigh[i].order = i;
  44. 		}
  46. 		qsort(coor, n, sizeof(coor[0]), cmp1);
  47. 		qsort(heigh, n, sizeof(heigh[0]), cmp1);
  49. 		int sign1, sign2, flag1, flag2;
  50. 		sign1 = sign2 = 1;
  51. 		flag1 = coor[1].orign, flag2 = heigh[1].orign;
  52. 		for(int i=1; i<=n; i++)
  53. 		{
  54. 			if(coor[i].orign != flag1)
  55. 			{
  56. 				flag1 = coor[i].orign;
  57. 				coor[i].rank = i+1;
  58. 				sign1 = i+1;
  59. 			}
  60. 			else 
  61. 				coor[i].rank = sign1;
  63. 			if(heigh[i].orign != flag2)
  64. 			{
  65. 				flag2 = heigh[i].orign;
  66. 				heigh[i].rank = i+1;
  67. 				sign2 = i+1;
  68. 			}
  69. 			else 
  70. 				heigh[i].rank = sign2;
  71. 		}
  73. 		//qsort(coor, n, sizeof(coor[0]), cmp);
  74. 		//qsort(heigh, n, sizeof(heigh[0]), cmp);
  75. 		
  76. 		//前面是对的， 但是我不知道怎么离散化。
  77. 	}
  78. 	return 0;
  79. }





附件列表

    【推广】 免费学中医，健康全家人
    原文地址：https://www.cnblogs.com/sober-reflection/p/0541852f4482f2b323b067f3f098466f.html