luogu P4169 天使玩偶

传送门

卡常神题

(话说正解好像是KDTree)

不管反正离线

考虑四个方向一个一个做

显然最好做的是左下套个三维偏序然后树状数组改成维护最大值就行

注意清零的时候的写法

然后四个方向分别做转一下

卡常卡不过

用了一个优化就是转完之后CDQ之前把不在左下的点删掉

开的O2 等学了KDTree再来卡

Code:

 1 // luogu-judger-enable-o2
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<vector>
 7 #include<iostream>
 8 #include<algorithm>
 9 #define itn int
10 #define ms(a,b) memset(a,b,sizeof a)
11 #define rep(i,a,n) for(int i = a;i <= n;i++)
12 #define per(i,n,a) for(int i = n;i >= a;i--)
13 #define inf 2147483647
14 using namespace std;
15 typedef long long ll;
16 ll read() {
17     ll as = 0,fu = 1;
18     char c = getchar();
19     while(c < '0' || c > '9') {
20         if(c == '-') fu = -1;
21         c = getchar();
22     }
23     while(c >= '0' && c <= '9') {
24         as = as * 10 + c - '0';
25         c = getchar();
26     }
27     return as * fu;
28 }
29 //head
30 const int N = 1000010;
31 const int M = 1000105;
32 int n,X,Y,T;
33 struct node {
34     int x,y,tim;
35 } a[N],b[N],tmp[N];
36 int t[M],ans[N];
37 inline void upd(int x,int k) {
38     for(int i = x;i < M;i += (i & (-i))) t[i] = max(t[i],k);
39 }
40 inline int qry(int x) {
41     int sum = 0;
42     for(int i = x;i;i -= (i & (-i))) sum = max(sum,t[i]);
43     return sum;
44 }
45 inline void clr(int x) {
46     for(int i = x;i < M;i += (i & (-i))) t[i] = 0;
47 }
48 
49 void CDQ(int l,int r) {
50     if(l == r) return;
51     int m = l+r >> 1;
52     CDQ(l,m),CDQ(m+1,r);
53     int p1 = l,p2 = m+1;
54     rep(i,l,r) {
55         if(p1 <= m && (p2 > r || a[p1].x <= a[p2].x)) {
56             tmp[i] = a[p1++];
57             if(!tmp[i].tim) upd(tmp[i].y,tmp[i].x + tmp[i].y);
58         } else {
59             tmp[i] = a[p2++];
60             if(!tmp[i].tim) continue;
61             int k = qry(tmp[i].y);
62             if(k) ans[tmp[i].tim] = min(ans[tmp[i].tim],tmp[i].x + tmp[i].y - k);
63         }
64     }
65     rep(i,l,m) if(!a[i].tim) clr(a[i].y);
66     rep(i,l,r) a[i] = tmp[i];
67 }
68 int maxx,maxy,cnt;
69 void Del() {
70     maxx = maxy = cnt = 0;
71     rep(i,1,n) if(a[i].tim) maxx = max(maxx,a[i].x),maxy = max(maxy,a[i].y);
72     rep(i,1,n) if(a[i].x <= maxx && a[i].y <= maxy) tmp[++cnt] = a[i];
73     rep(i,1,cnt) a[i] = tmp[i];
74 }
75 
76 int main() {
77     ms(ans,0x3f);
78     X = read(),Y = read();
79     rep(i,1,X) b[++n].x = read() + 1,b[n].y = read() + 1;
80     rep(i,1,Y) {
81         int op = read() - 1;
82         b[++n].x = read() + 1,b[n].y = read() + 1;
83         b[n].tim = op ? ++T : 0;
84     }
85     rep(i,1,n) a[i] = b[i];
86     Del(),CDQ(1,cnt);
87     rep(i,1,n) a[i] = b[i],a[i].y = N - b[i].y;
88     Del(),CDQ(1,cnt);
89     rep(i,1,n) a[i] = b[i],a[i].x = N - b[i].x,a[i].y = N - b[i].y;
90     Del(),CDQ(1,cnt);
91     rep(i,1,n) a[i] = b[i],a[i].x = N - b[i].x;
92     Del(),CDQ(1,cnt);
93     rep(i,1,T) printf("%d
",ans[i]);
94     return 0;
95 }