怀化网站建设公司,网站SEO建设,汕头小程序开发,网站优化方法页面今天太晚了#xff0c;代码先发上#xff0c;思路明天说吧。
陌上花开#xff0c;树上分桶
#include iostream
#include algorithm
#include vector
using namespace std;
/*** 对于y1不等于y2的#xff0c;可以用datC求解#xff0c;对于x1不等…今天太晚了代码先发上思路明天说吧。
陌上花开树上分桶
#include iostream
#include algorithm
#include vector
using namespace std;
/*** 对于y1不等于y2的可以用datC求解对于x1不等于x2的可以用datR求解* 因此需要结合datC和y1y2的same结合datR和x1x2的same才能求解问题*/
struct Same
{//_same是墙相等的那一个坐标例如x1x2_other是墙不相等的那一个坐标例如y1,_idx是墙的下标int _same, _other, _idx;Same(int _same 0, int _other 0, int _idx 0) : _same(_same), _other(_other), _idx(_idx) {}
};
bool compareSame(const Same a, const Same b)
{// 如果相等元素相同则按照相同元素排if (a._same ! b._same){return a._same b._same;}// 如果相同元素不同则按照不同元素排else{return a._other b._other;}
}
/*** sameX记录了x1x2的墙优先按照x1排序其次按照y1排序sameY记录了y1y2的墙优先按照y1排序其次按照x1排序*/
Same sameX[50009], sameY[50009];
/*** sameX和sameY里元素的数量*/
int sameXLen, sameYLen;
typedef pairint, int P;
/*** 树上分桶的大小*/
const int B 1500;
/*** x1不等于x2的墙即水平方向用R(row)表示这个数组保存的是x2用于统计x1xx2的个数*/
P **datR;
/*** y1不等于y2的墙即竖直方向用C(col)表示这个数组保存的是y2用于统计y1yy2的个数*/
P **datC;
/*** bktR[i]是对datR[i]的分桶*/
P ***bktR;
int **bktRSize;
/*** bktC[i]是对datC[i]的分桶*/
P ***bktC;
int **bktCSize;
/*** 输入*/
int x1[50009], x2[50009], y1[50009], y2[50009], x[50009], y[50009], n, m;
/*** 把x1!x2的墙都放在row里保存并按照x1排序把y1!y2的墙度放在col里保存并按照y1排序*/
P row[50009], col[50009];
/*** rowLen是row数组里元素的数量,colLen是col数组里元素的数量*/
int rowLen, colLen, bktRLen[131072], bktCLen[131072];
/***因为我们把x1!x2和y1!y2的墙分到了两颗树所以用一个变量代表当前查询哪一颗树如果isRtrue则查的datR否则datl*/
bool isR;
/***让x1x2y1y2*/
void swapIfNeed(int i)
{int tmp;if (y1[i] y2[i]){tmp y1[i];y1[i] y2[i];y2[i] tmp;}if (x1[i] x2[i]){tmp x1[i];x1[i] x2[i];x2[i] tmp;}
}
void input()
{scanf(%d%d, n, m);rowLen 0, colLen 0, sameXLen 0, sameYLen 0;for (int i 0; i n; i){scanf(%d%d%d%d, x1[i], y1[i], x2[i], y2[i]);swapIfNeed(i);if (x1[i] ! x2[i]){row[rowLen].first x1[i];row[rowLen].second i;rowLen;}if (y1[i] ! y2[i]){col[colLen].first y1[i];col[colLen].second i;colLen;}if (x1[i] x2[i]){sameX[sameXLen]._same x1[i];sameX[sameXLen]._other y1[i];sameX[sameXLen]._idx i;sameXLen;}if (y1[i] y2[i]){sameY[sameYLen]._same y1[i];sameY[sameYLen]._other x1[i];sameY[sameYLen]._idx i;sameYLen;}}for (int i 0; i m; i){scanf(%d%d, x[i], y[i]);}
}
void sortAll()
{sort(sameX, sameX sameXLen, compareSame);sort(sameY, sameY sameYLen, compareSame);sort(row, row rowLen);sort(col, col colLen);
}
void buildBkt(int i, int size)
{int len size / B;if (size % B ! 0){len;}if (isR){bktR[i] new P *[len];bktRSize[i] new int[len];bktRLen[i] len;}else{bktC[i] new P *[len];bktCSize[i] new int[len];bktCLen[i] len;}for (int j 0; j len; j){if (j 1 len){if (isR){bktR[i][j] new P[size - (B * j)];bktRSize[i][j] size - (B * j);}else{bktC[i][j] new P[size - (B * j)];bktCSize[i][j] size - (B * j);}}else{if (isR){bktR[i][j] new P[B];bktRSize[i][j] B;}else{bktC[i][j] new P[B];bktCSize[i][j] B;}}}for (int j 0; j size; j){if (isR){bktR[i][j / B][j - ((j / B) * B)].first y1[datR[i][j].second];bktR[i][j / B][j - ((j / B) * B)].second datR[i][j].second;}else{bktC[i][j / B][j - ((j / B) * B)].first x1[datC[i][j].second];bktC[i][j / B][j - ((j / B) * B)].second datC[i][j].second;}}for (int j 0; j len; j){if (isR){sort(bktR[i][j], bktR[i][j] bktRSize[i][j]);}else{sort(bktC[i][j], bktC[i][j] bktCSize[i][j]);}}
}
/*** 构建线段树*/
void buildDat(int i, int l, int r)
{if (r - l 1){// 如果目前是操作的datRif (isR){datR[i] new P[1];datR[i][0].first x2[row[l].second];datR[i][0].second row[l].second;}else{datC[i] new P[1];datC[i][0].first y2[col[l].second];datC[i][0].second col[l].second;}}else{int lch i * 2 1;int rch i * 2 2;int mid (l r) / 2;buildDat(lch, l, mid);buildDat(rch, mid, r);if (isR){datR[i] new P[r - l];merge(datR[lch], datR[lch] (mid - l), datR[rch], datR[rch] (r - mid), datR[i]);}else{datC[i] new P[r - l];merge(datC[lch], datC[lch] (mid - l), datC[rch], datC[rch] (r - mid), datC[i]);}}buildBkt(i, r - l);
}
/*** ans数组用来存放第i面墙被撞的次数ansIdx[i]用来存放第i只小鸟撞到的墙,ansLen用来存放第i只小鸟撞到的墙的数量ansDist存放第i只小鸟距墙的最近距离*/
int ans[50009], ansIdx[50009][10], ansLen[500009], ansDist[50009];
/*** _x,_y代表当前小鸟的位置_current代表它的下标*/
int _x, _y, _current;
void updateAns(int dist, int idx)
{if (ansDist[_current] 0 || ansDist[_current] dist){ansIdx[_current][ansLen[_current]] idx;ansLen[_current] ansLen[_current] 1;ansDist[_current] dist;}else if (ansDist[_current] dist){ansLen[_current] 0;ansIdx[_current][ansLen[_current]] idx;ansLen[_current] ansLen[_current] 1;ansDist[_current] dist;}
}
void handleNode(int i, int l, int r)
{int size r - l;P tmp;int idx, dist, bktSize;if (isR){tmp P(_x, -0x3f3f3f3f);idx lower_bound(datR[i], datR[i] size, tmp) - datR[i];bktSize bktRLen[i];}else{tmp P(_y, -0x3f3f3f3f);idx lower_bound(datC[i], datC[i] size, tmp) - datC[i];bktSize bktCLen[i];}if (idx size){return;}int firstBkt (idx B - 1) / B;for (int j idx; j min(size, firstBkt * B); j){if (isR){dist abs(y1[datR[i][j].second] - _y);updateAns(dist, datR[i][j].second);}else{dist abs(x1[datC[i][j].second] - _x);updateAns(dist, datC[i][j].second);}}for (int j firstBkt; j bktSize; j){if (isR){tmp.first _y;idx lower_bound(bktR[i][j], bktR[i][j] bktRSize[i][j], tmp) - bktR[i][j];if (idx bktRSize[i][j]){dist abs(bktR[i][j][idx].first - _y);updateAns(dist, bktR[i][j][idx].second);}idx--;if (idx 0){dist abs(bktR[i][j][idx].first - _y);updateAns(dist, bktR[i][j][idx].second);}}else{tmp.first _x;idx lower_bound(bktC[i][j], bktC[i][j] bktCSize[i][j], tmp) - bktC[i][j];if (idx bktCSize[i][j]){dist abs(bktC[i][j][idx].first - _x);updateAns(dist, bktC[i][j][idx].second);}idx--;if (idx 0){dist abs(bktC[i][j][idx].first - _x);updateAns(dist, bktC[i][j][idx].second);}}}
}
void query(int _l, int _r, int i, int l, int r)
{if (_l r || _r l){}else if (l _l r _r){handleNode(i, l, r);}else{query(_l, _r, i * 2 1, l, (l r) / 2);query(_l, _r, i * 2 2, (l r) / 2, r);}
}
void solveSame()
{int idx, dist;Same tmp;if (isR){tmp Same(_x, _y, -0x3f3f3f3f);idx lower_bound(sameX, sameX sameXLen, tmp, compareSame) - sameX;if (idx sameXLen sameX[idx]._same _x){dist sameX[idx]._other - _y;updateAns(dist, sameX[idx]._idx);}idx--;if (idx 0 sameX[idx]._same _x){dist _y - y2[sameX[idx]._idx];updateAns(dist, sameX[idx]._idx);}}else{tmp Same(_y, _x, -0x3f3f3f3f);idx lower_bound(sameY, sameY sameYLen, tmp, compareSame) - sameY;if (idx sameYLen sameY[idx]._same _y){dist sameY[idx]._other - _x;updateAns(dist, sameY[idx]._idx);}idx--;if (idx 0 sameY[idx]._same _y){dist _x - x2[sameY[idx]._idx];updateAns(dist, sameY[idx]._idx);}}
}
void solve(int i)
{_x x[i], _y y[i], _current i;solveSame();int idx;P tmp;if (isR rowLen 0){tmp P(_x, 0x3f3f3f3f);idx upper_bound(row, row rowLen, tmp) - row;if (idx 0){return;}query(0, idx, 0, 0, rowLen);}else if (colLen 0){tmp P(_y, 0x3f3f3f3f);idx upper_bound(col, col colLen, tmp) - col;if (idx 0){return;}query(0, idx, 0, 0, colLen);}
}
void putAns()
{for (int i 0; i m; i){for (int j 0; j ansLen[i]; j){ans[ansIdx[i][j]];}}for (int i 0; i n; i){printf(%d\n, ans[i]);}
}
int calcSize(int _size)
{int size 1;while (size _size){size size * 2;}return size * 2 - 1;
}
int main()
{input();sortAll();isR true;if (rowLen 0){datR new P *[calcSize(rowLen)];bktR new P **[calcSize(rowLen)];bktRSize new int *[calcSize(rowLen)];buildDat(0, 0, rowLen);}isR false;if (colLen 0){datC new P *[calcSize(colLen)];bktC new P **[calcSize(colLen)];bktCSize new int *[calcSize(colLen)];buildDat(0, 0, colLen);}for (int i 0; i m; i){isR true;solve(i);isR false;solve(i);}putAns();return 0;
}
