POJ 3470 Walls 树上分桶

树上分桶"/>

POJ 3470 Walls 树上分桶

今天太晚了，代码先发上，思路明天说吧。

陌上花开，树上分桶

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
/*** 对于y1不等于y2的，可以用datC求解，对于x1不等于x2的，可以用datR求解* 因此需要结合datC和y1==y2的same，结合datR和x1==x2的same，才能求解问题*/
struct Same
{//_same是墙相等的那一个坐标，例如x1=x2，_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记录了x1==x2的墙，优先按照x1排序，其次按照y1排序，sameY记录了y1==y2的墙，优先按照y1排序，其次按照x1排序*/
Same sameX[50009], sameY[50009];
/*** sameX和sameY里元素的数量*/
int sameXLen, sameYLen;
typedef pair<int, int> P;
/*** 树上分桶的大小*/
const int B = 1500;
/***  x1不等于x2的墙，即水平方向，用R(row)表示，这个数组保存的是x2，用于统计x1<=x<=x2的个数*/
P **datR;
/*** y1不等于y2的墙，即竖直方向，用C(col)表示，这个数组保存的是y2，用于统计y1<=y<=y2的个数*/
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的墙分到了两颗树，所以用一个变量代表当前查询哪一颗树，如果isR==true，则查的datR，否则datl*/
bool isR;
/***让x1<=x2，y1<=y2*/
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;
}