HDU 4666 Hyperspace

Hyperspace

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 136    Accepted Submission(s): 66

Problem Description

The great Mr.Smith has invented a hyperspace particle generator. The device is very powerful. The device can generate a hyperspace. In the hyperspace, particle may appear and disappear randomly. At the same time a great amount of energy was generated.
However, the device is in test phase, often in a unstable state. Mr.Smith worried that it may cause an explosion while testing it. The energy of the device is related to the maximum manhattan distance among particle.
Particles may appear and disappear any time. Mr.Smith wants to know the maxmium manhattan distance among particles when particle appears or disappears.

 

Input

The input contains several test cases, terminated by EOF.
In each case: In the first line, there are two integer q(number of particle appear and disappear event, ≤60000) and k(dimensions of the hyperspace that the hyperspace the device generated, ≤5). Then follows q lines. In each line, the first integer ‘od’ represents the event: od = 0 means this is an appear
event. Then follows k integer(with absolute value less then 4 × 10 ⁷). od = 1 means this is an disappear event. Follows a integer p represents the disappeared particle appeared in the pth event.

 

Output

Each test case should contains q lines. Each line contains a integer represents the maximum manhattan distance among paticles.

 

Sample Input

   
   10 2
0 208 403
0 371 -180
1 2
0 1069 -192
0 418 -525
1 5
1 1
0 2754 635
0 -2491 961
0 2954 -2516
  
  

 

Sample Output

   
   0
746
0
1456
1456
1456
0
2512
5571
8922
  
  

 

Source

2013 Multi-University Training Contest 7

 

Recommend

zhuyuanchen520

 

题意： 有Q个操作。 没次操作会增加一个点， 或者删除一个点。 每次输出点集的最大曼哈顿距离。

思路： STL应用

不知道什么原理，师兄说的。

一维就是  Max (x) - Min(x)

就是对于 二维的 x - y   和 x + y 做两个集合。 答案肯定会在  Max( x - y) -  Min( x - y)  或者 是  Max(x + y)  -  Min(x + y)

而三维就是 Max(x + y + z) - Min(x + y + z)  或者是 Max(x + y - z)  - Min(x + y - z) 略。

就是  a +- b +- c +- d +- e

2 ^ (k - 1)个集合里。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

//

const int V = 60000 + 50;
const int inf = 0x7fffffff;
int n, k;
int main() {
    int i, j, q;
    while(~scanf("%d%d", &n, &k)) {
        multiset<int> s[20];
        map<int, int> m[20];
        for(i = 1; i <= n; ++i) {
            int op;
            scanf("%d", &op);
            if(op == 0) {
                int po[10];
                for(j = 0; j < k; ++j)
                    scanf("%d", &po[j]);
                for(j = 0; j < (1 << (k - 1)); ++j) {
                    int sum = po[0];
                    for(q = 0; q < k - 1; ++q) {
                        if(j & (1 << q))
                            sum -= po[q + 1];
                        else
                            sum += po[q + 1];
                    }
                    s[j].insert(sum);
                    m[j][i] = sum;
                }
            }
            else {
                int temp;
                scanf("%d", &temp);
                for(j = 0; j < (1 << (k - 1)); ++j) {
                    if(m[j].size() > 0) {
                        s[j].erase(s[j].find(m[j][temp]));
                        m[j].erase(temp);
                    }
                }
            }
            int Max = 0;
            for(j = 0; j < (1 << (k - 1)); ++j) {
                if(s[j].size() > 0) {
                    multiset<int>::iterator fi = s[j].begin();
                    multiset<int>::iterator se = s[j].end();
                    se--;
                    Max = max(Max, *se - *fi);
                }
            }
            printf("%d\n", Max);
        }
    }
}