首页 > ACM题库 > HDU-杭电 > HDU 4428-Polaris of Pandora-线段树-[解题报告]HOJ
2015
07-16

HDU 4428-Polaris of Pandora-线段树-[解题报告]HOJ

Polaris of Pandora

问题描述 :

Polaris is a star. It is the most magnificent scene in the sky, and the most important navigation star of planet Pandora[1]. People live in Pandora call themselves as "Na’vi"[2], and they all love to fly in the sky with their ikran[3]. When they are flying in the sky, they use Polaris to navigate. Polaris could be used to navigate because that it is always staying in the straight line linking the North Pole and the South Pole of Pandora. That straight line could also be called as "axis of Pandora", and Polaris stays on the North Pole side.
Polaris is too far away from Pandora, so in every place near Pandora, light from Polaris could be regarded as parallel to axis of Pandora. Now several Na’vi ikran riders are flying in the sky of Pandora, they want to know the percentage of their whole flying distance that Polaris is visible. Polaris’s light is quite bright, so Polaris is visible even when it is just on the skyline.
To simplify the problem, Na’vi riders assume that Pandora is a perfect sphere, which have an R radius. A rider starts flying from a point on the Pandora’s surface and lands at another point, the flying height is given as H. Ikran is so powerful that flying time between the surface of Pandora and the flying height could be ignored, and ikran will always fly straight up and down between surface and flying height. Both the starting point and the landing point could be described using latitude and longitude [4] of Pandora. And riders will always choose the shortest path to fly.

输入:

There are several test cases. Process to the end of file.
The only line of each test case contains 6 real numbers R (1000 ≤ R ≤ 10000), H (1 ≤ H ≤ R), lat0 (-π/2 < lat0 < π/2), lng0 (-π < lng0 < π), lat1 (-π/2 < lat1 < π/2), lng1 (-π < lng1 < π). R is radius of planet Pandora, H is Na’vi ikran rider’s flying height, lat0 and lng0 are latitude and longitude of starting point, lat1 and lng1 are latitude and longitude of landing point.
We guarantee that starting point and landing point will not be the same, and they also will not be "opposite" (Starting point, landing point and Pandora’s center will not be in the same line.)

输出:

There are several test cases. Process to the end of file.
The only line of each test case contains 6 real numbers R (1000 ≤ R ≤ 10000), H (1 ≤ H ≤ R), lat0 (-π/2 < lat0 < π/2), lng0 (-π < lng0 < π), lat1 (-π/2 < lat1 < π/2), lng1 (-π < lng1 < π). R is radius of planet Pandora, H is Na’vi ikran rider’s flying height, lat0 and lng0 are latitude and longitude of starting point, lat1 and lng1 are latitude and longitude of landing point.
We guarantee that starting point and landing point will not be the same, and they also will not be "opposite" (Starting point, landing point and Pandora’s center will not be in the same line.)

样例输入:

1000 10 0 0 0 0.5
4000 1000 0 0.618 1.0 0.618

样例输出:

100.000
64.350
Hint
Reference [1] Pandora is the fifth moon of the gas giant Polyphemus (both are figures in Greek mythology), which orbits the closest star to the sun, Alpha Centauri A. [2] The Na'vi (English: The People) are a race of sentient extraterrestrial humanoids who inhabit the lush jungle moon of Pandora. [3] Ikran (English: Mountain banshees) are large, bird-like aerial predators that are native to Pandora. They are used by the Na'vi for hunting from the air and traveling larger distances. [4] To define latitude and longitude of Pandora, we need to know equator of the planet. The equator is the intersection of Pandora's surface with the plane perpendicular to axis of Pandora and containing the planet's center. Latitude is a geographic coordinate that specifies the north-south position of a point on the Pandora's surface, it is the angle between the equator and the line connected point on the surface with the planet's center. Latitude is an angle which ranges from -π/2 at the North pole to π/2 at the South pole. Longitude is a geographic coordinate that specifies the east-west position of a point on the Earth's surface. Points with the same longitude lie in lines running from the North Pole to the South Pole. The longitude of a point on the surface is measured as an angle east or west from the Hometree [5], ranging from 0 at the Hometree to π eastward and -π westward. Specifically, it is the angle between a plane containing the Hometree and a plane containing the North Pole, South Pole and the point on the surface. [5] Hometrees (Na'vi name: Kelutral) are massive trees that can be found throughout Pandora. Many Na'vi clans make these enormous plants their home.

Coder

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2547    Accepted Submission(s): 1013

Problem Description
 
 In mathematics and computer science, an algorithm describes a set of
procedures or instructions that define a procedure. The term has become
increasing popular since the advent of cheap and reliable computers.
Many companies now employ a single coder to write an algorithm that will
replace many other employees. An added benefit to the employer is that
the coder will also become redundant once their work is done. 1
 
 You are now the signle coder, and have been assigned a new task writing
