Vani原创 欢迎移步 OJ2648

  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4   5 inline int nextChar(void) {  6     const int siz = 1024;  7     static char buf[siz];  8     static char *hd = buf + siz;  9     static char *tl = buf + siz; 10     if (hd == tl) 11         fread(hd = buf, 1, siz, stdin); 12     return int(*hd++); 13 } 14  15 inline int nextInt(void) { 16     register int ret = 0; 17     register int neg = false; 18     register int bit = nextChar(); 19     for (; bit < 48; bit = nextChar()) 20         if (bit == ‘-‘)neg ^= true; 21     for (; bit > 47; bit = nextChar()) 22         ret = ret * 10 + bit - 48; 23     return neg ? -ret : ret; 24 } 25  26 const int lim = 1000001; 27 const int siz = 1000005; 28 const int inf = 1000000007; 29  30 int n, m; 31  32 struct data { 33     int k, x, y, t, p; 34     inline friend bool operator <  35     (const data &a, const data &b) { 36         if (a.x != b.x) 37             return a.x < b.x; 38         else 39             return a.k < b.k; 40     } 41 }p[siz], s[siz], q[siz]; 42  43 int ans[siz]; 44  45 int now; 46 int bit[siz]; 47 int tim[siz]; 48  49 inline void add(int t, int k) { 50     for (; t < siz; t += t&-t) 51         if (bit[t] < k || tim[t] != now) 52             bit[t] = k, tim[t] = now; 53 } 54  55 inline int ask(int t) { 56     int ret = -inf; 57     for (; t; t -= t&-t) 58         if (ret < bit[t] && tim[t] == now) 59             ret = bit[t]; 60     return ret; 61 } 62  63 void cdqSolve(int l, int r) { 64     if (l >= r)return; 65      66     int mid = (l + r) >> 1; 67      68     cdqSolve(l, mid); 69     cdqSolve(mid + 1, r); 70      71     int t1 = l, t2 = mid + 1, tot = l; 72      73     while (t1 <= mid && t2 <= r) { 74         if (s[t1] < s[t2]) 75             q[tot++] = s[t1++]; 76         else 77             q[tot++] = s[t2++]; 78     } 79      80     while (t1 <= mid) 81         q[tot++] = s[t1++]; 82          83     while (t2 <= r) 84         q[tot++] = s[t2++]; 85          86     for (int i = l; i <= r; ++i) 87         s[i] = q[i]; 88      89     ++now; 90      91     for (int i = l; i <= r; ++i) 92         if (s[i].k && s[i].t > mid) { 93             int tmp = s[i].x + s[i].y - ask(s[i].y); 94             if (ans[s[i].p] > tmp) 95                 ans[s[i].p] = tmp; 96         } 97         else if (!s[i].k && s[i].t <= mid) 98             add(s[i].y, s[i].x + s[i].y); 99 }100 101 inline void cdqSolve1(void) {102     memcpy(s, p, sizeof(s));103     cdqSolve(1, n + m);104 }105 106 inline void cdqSolve2(void) {107     memcpy(s, p, sizeof(s));108     for (int i = 1; i <= n + m; ++i)109         s[i].x = lim - s[i].x;110     cdqSolve(1, n + m);111 }112 113 inline void cdqSolve3(void) {114     memcpy(s, p, sizeof(s));115     for (int i = 1; i <= n + m; ++i)116         s[i].y = lim - s[i].y;117     cdqSolve(1, n + m);118 }119 120 inline void cdqSolve4(void) {121     memcpy(s, p, sizeof(s));122     for (int i = 1; i <= n + m; ++i)123         s[i].x = lim - s[i].x,124         s[i].y = lim - s[i].y;125     cdqSolve(1, n + m);126 }127 128 signed main(void) {129 //    freopen("in", "r", stdin);130 //    freopen("out", "w", stdout);131     132     n = nextInt();133     m = nextInt();134     135     for (int i = 1; i <= n; ++i) {136         p[i].x = nextInt();137         p[i].y = nextInt();138         p[i].k = 0;139         p[i].t = i;140     }141     142     for (int i = 1; i <= m; ++i) {143         p[i + n].k = nextInt() - 1;144         p[i + n].x = nextInt();145         p[i + n].y = nextInt();146         p[i + n].t = i + n;147         p[i + n].p = i;148     }149     150     for (int i = 1; i <= m; ++i)151         ans[i] = inf;152     153     cdqSolve1();154     cdqSolve2();155     cdqSolve3();156     cdqSolve4();157     158     for (int i = 1; i <= m; ++i)159         if (p[i + n].k)printf("%d\n", ans[i]);160 }