BZOJ 2716: [Violet 3]天使玩偶/2648: SJY摆棋子

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
HINT
题解

Description

Input

Output

Sample Input

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

100 100

81 23

27 16

52 58

44 24

25 95

34 2

96 25

8 14

97 50

97 18

64 3

47 22

55 28

89 37

75 45

67 22

90 8

65 45

68 93

87 8

61 45

69 72

38 57

58 76

45 34

88 54

27 8

35 34

70 81

25 24

97 97

4 43

39 38

82 68

27 58

2 21

92 88

96 70

97 29

14 53

6 42

1 2

35 84

64 88

63 57

53 40

82 59

49 56

75 72

29 30

50 1

40 83

52 94

22 35

39 1

94 88

89 96

79 46

33 75

31 42

33 95

6 83

90 66

37 54

35 64

17 66

48 37

30 8

95 51

3 51

90 33

29 48

94 78

53 7

1 26

73 35

18 33

99 78

83 59

23 87

4 17

53 91

98 3

54 82

85 92

77 8

56 74

4 5

63 1

26 8

42 15

48 98

27 11

70 98

36 9

78 92

34 40

42 82

64 83

75 47

2 51 55

1 7 62

2 21 62

1 36 39

1 35 89

1 84 15

2 19 24

1 58 53

2 52 34

1 98 49

1 4 100

1 17 25

1 30 56

1 69 43

2 57 23

2 23 13

1 98 25

2 50 27

1 84 63

2 84 81

2 84 77

1 60 23

2 15 27

1 9 51

1 31 11

1 96 56

2 20 85

1 46 32

1 60 88

2 92 48

1 68 5

2 90 17

1 16 46

2 67 5

2 29 83

1 84 70

2 68 27

1 99 33

2 39 89

2 38 28

1 42 3

1 10 60

2 56 29

2 12 60

2 46 51

2 15 73

1 93 42

1 78 82

1 66 20

1 46 17

2 48 5

1 59 61

1 87 59

2 98 72

1 49 3

2 21 10

1 15 4

1 48 14

2 67 75

2 83 77

1 88 65

2 100 93

2 58 83

1 29 80

2 31 88

2 92 94

1 96 66

1 61 82

2 87 24

1 64 83

1 28 87

2 72 90

2 7 3

1 86 3

2 26 53

2 71 2

2 88 24

1 69 60

1 92 44

2 74 94

1 12 78

2 1 2

1 4 73

1 58 5

1 62 14

2 64 58

2 39 45

1 99 27

1 42 21

1 87 2

2 16 98

2 17 21

2 41 20

1 46 72

1 11 62

2 68 29

1 64 66

2 90 42

2 63 35

1 64 71

Sample Output

HINT

题解