code, since your boss would like to replace many other employees (and
you when you become redundant once your task is complete).
Your code should be able to complete a task to replace these employees who do nothing all day but eating: make the digest sum.
 
 By saying “digest sum” we study some properties of data. For the sake
of simplicity, our data is a set of integers. Your code should give
response to following operations:
  1. add x – add the element x to the set;
  2. del x – remove the element x from the set;
  3. sum – find the digest sum of the set. The digest sum should be understood by
Polaris of Pandora

  where the set S is written as {a1, a2, … , ak} satisfying a1 < a2 < a3 < … < ak
  Can you complete this task (and be then fired)?
——————————————————————————
1 See http://uncyclopedia.wikia.com/wiki/Algorithm
 

 

Input
  There’re several test cases.
  In each test case, the first line contains one integer N ( 1 <= N <= 105 ), the number of operations to process.
  Then following is n lines, each one containing one of three operations: “add x” or “del x” or “sum”.
  You may assume that 1 <= x <= 109.
  Please see the sample for detailed format.
  For any “add x” it is guaranteed that x is not currently in the set just before this operation.
  For any “del x” it is guaranteed that x must currently be in the set just before this operation.
  Please process until EOF (End Of File).
 

 

Output
 
 For each operation “sum” please print one line containing exactly one
integer denoting the digest sum of the current set. Print 0 if the set
is empty.
 

 

Sample Input
9
add 1
add 2
add 3
add 4
add 5
sum
add 6
del 3
sum
6
add 1
add 3
add 5
add 7
add 9
sum
 

 

Sample Output
3
4
5
线段树:
区间一个维护该集合的个数,一个维护模5之后该集合对应1,2,3,4,0即sum[0,1,2,3,4](一一对应记录)的和。当添加一个数时,对应区间更新之后再向上更新。更新父区间时,等于左区间的Lsum[0,1,2,3,4]+右区间的Rsum[0,1,2,3,4]加上左区间个数来说。比如左区间有num个数,假设num%5 = 3,则sum[0] = Lsum[0] + Rsum[2]因为右区间的第三个数相当于整个左右区间模5余1。
sum[1] = Lsum[1] + Rsum[3],
sum[2] = Lsum[2] + Rsum[4],
sum[3] = Lsum[3] + Rsum[0],
sum[4] = Lsum[4] + Rsum[1];
即:sum[i] = Lsum[i] + Rsum[(((i - (num%5)) % 5 + 5) % 5]
 #include <stdio.h>
 #include <string.h>
 #include <algorithm>
 #include <iomanip>
 #include <set>
 #include <map>
 #include <vector>
 #include <queue>
 #define N 100005
 #define llt long long int
 using namespace std;
 
 int num[N << 2];//记录区间的个数 
 llt segtree[N << 2][5];// 
 struct node
 {
     int x;
     char s[4];
 }a[N];
 int b[N];
 map<int, int> mp;//使用map离散化 
 void build(int l, int r, int p)
 {
     memset(segtree[p], 0, sizeof(segtree[p]));
     num[p] = 0;
     if (l < r)
     {
         int mid = (l + r) >> 1, pp = p << 1;
         build(l, mid, pp);
         build(mid + 1, r, pp + 1);
     }
 }
 void update(int l, int r, int p, int pos, int v)
 {
     if (pos == l && pos == r)
     {
         segtree[p][0] += 1ll * v;
         num[p] = v > 0 ? 1 : 0;
         return;
     }
     int mid = (l + r) >> 1, pp = p << 1;
     if (mid >= pos)
         update(l, mid, pp, pos, v);
     else
         update(mid + 1, r, pp + 1, pos, v); 
     for (int i = 0; i < 5; i++)
         segtree[p][i] = segtree[pp][i] + segtree[pp + 1][((i - num[pp]) % 5 + 5) % 5];
     num[p] = num[pp] + num[pp + 1];
 }
 int main()
 {
     int n, i, k;
     while (~scanf("%d", &n))
     {
         k = 1;
         mp.clear();
         for (i = 1; i <= n; i++)
         {
             scanf("%s", a[i].s);
             if (a[i].s[0] == 'a')
             {
                 scanf("%d", &a[i].x);
                 b[k++] = a[i].x;
             }
             else
                 if (a[i].s[0] == 'd')
                 {
                     scanf("%d", &a[i].x);
                     a[i].x = -a[i].x;
                 }    
         }
         build(1, k - 1, 1);
         sort(b + 1, b + k); 
         for (i = 1; i < k; i++)
             mp[b[i]] = i;//重新编号 
         for (i = 1; i <= n; i++)
         {
             if (a[i].s[0] == 's')
                 printf("%I64d\n", segtree[1][2]);
             else
                 update(1, k - 1, 1, mp[abs(a[i].x)], a[i].x);            
         }
     }
     return 0;
 }

 

参考:http://www.cnblogs.com/jecyhw/archive/2013/12/01/3452473.html