BZOJ4066 简单题

妈蛋真简单。。。

离线版的可以乱搞。。。貌似是BZOJ的2683

在线的话。。一开始想到了BIT套平衡树。。。空间复杂度$O(n * logm)$非常开心的MLE了。。。QAQ

于是写KD树，空间复杂度$O(n)$，时间复杂度$O(msqrt(m))$，于是就过了QAQQQ

看错题了非常开心。。。一开始读入的终止条件写成了：

    for (i = 1; i <= n; ++i)

于是再见了QAQQQ

  1 /**************************************************************
  2     Problem: 4066
  3     User: rausen
  4     Language: C++
  5     Result: Accepted
  6     Time:42812 ms
  7     Memory:9408 kb
  8 ****************************************************************/
  9  
 10 #include <cstdio>
 11 #include <algorithm>
 12  
 13 using namespace std;
 14 typedef long long ll;
 15 const int M = 2e5 + 5;
 16  
 17 int n;
 18 ll ans;
 19  
 20 inline int read(int f = 1) {
 21     static int x;
 22     static char ch;
 23     x = 0, ch = getchar();
 24     while (ch < '0' || '9' < ch)
 25         ch = getchar();
 26     while ('0' <= ch && ch <= '9')
 27         x = x * 10 + ch - '0', ch = getchar();
 28     if (f) x ^= ans;
 29     return x;
 30 }
 31  
 32 struct point {
 33     int x[2], v;
 34      
 35     int& operator [] (int i) {
 36         return x[i];
 37     }
 38     inline bool operator == (const point &p) const {
 39         return x[0] == p.x[0] && x[1] == p.x[1];
 40     }
 41     inline void get() {
 42         x[0] = read(), x[1] = read(), v = read();
 43     }
 44 };
 45  
 46 struct KD_tree {
 47     KD_tree *son[2];
 48     point p;
 49     int mn[2], mx[2];
 50     ll sum;
 51      
 52     KD_tree(point _p) {
 53         son[0] = son[1] = NULL, p.v = sum = _p.v;
 54         p[0] = mn[0] = mx[0] = _p[0], p[1] = mn[1] = mx[1] = _p[1];
 55     }
 56     KD_tree() {}
 57      
 58     inline void* operator new(size_t, point _p) {
 59         static KD_tree mempool[M], *c = mempool;
 60         *c = KD_tree(_p);
 61         return c++; 
 62     }
 63      
 64     inline void update() {
 65         static int i;
 66         for (i = 0; i < 2; ++i) {
 67             mn[i] = mx[i] = p[i];
 68             if (son[0]) {
 69                 mn[i] = min(mn[i], son[0] -> mn[i]);
 70                 mx[i] = max(mx[i], son[0] -> mx[i]);
 71             }
 72             if (son[1]) {
 73                 mn[i] = min(mn[i], son[1] -> mn[i]);
 74                 mx[i] = max(mx[i], son[1] -> mx[i]);
 75             }
 76         }
 77         sum = p.v;
 78         if (son[0]) sum += son[0] -> sum;
 79         if (son[1]) sum += son[1] -> sum;
 80     }
 81      
 82     void insert(point _p, int dep) {
 83         if (p == _p) {
 84             p.v += _p.v, sum += _p.v;
 85             return;
 86         }
 87         bool d = _p[dep] < p[dep];
 88         if (!son[d]) son[d] = new(_p)KD_tree;
 89         else son[d] -> insert(_p, !dep);
 90         update();
 91     }
 92  
 93     inline bool in(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2) {
 94         return x1 <= X1 && X2 <= x2 && y1 <= Y1 && Y2 <= y2;
 95     }
 96      
 97     inline bool out(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2) {
 98         return X2 < x1 || x2 < X1 || Y2 < y1 || y2 < Y1;
 99     }
100      
101     ll query(int x1, int y1, int x2, int y2) {
102         ll res = 0;
103         if (in(x1, y1, x2, y2, mn[0], mn[1], mx[0], mx[1])) return sum;
104         if (out(x1, y1, x2, y2, mn[0], mn[1], mx[0], mx[1])) return 0;
105         if (in(x1, y1, x2, y2, p[0], p[1], p[0], p[1])) res += p.v;
106         if (son[0]) res += son[0] -> query(x1, y1, x2, y2);
107         if (son[1]) res += son[1] -> query(x1, y1, x2, y2);
108         return res;
109     }
110 } *T;
111  
112 void work_add() {
113     static point p;
114     p.get();
115     if (!T) T = new(p)KD_tree;
116     else T -> insert(p, 0);
117 }
118  
119 inline void work_query() {
120     static int x1, y1, x2, y2;
121     x1 = read(), y1 = read(), x2 = read(), y2 = read();
122     if (!T) printf("%lld
", ans = 0);
123     else printf("%lld
", ans = T -> query(x1, y1, x2, y2));
124 }
125  
126 int main() {
127     int i, oper;
128     n = read(0), ans = 0;
129     while (1) {
130         oper = read(0);
131         if (oper == 1) work_add();
132         else if (oper == 2) work_query();
133         else break;
134     }
135     return 0;
136 }

View Code