还是K-DTree、、算是写一些模板题练练手吧！

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
const int Maxn=500010;
const int Maxm=500010;
const int Inf=2100000000;
int D;
struct KDTree{
    int lx,rx;
    int d[2],nm[2],nx[2];
    KDTree(){}
    KDTree(int x,int y){
        d[0]=nm[0]=nx[0]=x;
        d[1]=nm[1]=nx[1]=y;
        lx=rx=0;
    }
    friend bool operator<(KDTree a,KDTree b){
        return a.d[D]<b.d[D];
    }
};
KDTree tree[(Maxn+Maxm)*2];
KDTree chess[Maxn];
int nume;
int Root;
inline int remin(int a,int b){return (a<b?a:b);}
inline int remax(int a,int b){return (a>b?a:b);}
inline void update(int x){
    //printf("Update:(%d,%d)~(%d,%d)  ->n",tree[x].nm[0],tree[x].nm[1],tree[x].nx[0],tree[x].nx[1]);
    if (tree[x].lx){
        KDTree T=tree[tree[x].lx];
        //printf("       ->Left (%d,%d)~(%d,%d)n",T.nm[0],T.nm[1],T.nx[0],T.nx[1]);
        for (int i=0;i<2;i++){
            tree[x].nm[i]=remin(tree[x].nm[i],T.nm[i]);
            tree[x].nx[i]=remax(tree[x].nx[i],T.nx[i]);
        }
    }
    if (tree[x].rx){
        KDTree T=tree[tree[x].rx];
        //printf("       ->Right (%d,%d)~(%d,%d)n",T.nm[0],T.nm[1],T.nx[0],T.nx[1]);
        for (int i=0;i<2;i++){
            tree[x].nm[i]=remin(tree[x].nm[i],T.nm[i]);
            tree[x].nx[i]=remax(tree[x].nx[i],T.nx[i]);
        }
    }
    //printf("        ->(%d,%d)~(%d,%d)n",tree[x].nm[0],tree[x].nm[1],tree[x].nx[0],tree[x].nx[1]);
}
int build(int left,int right,int now){
    D=now;
    int mid=(left+right)/2;
    nth_element(chess+left,chess+mid,chess+right+1);
    tree[mid]=chess[mid];
    if (left<mid) tree[mid].lx=build(left,mid-1,now^1);
    if (mid<right) tree[mid].rx=build(mid+1,right,now^1);
    update(mid);
    return mid;
}
void insert(int &x,KDTree T,int now){
    if (!x){
        x=++nume;
        //printf("Insert (%d,%d)n",T.d[0],T.d[1]);
        tree[x]=T;
        return ;
    }else{
        if (tree[x].d[0]==T.d[0] && tree[x].d[1]==T.d[1]) return;
        if (T.d[now]<tree[x].d[now]){
            //printf("Insert (%d,%d)~(%d,%d) Left (%d,%d)n",tree[x].nm[0],tree[x].nm[1],tree[x].nx[0],tree[x].nx[1],T.d[0],T.d[1]);
            insert(tree[x].lx,T,now^1);
            //printf("Tree.Lx=%dn",tree[x].lx);
        }else{
            //printf("Insert (%d,%d)~(%d,%d) Right (%d,%d)n",tree[x].nm[0],tree[x].nm[1],tree[x].nx[0],tree[x].nx[1],T.d[0],T.d[1]);
            insert(tree[x].rx,T,now^1);
            //printf("Tree.Rx=%dn",tree[x].rx);
        }
        update(x);
    }
}
inline int abs(int x){return (x<0?-x:x);}
inline int getDist(KDTree T,int x,int y){return abs(T.d[0]-x)+abs(T.d[1]-y);}
inline int GetBase(int x,int x0,int y0){
    if (!x) return Inf;
    KDTree T=tree[x];
    int ret=0;
    int d[2];d[0]=x0;d[1]=y0;
    for (int i=0;i<2;i++){
        ret+=remax(0,T.nm[i]-d[i]);
        ret+=remax(0,d[i]-T.nx[i]);
    }
    //printf("GetBase:(%d,%d) -  (%d,%d)~(%d,%d) = %dn",x0,y0,T.nm[0],T.nm[1],T.nx[0],T.nx[1],ret);
    return ret;
}
int query(int x,int x0,int y0,int now){
    if (!x) return Inf;
    int Ret=getDist(tree[x],x0,y0);
    int Distl=GetBase(tree[x].lx,x0,y0),Distr=GetBase(tree[x].rx,x0,y0);
    if (Distl<Distr){
        if (Ret>Distl) Ret=remin(Ret,query(tree[x].lx,x0,y0,now^1));
        if (Ret>Distr) Ret=remin(Ret,query(tree[x].rx,x0,y0,now^1));
    }else{
        if (Ret>Distr) Ret=remin(Ret,query(tree[x].rx,x0,y0,now^1));
        if (Ret>Distl) Ret=remin(Ret,query(tree[x].lx,x0,y0,now^1));
    }
    //Ret=remin(Ret,query(tree[x].rx,x0,y0,now^1));
    //Ret=remin(Ret,query(tree[x].lx,x0,y0,now^1));
    return Ret;
}
int n,m;
int t,x,y;
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        chess[i]=KDTree(x,y);
    }
    Root=build(1,n,0);
    nume=n;
    for (int i=1;i<=m;i++){
        scanf("%d%d%d",&t,&x,&y);
        if (t==1){
            KDTree T=KDTree(x,y);
            //printf("Insert (%d,%d)n",x,y);
            insert(Root,T,0);
        }else{
            printf("%dn",query(Root,x,y,0));
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<string>

#include<cstring>

using namespace std;

const int Maxn=500010;

const int Maxm=500010;

const int Inf=2100000000;

int D;

struct KDTree{

int lx,rx;

int d[2],nm[2],nx[2];

KDTree(){}

KDTree(int x,int y){

d[0]=nm[0]=nx[0]=x;

d[1]=nm[1]=nx[1]=y;

lx=rx=0;

}

friend bool operator<(KDTree a,KDTree b){

return a.d[D]<b.d[D];

}

};

KDTree tree[(Maxn+Maxm)*2];

KDTree chess[Maxn];

int nume;

int Root;

inline int remin(int a,int b){return (a<b?a:b);}

inline int remax(int a,int b){return (a>b?a:b);}

inline void update(int x){

//printf("Update:(%d,%d)~(%d,%d) ->n",tree[x].nm[0],tree[x].nm[1],tree[x].nx[0],tree[x].nx[1]);

if (tree[x].lx){

KDTree T=tree[tree[x].lx];

//printf(" ->Left (%d,%d)~(%d,%d)n",T.nm[0],T.nm[1],T.nx[0],T.nx[1]);

for (int i=0;i<2;i++){

tree[x].nm[i]=remin(tree[x].nm[i],T.nm[i]);

tree[x].nx[i]=remax(tree[x].nx[i],T.nx[i]);

}

if (tree[x].rx){

KDTree T=tree[tree[x].rx];

//printf(" ->Right (%d,%d)~(%d,%d)n",T.nm[0],T.nm[1],T.nx[0],T.nx[1]);

for (int i=0;i<2;i++){

tree[x].nm[i]=remin(tree[x].nm[i],T.nm[i]);

tree[x].nx[i]=remax(tree[x].nx[i],T.nx[i]);

}

//printf(" ->(%d,%d)~(%d,%d)n",tree[x].nm[0],tree[x].nm[1],tree[x].nx[0],tree[x].nx[1]);

}

int build(int left,int right,int now){

D=now;

int mid=(left+right)/2;

nth_element(chess+left,chess+mid,chess+right+1);

tree[mid]=chess[mid];

if (left<mid) tree[mid].lx=build(left,mid-1,now^1);

if (mid<right) tree[mid].rx=build(mid+1,right,now^1);

update(mid);

return mid;

}

void insert(int &x,KDTree T,int now){

if (!x){

x=++nume;

//printf("Insert (%d,%d)n",T.d[0],T.d[1]);

tree[x]=T;

return ;

}else{

if (tree[x].d[0]==T.d[0] && tree[x].d[1]==T.d[1]) return;

if (T.d[now]<tree[x].d[now]){

//printf("Insert (%d,%d)~(%d,%d) Left (%d,%d)n",tree[x].nm[0],tree[x].nm[1],tree[x].nx[0],tree[x].nx[1],T.d[0],T.d[1]);

insert(tree[x].lx,T,now^1);

//printf("Tree.Lx=%dn",tree[x].lx);

}else{

//printf("Insert (%d,%d)~(%d,%d) Right (%d,%d)n",tree[x].nm[0],tree[x].nm[1],tree[x].nx[0],tree[x].nx[1],T.d[0],T.d[1]);

insert(tree[x].rx,T,now^1);

//printf("Tree.Rx=%dn",tree[x].rx);

}

update(x);

}

inline int abs(int x){return (x<0?-x:x);}

inline int getDist(KDTree T,int x,int y){return abs(T.d[0]-x)+abs(T.d[1]-y);}

inline int GetBase(int x,int x0,int y0){

if (!x) return Inf;

KDTree T=tree[x];

int ret=0;

int d[2];d[0]=x0;d[1]=y0;

for (int i=0;i<2;i++){

ret+=remax(0,T.nm[i]-d[i]);

ret+=remax(0,d[i]-T.nx[i]);

}

//printf("GetBase:(%d,%d) - (%d,%d)~(%d,%d) = %dn",x0,y0,T.nm[0],T.nm[1],T.nx[0],T.nx[1],ret);

return ret;

}

int query(int x,int x0,int y0,int now){

if (!x) return Inf;

int Ret=getDist(tree[x],x0,y0);

int Distl=GetBase(tree[x].lx,x0,y0),Distr=GetBase(tree[x].rx,x0,y0);

if (Distl<Distr){

if (Ret>Distl) Ret=remin(Ret,query(tree[x].lx,x0,y0,now^1));

if (Ret>Distr) Ret=remin(Ret,query(tree[x].rx,x0,y0,now^1));

}else{

if (Ret>Distr) Ret=remin(Ret,query(tree[x].rx,x0,y0,now^1));

if (Ret>Distl) Ret=remin(Ret,query(tree[x].lx,x0,y0,now^1));

}

//Ret=remin(Ret,query(tree[x].rx,x0,y0,now^1));

//Ret=remin(Ret,query(tree[x].lx,x0,y0,now^1));

return Ret;

}

int n,m;

int t,x,y;

int main(){

scanf("%d%d",&n,&m);

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

scanf("%d%d",&x,&y);

chess[i]=KDTree(x,y);

}

Root=build(1,n,0);

nume=n;

for (int i=1;i<=m;i++){

scanf("%d%d%d",&t,&x,&y);

if (t==1){

KDTree T=KDTree(x,y);

//printf("Insert (%d,%d)n",x,y);

insert(Root,T,0);

}else{

printf("%dn",query(Root,x,y,0));

}

return 0;

}

WNJXYKの博客

喂你脚下有坑