一轮就滚回来了 文化课快乐

改了改分块的写法 以前的写法…太丑了

懵逼的 题目

传送至 CH

扯淡的 题解

sb分块, 一开始觉得是个三维偏序, 后来发现时间这一维不怎么好搞, 那就大力分块吧…

排序后我们发现, 对于任意一块磁石, 位置符合要求(位置在吸引半径内)的磁石是一个区间, 重量符合要求的磁石也是一个区间

于是我们先按照位置远近排序, 这样我们就相当于在一个区间内找比一个数小的数的个数, 经典的分块问题

然后按照$\sqrt n$的大小分块(其实应该有更好的块大小…但是懒得搞了), 块内按照重量排序, 二分答案(其实有更好的方法), 对于满足条件的石头放入枚举队列中, 并标记为不可再用, 块内重新按照重量排序(其实还有更好的方法), 枚举零散块内的石子, 暴力更新答案

然后…WAWAWAWA…

发现我分块写得实在是太丑了…于是参悟了lydrainbowcat神的代码Emmm…用le, ri数组代替了不靠谱的宏…

然后…TTTTTT…

下载测试点一看woc$10^4$的数据跑了6s多…Emmmm还不如暴力啊woc…

然后发现…woc我怎么整块也块内排序了…这不就$n^2 \lg n$了…

因为一个磁石被选中后就不会再用到了, 改成移动块端点…

然后…WAWA…

INF赋小了…6个f好像会炸?

A了…emmmmmmmm

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define MAXN (250000 + 5)
#define INF (0x7fffffff)
#define LL long long
#define int LL
using namespace std;
struct stone
{
    int length, weight, force, range;
    stone() {}
    stone(int l, int w, int f, int r): length(l), weight(w), force(f), range(r) {}
} b[MAXN];
int n, block, maxb[MAXN], le[MAXN], ri[MAXN];
bool cmp(stone x, stone y)
{ return x.length < y.length; }
bool comp(stone x, stone y)
{ return x.weight < y.weight; }
void init()
{
    sort(b + 1, b + n + 1, cmp);
    for (int i = 1; i <= n; i += block)
        le[++le[0]] = i, ri[++ri[0]] = min(n, i + block - 1), maxb[le[0]] = b[ri[le[0]]].length;
    for (int i = 1; i <= le[0]; i++)
        sort(b + le[i], b + ri[i] + 1, comp);
}
queue<stone> q;
int ans = 0;
void solve(int fce, int len)
{
    int rigk = 0;
    for (int i = 1; i <= le[0]; i++)
    {
        if (maxb[i] > len)
            break;
        rigk = max(rigk, i);
    }
    for (int i = 1; i <= rigk; i++)
    {
        for (; le[i] <= ri[i] && b[le[i]].weight <= fce; le[i]++)
            ++ans, q.push(b[le[i]]);
    }
    if (rigk == le[0])
        return ;
    for (int i = le[rigk + 1]; i <= min(ri[rigk + 1], n); i++)
        if (b[i].length <= len && b[i].weight <= fce)
            ++ans, q.push(b[i]), b[i].weight = INF;
    sort(b + le[rigk + 1], b + ri[rigk + 1] + 1, comp);
}
inline int read()
{
    int re = 0;
    bool f = false;
    char x = 0;
    while (x < '0' || x > '9')
    {
        x = getchar();
        if (x == '-')
            f = true;
    }
    while (x >= '0' && x <= '9')
    {
        re = (re << 1) + (re << 3) + x - '0';
        x = getchar();
    }
    return (f ? (-re) : re);
}
main()
{
//#ifndef ONLINE_JUDEG
    freopen("in.in", "r", stdin);
//    freopen("wa.out", "w", stdout);
//#endif
    int x0 = read(), y0 = read(), pl = read(), rl = read();
    n = read();
    q.push(stone(0, INF, pl, rl * rl));
    block = sqrt(n) + 1;
    for (int i = 1; i <= n; i++)
    {
        int srx = read(), sry = read(), srw = read(), srf = read(), srr = read();
        b[i] = stone((srx - x0) * (srx - x0) + (sry - y0) * (sry - y0), srw, srf, srr * srr);
    }
    init();
    while (!q.empty())
    {
        stone dq = q.front();
        q.pop();
        solve(dq.force, dq.range);
    }
    printf("%lld", ans);
    return 0;
}

/*
0 0 5 10 5
5 4 7 11 5
-7 1 4 7 8
0 2 13 5 6
2 -3 9 3 4
13 5 1 9 9
*/

By …的Cansult