• POJ 3470 Walls 树上分桶

    一、题目大意

    我们有n面围墙，这些围墙高度无限！从一架飞机向下看，就像一条条线段一般！我们做些实验，有m只小鸟，它们会不断的飞直到碰撞围墙！确保每一只小鸟放下来，它一定会撞到围墙，而且它会朝着最快撞到围墙的方向去飞，题目保证每只小鸟的四个方向里，只有一个方向是最近的

    然后题目最后需要我们输出，每一面墙被小鸟撞过的次数

    题目中的墙都是与坐标轴垂直的，一定为竖直方向，或水平方向。

    n最大可以达到50000，m最大也可以达到50000，限定时间6秒钟！

    题目不会一开始就把小鸟放在墙上

    二、解题思路

    思考这样的一个问题，我们可以对墙分开考虑，这里我假设 x1<=x2 ,y1 <= y2

    情况1、对于水平方向的墙，x1 != x2,y1 == y2，那么根据小鸟的位置 x y，当x1<= x <=x2时，这面墙是一定可以够得到的！然后到这面墙的距离就是 |y1 - y|

    情况2、对于竖直方向的墙，x1 == x2，y1 != y2，那么根据愤怒的小鸟的位置，当 y1 <= y <= y2时，这面墙也一定够的到吧！距离是 |x1 - x|

    然后水平和墙和竖直的墙都考虑到了，那么还可能存在这面墙就与 小鸟在同一行或者同一列的情况。

    情况3、与小鸟在用一列的墙 x1 == x2 == x，然后 y2 < y 或者 y1 > y，这种的话，对于 y2 < y的，y - y2就是它的距离，对于 y1 > y 的，y1 - y 就是它的距离。

    情况4、与小鸟在同一行的墙，y1 == y2 == x，然后 x2 < x 或者 x1 > x，这种的话，对于x2 < x的墙，x - x2是它的距离，对于x1 > x的墙，x1 - x是它的距离。

    然后有i可能存在一只小鸟撞多个墙的情况，但是我觉得最多只撞的到2面墙，从题目大意上看，墙的高度无限，是不会有重合的，唯一的重合就是竖直与水平相交！而小鸟撞多个墙的情况，就是它撞到了这个交点，所以撞到2面墙，见下图！

    针对情况1，我们把x1 != x2的墙都记录下来，根据x1排序放到row数组，然后按2048的大小进行分桶，每个桶内按 x2排序，然后针对每个桶的数组，建立一颗线段树（归并树）树上的每个节点按照 y1 排序，针对每次 x y，首先二分 row数组，找到 x1<=x的区间，确定涉及到的桶，在桶内二分找到 x2 >= x的区间，然后去线段树上查出这些区间里最接近 y 的 y1，并用abs(y - y1)更新结果。对于桶外的元素（不超过2048）那就去row数组一个个判断了，如果 x2>=x那么用abs(y - y1)更新结果即可。

    针对情况2，我们把y1 != y2的墙都记录下来，根据y1排序放在col数组，然后按2048的大小进行分桶，每个桶内按 y2排序。针对每个桶的数组，建立一颗线段树（归并树）树上每个节点按照y1排序，针对每次x y，首先二分col数组，找到y1<=y的区间，确定涉及到的桶，在桶内二分找到y2>=y的区间，然后去线段树上查出这些区间里最接近x的x1，并用abs(x - x1)更新结果。对于桶外的元素（不超过2048）那就去col数组一个个判断了，如果y2>=y那就用abs(x - x1)更新结果即可。

    针对情况3，我们可以把x1 == x2的墙，放在数组里，然后优先根据 x1 排序，对x1相同的，根据 y1 排序，这样我们根据小鸟的位置 x y ，只需要把它传进去数组二分得到idx，然后判断idx的位置 x1是不是与 x相等，是的话，距离是 y1 - y（lower_bound得到的是第一个不小于的到idx，则idx要么x1==x且y1>=y，要么x1>x），判断下这个距离是不是最近的，然后idx--，再判断idx的位置是不是x1与x相等，是的话，用 y - y2更新结果

    针对情况4，我们可以把y1 == y2的墙，放在数组里，优先根据 y1 排序，对于 y1 相同的，根据 x1 排序，然后也是把 x 和 y传进来，去二分得到idx，判断 idx位置的y1==y?，若相等，则 判断距离 x1 - x更新结果，再判断idx-1位置的y1==y?，若相等，用 x - x2更新结果。

    需要注意的一点是，我在使用vector建树的时候超时了，最好不用vector，用指针。

    三、桶上分树代码

    1. #include 
    2. #include 
    3. using namespace std;
    4. struct Same
    5. {
    6.     int _same, _other, _idx;
    7.     Same(int _same = 0, int _other = 0, int _idx = 0) : _same(_same), _other(_other), _idx(_idx) {}
    8. };
    9. bool compareSame(const Same &a, const Same &b)
    10. {
    11.     return a._same != b._same ? a._same < b._same : a._other < b._other;
    12. }
    13. Same sameX[50009], sameY[50009];
    14. int sameXSize, sameYSize;
    15. const int B = 2048;
    16. typedef pair<int, int> P;
    17. int rowSize, colSize;
    18. P row[50009], col[50009], bktR[27][2057], bktC[27][2057];
    19. // P datR[27][100][100], datC[27][100][100];
    20. P **datR[27], **datC[27];
    21. int x[50009], y[50009], x1[50009], x2[50009], y1[50009], y2[50009], n, m;
    22. void swapIfNeed(int i)
    23. {
    24.     int tmp;
    25.     if (x1[i] > x2[i])
    26.     {
    27.         tmp = x1[i];
    28.         x1[i] = x2[i];
    29.         x2[i] = tmp;
    30.     }
    31.     if (y1[i] > y2[i])
    32.     {
    33.         tmp = y1[i];
    34.         y1[i] = y2[i];
    35.         y2[i] = tmp;
    36.     }
    37. }
    38. void input()
    39. {
    40.     rowSize = 0, colSize = 0, sameXSize = 0, sameYSize = 0;
    41.     scanf("%d%d", &n, &m);
    42.     for (int i = 0; i < n; i++)
    43.     {
    44.         scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
    45.         swapIfNeed(i);
    46.         if (x1[i] != x2[i])
    47.         {
    48.             row[rowSize].first = x1[i];
    49.             row[rowSize].second = i;
    50.             rowSize++;
    51.         }
    52.         if (y1[i] != y2[i])
    53.         {
    54.             col[colSize].first = y1[i];
    55.             col[colSize].second = i;
    56.             colSize++;
    57.         }
    58.         if (x1[i] == x2[i])
    59.         {
    60.             sameX[sameXSize]._same = x1[i];
    61.             sameX[sameXSize]._other = y1[i];
    62.             sameX[sameXSize]._idx = i;
    63.             sameXSize++;
    64.         }
    65.         if (y1[i] == y2[i])
    66.         {
    67.             sameY[sameYSize]._same = y1[i];
    68.             sameY[sameYSize]._other = x1[i];
    69.             sameY[sameYSize]._idx = i;
    70.             sameYSize++;
    71.         }
    72.     }
    73.     for (int i = 0; i < m; i++)
    74.     {
    75.         scanf("%d%d", &x[i], &y[i]);
    76.     }
    77. }
    78. void sortAll()
    79. {
    80.     sort(row, row + rowSize);
    81.     sort(col, col + colSize);
    82.     sort(sameX, sameX + sameXSize, compareSame);
    83.     sort(sameY, sameY + sameYSize, compareSame);
    84. }
    85. void build(int idx, int i, int l, int r, bool isR)
    86. {
    87.     if (r - l == 1)
    88.     {
    89.         if (isR)
    90.         {
    91.             datR[idx][i] = new P[1];
    92.             datR[idx][i][0].first = y1[bktR[idx][l].second];
    93.             datR[idx][i][0].second = bktR[idx][l].second;
    94.         }
    95.         else
    96.         {
    97.             datC[idx][i] = new P[1];
    98.             datC[idx][i][0].first = x1[bktC[idx][l].second];
    99.             datC[idx][i][0].second = bktC[idx][l].second;
    100.         }
    101.     }
    102.     else
    103.     {
    104.         int lch = i * 2 + 1;
    105.         int rch = i * 2 + 2;
    106.         int mid = (l + r) / 2;
    107.         build(idx, lch, l, mid, isR);
    108.         build(idx, rch, mid, r, isR);
    109.         if (isR)
    110.         {
    111.             datR[idx][i] = new P[r - l];
    112.             merge(datR[idx][lch], datR[idx][lch] + (mid - l), datR[idx][rch], datR[idx][rch] + (r - mid), datR[idx][i]);
    113.         }
    114.         else
    115.         {
    116.             datC[idx][i] = new P[r - l];
    117.             merge(datC[idx][lch], datC[idx][lch] + (mid - l), datC[idx][rch], datC[idx][rch] + (r - mid), datC[idx][i]);
    118.         }
    119.     }
    120. }
    121. int calcSize(int _size)
    122. {
    123.     int size = 1;
    124.     while (size < _size)
    125.     {
    126.         size = size * 2;
    127.     }
    128.     return size * 2 - 1;
    129. }
    130. void buckedMethod()
    131. {
    132.     for (int i = 0; i < rowSize; i++)
    133.     {
    134.         bktR[i / B][i - ((i / B) * B)].first = x2[row[i].second];
    135.         bktR[i / B][i - ((i / B) * B)].second = row[i].second;
    136.     }
    137.     for (int i = 0; i < rowSize; i = i + B)
    138.     {
    139.         int bucketR = i + B;
    140.         bucketR = (bucketR > rowSize ? rowSize : bucketR);
    141.         sort(bktR[i / B], bktR[i / B] + (bucketR - i));
    142.         int size = calcSize(bucketR - i);
    143.         datR[i / B] = new P *[size];
    144.         build(i / B, 0, 0, (bucketR - i), true);
    145.     }
    146.     for (int i = 0; i < colSize; i++)
    147.     {
    148.         bktC[i / B][i - ((i / B) * B)].first = y2[col[i].second];
    149.         bktC[i / B][i - ((i / B) * B)].second = col[i].second;
    150.     }
    151.     for (int i = 0; i < colSize; i = i + B)
    152.     {
    153.         int bucketR = i + B;
    154.         bucketR = (bucketR > colSize ? colSize : bucketR);
    155.         sort(bktC[i / B], bktC[i / B] + (bucketR - i));
    156.         int size = calcSize(bucketR - i);
    157.         datC[i / B] = new P *[size];
    158.         build(i / B, 0, 0, (bucketR - i), false);
    159.     }
    160. }
    161. int ansIdx[50009][10], ans[50009], ansLen[50009], ansDist[50009], _current;
    162. void updateAns(int dist, int idx)
    163. {
    164.     if (ansDist[_current] == 0 || ansDist[_current] == dist)
    165.     {
    166.         ansIdx[_current][ansLen[_current]] = idx;
    167.         ansLen[_current] = ansLen[_current] + 1;
    168.         ansDist[_current] = dist;
    169.     }
    170.     if (ansDist[_current] > dist)
    171.     {
    172.         ansLen[_current] = 0;
    173.         ansIdx[_current][ansLen[_current]] = idx;
    174.         ansLen[_current] = ansLen[_current] + 1;
    175.         ansDist[_current] = dist;
    176.     }
    177. }
    178. void handleSame(Same current, int size, bool isR)
    179. {
    180.     if (size <= 0)
    181.     {
    182.         return;
    183.     }
    184.     int idx;
    185.     if (isR)
    186.     {
    187.         idx = lower_bound(sameX, sameX + size, current, compareSame) - sameX;
    188.     }
    189.     else
    190.     {
    191.         idx = lower_bound(sameY, sameY + size, current, compareSame) - sameY;
    192.     }
    193.     if (isR)
    194.     {
    195.         if (idx < size && sameX[idx]._same == current._same)
    196.         {
    197.             updateAns(sameX[idx]._other - current._other, sameX[idx]._idx);
    198.         }
    199.         idx--;
    200.         if (idx >= 0 && sameX[idx]._same == current._same)
    201.         {
    202.             updateAns(current._other - y2[sameX[idx]._idx], sameX[idx]._idx);
    203.         }
    204.     }
    205.     else
    206.     {
    207.         if (idx < size && sameY[idx]._same == current._same)
    208.         {
    209.             updateAns(sameY[idx]._other - current._other, sameY[idx]._idx);
    210.         }
    211.         idx--;
    212.         if (idx >= 0 && sameY[idx]._same == current._same)
    213.         {
    214.             updateAns(current._other - x2[sameY[idx]._idx], sameY[idx]._idx);
    215.         }
    216.     }
    217. }
    218. void handleTreeNode(P current, int bkt, int tree, int size, bool isR)
    219. {
    220.     int idx;
    221.     if (isR)
    222.     {
    223.         idx = lower_bound(datR[bkt][tree], datR[bkt][tree] + size, current) - datR[bkt][tree];
    224.     }
    225.     else
    226.     {
    227.         idx = lower_bound(datC[bkt][tree], datC[bkt][tree] + size, current) - datC[bkt][tree];
    228.     }
    229.     for (int i = idx - 1; i <= idx; i++)
    230.     {
    231.         if (i >= 0 && i < size)
    232.         {
    233.             if (isR)
    234.             {
    235.                 updateAns(abs(datR[bkt][tree][i].first - current.first), datR[bkt][tree][i].second);
    236.             }
    237.             else
    238.             {
    239.                 updateAns(abs(datC[bkt][tree][i].first - current.first), datC[bkt][tree][i].second);
    240.             }
    241.         }
    242.     }
    243. }
    244. void queryTree(P current, int bkt, int _l, int _r, int i, int l, int r, bool isR)
    245. {
    246.     if (_l >= r || _r <= l)
    247.     {
    248.     }
    249.     else if (l >= _l && r <= _r)
    250.     {
    251.         handleTreeNode(current, bkt, i, r - l, isR);
    252.     }
    253.     else
    254.     {
    255.         queryTree(current, bkt, _l, _r, i * 2 + 1, l, (l + r) / 2, isR);
    256.         queryTree(current, bkt, _l, _r, i * 2 + 2, (l + r) / 2, r, isR);
    257.     }
    258. }
    259. void handleBucket(int size, int first, int second, bool isR)
    260. {
    261.     if (size <= 0)
    262.     {
    263.         return;
    264.     }
    265.     int limit;
    266.     if (isR)
    267.     {
    268.         limit = upper_bound(row, row + size, P(first, 0x3f3f3f3f)) - row;
    269.     }
    270.     else
    271.     {
    272.         limit = upper_bound(col, col + size, P(first, 0x3f3f3f3f)) - col;
    273.     }
    274.     if (limit <= 0)
    275.     {
    276.         return;
    277.     }
    278.     for (int i = 0; i < size; i = i + B)
    279.     {
    280.         int bucketL = i;
    281.         int bucketR = i + B;
    282.         bucketR = (bucketR > size ? size : bucketR);
    283.         if (bucketL >= limit)
    284.         {
    285.             break;
    286.         }
    287.         if (bucketR <= limit)
    288.         {
    289.             int idx;
    290.             if (isR)
    291.             {
    292.                 idx = lower_bound(bktR[i / B], bktR[i / B] + (bucketR - bucketL), P(first, -0x3f3f3f3f)) - bktR[i / B];
    293.             }
    294.             else
    295.             {
    296.                 idx = lower_bound(bktC[i / B], bktC[i / B] + (bucketR - bucketL), P(first, -0x3f3f3f3f)) - bktC[i / B];
    297.             }
    298.             if (idx < (bucketR - bucketL))
    299.             {
    300.                 queryTree(P(second, -0x3f3f3f3f), i / B, idx, (bucketR - bucketL), 0, 0, (bucketR - bucketL), isR);
    301.             }
    302.             continue;
    303.         }
    304.         for (int j = bucketL; j < limit; j++)
    305.         {
    306.             int need;
    307.             if (isR)
    308.             {
    309.                 need = x2[row[j].second];
    310.             }
    311.             else
    312.             {
    313.                 need = y2[col[j].second];
    314.             }
    315.             if (need >= first)
    316.             {
    317.                 if (isR)
    318.                 {
    319.                     updateAns(abs(y1[row[j].second] - second), row[j].second);
    320.                 }
    321.                 else
    322.                 {
    323.                     updateAns(abs(x1[col[j].second] - second), col[j].second);
    324.                 }
    325.             }
    326.         }
    327.     }
    328. }
    329. void solve()
    330. {
    331.     for (int i = 0; i < m; i++)
    332.     {
    333.         _current = i;
    334.         handleBucket(rowSize, x[i], y[i], true);
    335.         handleSame(Same(x[i], y[i], -0x3f3f3f3f), sameXSize, true);
    336.         handleBucket(colSize, y[i], x[i], false);
    337.         handleSame(Same(y[i], x[i], -0x3f3f3f3f), sameYSize, false);
    338.     }
    339. }
    340. void putAns()
    341. {
    342.     for (int i = 0; i < m; i++)
    343.     {
    344.         for (int j = 0; j < ansLen[i]; j++)
    345.         {
    346.             ans[ansIdx[i][j]] = ans[ansIdx[i][j]] + 1;
    347.         }
    348.     }
    349.     for (int i = 0; i < n; i++)
    350.     {
    351.         printf("%d\n", ans[i]);
    352.     }
    353. }
    354. int main()
    355. {
    356.     input();
    357.     sortAll();
    358.     buckedMethod();
    359.     solve();
    360.     putAns();
    361.     return 0;
    362. }

    四、效率

    题目限时6000ms，差不多用了4600ms过了。

  • 相关阅读:
    文件上传绕过复现
    JVM(尚硅谷)学习之GC日志分析
    js继承，原型链继承，构造函数继承，组合式继承，原型式继承，寄生式继承，组合寄生式继承，extends继承
    【网络杂烩 ---＞ 网络安全】DLL 注入 --- c/c++ 代码实现（超 · 详细）
    Flutter 匠心千刃 | SHA256 加密
    ArrayList和LinkedList的区别，以及应用场景
    Java 抽象工厂模式
    两台同一局域网下的电脑实现共享文件夹
    [青少年CTF训练平台]web部分题解（已完结！）
    前端性能-首次加载优化70%
  • 原文地址：https://blog.csdn.net/qq_53038151/article/details/134001121