【数据结构-根号算法】分块

CNS_5t0_0r2 · 2024-03-11 18:06:59 · 算法·理论

【0】引入

众所周知，分块是一种比较暴力的数据结构。

虽说分块效率不高，但它能处理一些树状数组和线段树难以维护的东西（尤其是不具备可拆分性和可合并性的东西）。

分块遵循整块维护，块内暴力的原则。所以我们一般先考虑一个暴力算法，再使用分块优化。

【1】分块基本操作

【1.1】建立分块：

我们定义一个分块的结构体 b，分别存储每个块的首尾。

对于每个块的第一个元素的下标，我们将其设为上一个块的最后一个元素的下标加 1。对于每个块的最后一个元素的下标，就是这个块的左端点加上一个块长再减 1。

因为可能会出现 n 不是块长或块的个数的倍数的情况，所以我们强制令最后一个块的末尾为序列长度 n。

最后，我们还要标记每个下标属于的块的编号。这非常有用，所有分块题都需要。

我们一般将块的个数和块长设为 \lfloor \sqrt{n}\rfloor（为什么下文会提到）。

带修莫队：那我走？（雾）

//一般来说所有分块题都要维护左右端点，当然有的题目还要维护额外的信息
struct block{
    int l,r;//块的左右端点
} b[SqrtN];
int belong[N];//belong[i]表示下标i属于的块的编号
int block_cnt,block_len;//块的个数，块长
void build_block(){
    block_cnt = block_len = (int)sqrt(n);
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = b[i].l + block_len - 1;
    }
    b[block_cnt].r = n;//上文讲了的
    for(int i = 1;i <= block_cnt;i++)
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;
}

【1.2】 区间修改/查询：

引入中说，分块遵循整体维护，块内暴力的原则。

所以分块查询一般套路如下：

如果查询两端点在同一块内，直接暴力，复杂度 O(s)，s 为块长。

否则，我们把询问拆分成三部分：

首先是两个散块，即左端点到左端点所在块的末尾，以及右端点所在块的开头到右端点两段，这两段也是暴力,复杂度也是 O(s)。

其次是中间的整块（也可能没有），对于这些部分，我们需要对它们维护一些信息，这样就可以降低整块查询的复杂度（至多不能超过 O(s)），否则，分块算法就会退化成原版的暴力。

假定单整块查询的复杂度是 O(1)，那么多个整块查询的复杂度是 O(\frac{n}{s})，即跟块的数量同级。所以整个查询时间复杂度为 O(s + \frac{n}{s})

在建立分块中说了，一般将块的个数和块长设为 \lfloor \sqrt{n}\rfloor。由均值不等式，O(s + \frac{n}{s}) 在 s = \sqrt{n} 时，取到最小值 O(\sqrt{n})（均值不等式不用我说了吧）。

拿到一道分块题，我们可以先取块长 s = \lfloor \sqrt{n} \rfloor，发现有更优解再调整块长。

【3】例题

【3.1】分块维护动态问题

例题 1：教主的魔法

非常经典的带修分块题。

查询一个区间有多少个大于 C 的数其实很难用线段树或树状数组维护（树套树还是可以的），但本题的修改是区间加，这样树套树差不多也萎了，所以考虑分块。

还是一样先设块长和块的个数为 \lfloor \sqrt{n} \rfloor，建好分块。

先考虑暴力解法。很容易想到用一个临时数组，复制下要查询的区间 [l,r]，对这个数组排序再二分。

这样的暴力算法单次复杂度修改 O(n)，查询 O(n \log n)，显然过不了。

因此，我们考虑分块，接下来分别优化修改和查询。

学过线段树的肯定知道“懒标记”这个东西，懒标记用到分块上同样适用。

还记得分块的整块维护，块内暴力的原则吗？修改也是一样的。

和查询类似，当左右端点在同一块内时，直接暴力修改，复杂度 O(\sqrt{n})。

否则，分别暴力修改左端点 l 到左端点 l 所在块的右边界和右端点 r 所在块的右边界到右端点 r，复杂度 O(\sqrt{n})。

对于每个整块，将这些整块的标记都加上 W，代表这些整块的数都要加上 W，复杂度 O(\sqrt{n})。

那么查询呢？

按照暴力的思路，我们应该对每个块内排序再二分。所以我们可以先预处理，对每个块内排序。但是每次要修改怎么办呢？

我们可以发现：对于一个单调递增的序列，整体加一个数是不会改变其单调性的，所以对于整块，只用打标记即可。

对于两个散块，暴力加后直接复制到临时数组上排序，复杂度 O(\sqrt{n} \log \sqrt{n})。

这样查询就简单了，在每个块内二分查找即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9,SqrtN = 1e3 + 9;
int n,q;
int a[N],tmp[N];
struct block{
    int l,r,add;//额外维护一个标记
} b[SqrtN];
int belong[N];//belong[i]表示下标i属于的块的编号
int block_cnt,block_len;
void block_sort(int block_id){
    int l = b[block_id].l,r = b[block_id].r;
    for(int i = l;i <= r;i++)
        tmp[i] = a[i];
    sort(tmp + l,tmp + r + 1);
}
void build_block(){
    block_cnt = block_len = (int)sqrt(n);
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = b[i].l + block_len - 1;
    }
    b[block_cnt].r = n;
    for(int i = 1;i <= block_cnt;i++){
        block_sort(i);//块内排序
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;
    }
}
void update(int l,int r,int k){
    int pos_l = belong[l],pos_r = belong[r];
    if(pos_l == pos_r){
        for(int i = l;i <= r;i++)
            a[i] += k;
        block_sort(pos_r);
        return;
    }
    for(int i = l;i <= b[pos_l].r;i++)
        a[i] += k;
    for(int i = b[pos_r].l;i <= r;i++)
        a[i] += k;
    for(int i = pos_l + 1;i <= pos_r - 1;i++)
        b[i].add += k;
    block_sort(pos_l);
    block_sort(pos_r);
}
int query(int l,int r,int k){
    int ret = 0;
    int pos_l = belong[l],pos_r = belong[r];
    if(pos_l == pos_r){
        for(int i = l;i <= r;i++)
            if(a[i] + b[pos_l].add >= k)
                ret++;
        return ret;
    }
    for(int i = l;i <= b[pos_l].r;i++)
        if(a[i] + b[pos_l].add >= k)
            ret++;
    for(int i = b[pos_r].l;i <= r;i++)
        if(a[i] + b[pos_r].add >= k)
            ret++;
    for(int i = pos_l + 1;i <= pos_r - 1;i++){
        int L = b[i].l,R = b[i].r;
        int pos = lower_bound(tmp + L,tmp + R + 1,k - b[i].add) - tmp;
        ret += b[i].r - pos + 1;
    }
    return ret;
}
signed main(){
    ios::sync_with_stdio(false);
    cin >> n >> q;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    build_block();
    for(int i = 1;i <= q;i++){
        string op;
        int l,r,k;
        cin >> op >> l >> r >> k;
        if(op == "M")
            update(l,r,k);
        else
            cout << query(l,r,k) << '\n';
    }
    return 0;
}

例题 2：由乃打扑克

做法沿用了上一题的做法（数据太太太水了）。

上题中我们实现了动态求区间内不小于 k 的数的个数，这题要求区间第 k 小，可以二分答案，设二分判定的值是 mid，那么我们就查询区间内不大于 mid 的数有多少个（其实就是 区间长度 - 区间内不小于 mid + 1 的数）,再比较 tmp 与 k 的大小关系从而缩小二分范围，具体参见代码。

毕竟还是 Ynoi，所以需要卡常。

我加了几个卡常，但真正最有用的卡常其实就这两个：

1. 缩小二分范围，可以通过维护区间最值来确定最初二分的范围。

2. 查询区间内不小于 k 的数的个数的函数内特判整块是否整体大于/小于 mid（可以通过块内最值判断）。

值得说的是，块内最值可以直接通过块内排好序的临时数组确定，不用另外维护。

#include<bits/stdc++.h>
#define int long long
#define min(x,y) (x < y ? x : y)
#define max(x,y) (x > y ? x : y)
using namespace std;
const int N = 1e5 + 9,SqrtN = 359,INF = 2e9 + 2e4 + 9;
inline char gc(){
    static char buf[10000005],*t1 = buf,*t2 = buf;
    return t1 == t2 && (t2 = (t1 = buf) + fread(buf,1,1000000,stdin),t1 == t2) ? EOF : *t1++;
}
int read(){
    char c = getchar();
    int x = 0,f = 1;
    while(c < '0' || c > '9'){
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

int n,q;
int a[N],tmp[N];
struct block{
    int l,r,add;
} b[SqrtN];
int belong[N];
int block_cnt,block_len;
void block_sort(const int block_id){
    const int l = b[block_id].l,r = b[block_id].r;
    for(int i = l;i <= r;i++)
        tmp[i] = a[i];
    sort(tmp + l,tmp + r + 1);
}
void build_block(){
    block_len = block_cnt = sqrt(n);
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = b[i].l + block_len - 1;
    }
    if(b[block_cnt].r != n){
        block_cnt++;
        b[block_cnt].l = b[block_cnt - 1].r + 1;
        b[block_cnt].r = n;
    }
    for(int i = 1;i <= block_cnt;i++){
        block_sort(i);
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;
    }
}
void update(const int &l,const int &r,const int &k){
    const int pos_l = belong[l],pos_r = belong[r];
    if(pos_l == pos_r){
        for(int i = l;i <= r;i++)
            a[i] += k;
        block_sort(pos_r);
        return;
    }
    for(int i = l;i <= b[pos_l].r;i++)
        a[i] += k;
    for(int i = b[pos_r].l;i <= r;i++)
        a[i] += k;
    for(int i = pos_l + 1;i <= pos_r - 1;i++)
        b[i].add += k;
    block_sort(pos_l);
    block_sort(pos_r);
}
int query(const int &l,const int &r,const int &k){
    int ret = 0;
    const int pos_l = belong[l],pos_r = belong[r];
    if(pos_l == pos_r){
        for(int i = l;i <= r;i++)
            if(a[i] + b[pos_l].add >= k)
                ret++;
        return ret;
    }

    for(int i = l;i <= b[pos_l].r;i++)
        if(a[i] + b[pos_l].add >= k)
            ret++;
    for(int i = b[pos_r].l;i <= r;i++)
        if(a[i] + b[pos_r].add >= k)
            ret++;
    for(int i = pos_l + 1;i <= pos_r - 1;i++){
        const int L = b[i].l,R = b[i].r;
        //卡常2 
        if(tmp[R] + b[i].add < k)
            continue;
        if(tmp[L] + b[i].add >= k){
            ret += R - L + 1;
            continue;
        }
        int pos = lower_bound(tmp + L,tmp + R + 1,k - b[i].add) - tmp;
        ret += R - pos + 1;
    }
    return ret;
}
int query_min(const int &l,const int &r){
    int ret = INF;
    const int pos_l = belong[l],pos_r = belong[r];
    if(pos_l == pos_r){
        for(int i = l;i <= r;i++)
            ret = min(ret,a[i] + b[pos_l].add);
        return ret;
    }
    for(int i = l;i <= b[pos_l].r;i++)
        ret = min(ret,a[i] + b[pos_l].add);
    for(int i = b[pos_r].l;i <= r;i++)
        ret = min(ret,a[i] + b[pos_r].add);
    for(int i = pos_l + 1;i <= pos_r - 1;i++)
        ret = min(ret,tmp[b[i].l] + b[i].add);
    return ret;
}
int query_max(const int &l,const int &r){
    int ret = -INF;
    const int pos_l = belong[l],pos_r = belong[r];
    if(pos_l == pos_r){
        for(int i = l;i <= r;i++)
            ret = max(ret,a[i] + b[pos_l].add);
        return ret;
    }
    for(int i = l;i <= b[pos_l].r;i++)
        ret = max(ret,a[i] + b[pos_l].add);
    for(int i = b[pos_r].l;i <= r;i++)
        ret = max(ret,a[i] + b[pos_r].add);
    for(int i = pos_l + 1;i <= pos_r - 1;i++)
        ret = max(ret,tmp[b[i].r] + b[i].add);
    return ret;
}
signed main(){
    ios::sync_with_stdio(false);
    cout.tie(0);
    n = read();q = read();
    for(int i = 1;i <= n;i++)
        a[i] = read();
    build_block();
    while(q--){
        int op = read();
        int l = read(),r = read(),k = read();
        if(op == 2)
            update(l,r,k);
        else{
            if(k <= 0 || k > (r - l + 1)){
                cout << "-1\n";
                continue;
            }
            int L = query_min(l,r),R = query_max(l,r),ans = -1;//卡常1 
            while(L <= R){
                const int mid = (L + R) >> 1,tmp = query(l,r,mid + 1);
                if((r - l + 1) - tmp >= k){
                    ans = mid;
                    R = mid - 1;
                }
                else
                    L = mid + 1;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

【3.2】分块维护静态问题

例题 3：[Violet] 蒲公英

本题大意就是求一个区间出现最多的数（众数），如有多个则取最小的一个，强制在线。

显然，区间众数不满足可合并性或可拆分性，所以分块就成了一个很好的选择。

先取块长为 O(\sqrt{n})，然后我们考虑什么样的数可能成为区间众数。

凭借敏锐的观察力（雾），发现区间众数只可能是这两种数：

1. 整块中的众数（最小的一个）。

2. 散块中出现了的数。

显然，如果一个数只在散块中出现过，且出现次数不多于整块众数，那么不管怎么样，整块的众数肯定更优。这样就将需要比较的数压缩到了 O(\sqrt{n}) 级别。

另外，众数只与值出现的次数有关，与值本身无关（在本题中与大小关系有关），所以考虑离散化把值域压缩至 O(n) 级别。

因为是静态问题，所以我们预处理两个数组：

1. s[SqrtN][N]：s[i][j] 表示前 i 个块中数 j 出现的次数。

2. p[SqrtN][SqrtN]：p[i][j] 代表第 i \sim j 个块中的众数。

那怎么预处理呢？

对于 s 数组，两重循环。外层循环枚举块的编号 i，内层循环枚举第 i 个块内的元素 a_j，每扫过一个，就将 s[i][a[j]] 加 1。另外，我们还好把前 i - 1 个块的元素转移过来。用一层循环，枚举值 j \leq n（毕竟离散化了），将 s[i][j] 加 s[i - 1][j]。

外层循环复杂度 O(\sqrt{n})，内层循环复杂度 O(n)（瓶颈在转移上），所以预处理 s 数组的复杂度为 O(n\sqrt{n})。

对于 p 数组，我们用两层循环枚举左块 i 和右块 j。另外，我们还要维护一个计数器 cnt[N]，记录值出现的次数，以及 Max 和 Max_cnt 用于打擂台。

先考虑最暴力的方法：暴力扫描第 i \sim j 块中的所有数 a_k，每扫到一个立刻将 cnt[a[k]] 加 1，同时立刻将 a_k 和 Max 打擂台。

但这样最内层循环的复杂度是 O(n) 的，所以这种预处理 p 数组的方法复杂度 O(n ^ 2)，需要优化。

问：我们每次真的需要清空计数器再重新全部扫描吗？

答：显然是不需要的。

我们发现：当我们扫描完第 i \sim j - 1 块时，其实可以通过对第 j 块的扫描配合此时的计数器就可以得到扫完第 i \sim j 块时的计数器，完全不需要清空，因此内层循环只用扫第 j 个块即可，复杂度 O(\sqrt{n})。

不过，当最外层循环的 i 加 1 时，这就得把计数器清空了，但复杂度还是优化到了 O(n \sqrt{n})，可以接受。

预处理完后，就可以查询了。还记得可能成为众数的数吗？这里再放出来：

1. 整块中的众数（最小的一个）。

2. 散块中出现了的数。

如果区间左右端点在同一个块中，直接按照预处理 p 数组的方式暴力即可，复杂度 O(\sqrt{n})。

否则，我们必须先得到整块中的众数及其在整个区间中出现的次数。

记左端点所在块的编号为 pos_l，右端点所在块的编号为 pos_r，显然，整块中的区间众数就是 p[pos_l + 1][pos_r - 1]。设其为 ret，则 ret 在整块中的出现次数 ret_cnt 即为 s[pos_r - 1][ret] - s[pos_l][ret]。

我们两次扫描两个散块，当扫描到的数 a_k = ret 时，将 ret_cnt 加 1，就得到了整块中的众数在整个区间的出现次数。

散块中的数处理和预处理 p 数组是类似的，不过打擂台的方式不同：因为我们只扫描散块，没考虑整块，所以每次打擂台比较的是 Max_cnt 和 cnt[a[k]] + s[pos_r - 1][a[k]] - s[pos_l][a[k]]。

这样得到的查询算法单次复杂度 O(\sqrt{n})。需要说明的是：每次清空 cnt 如果使用的是 memset，因为本题数据宽松，加上 memset 常数小，可以通过本题，但更优的方法是先扫描散块，只清空散块中出现的数，复杂度 O(\sqrt{n})。

这样，本题的时间复杂度为 O((n + m)\sqrt{n})，空间复杂度 O(n \sqrt{n})（瓶颈在 s 数组上）。

#include<bits/stdc++.h>
using namespace std;
const int N = 4e4 + 9,SqrtN = 2e2 + 9;
int n,m,ans;
int a[N],tmp[N],len;
int block_cnt,block_len;
struct block{
    int l,r;
} b[SqrtN];
int belong[N];
int p[SqrtN][SqrtN];
int s[SqrtN][N];
void build_block(){
    block_cnt = block_len = (int)sqrt(n);
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = b[i].l + block_len - 1;
    }
    b[block_cnt].r = n;
    for(int i = 1;i <= block_cnt;i++)
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;
}
int cnt[N];
void init(){
    for(int i = 1;i <= block_cnt;i++){
        for(int j = 1;j <= len;j++)
            s[i][j] = s[i - 1][j];
        for(int j = b[i].l;j <= b[i].r;j++)
            s[i][a[j]]++;
    }
    for(int i = 1;i <= block_cnt;i++){
        int Max = INT_MAX,Max_cnt = 0;
        memset(cnt,0,sizeof cnt);
        for(int j = i;j <= block_cnt;j++){
            for(int k = b[j].l;k <= b[j].r;k++){
                cnt[a[k]]++;
                if(cnt[a[k]] > Max_cnt || (cnt[a[k]] == Max_cnt && a[k] < Max)){
                    Max = a[k];
                    Max_cnt = cnt[a[k]];
                }
            }
            p[i][j] = Max;
        }
    }
}
int query(int l,int r){
    int pos_l = belong[l],pos_r = belong[r];
    int Max = INT_MAX,Max_cnt = 0;
    memset(cnt,0,sizeof cnt);
    int ret = p[pos_l + 1][pos_r - 1],ret_cnt = s[pos_r - 1][ret] - s[pos_l][ret];
    if(pos_l == pos_r){
        for(int i = l;i <= r;i++){
            cnt[a[i]]++;
            if(cnt[a[i]] > Max_cnt || (cnt[a[i]] == Max_cnt && a[i] < Max)){
                Max = a[i];
                Max_cnt = cnt[a[i]];
            }
        }
        return Max;
    }
    for(int i = l;i <= b[pos_l].r;i++)
        cnt[a[i]]++;
    for(int i = b[pos_r].l;i <= r;i++)
        cnt[a[i]]++;
    ret_cnt += cnt[ret];
    for(int i = l;i <= b[pos_l].r;i++){
        int val = cnt[a[i]] + s[pos_r - 1][a[i]] - s[pos_l][a[i]];
        if(val > Max_cnt || (val == Max_cnt && a[i] < Max)){
            Max = a[i];
            Max_cnt = val;
        }
    }
    for(int i = b[pos_r].l;i <= r;i++){
        int val = cnt[a[i]] + s[pos_r - 1][a[i]] - s[pos_l][a[i]];
        if(val > Max_cnt || (val == Max_cnt && a[i] < Max)){
            Max = a[i];
            Max_cnt = val;
        }
    }
    if(Max_cnt > ret_cnt || (Max_cnt == ret_cnt && Max < ret))
        ret = Max;
    return ret;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i++){
        scanf("%d", &a[i]);
        tmp[i] = a[i];
    }
    sort(tmp + 1,tmp + n + 1);
    len = unique(tmp + 1,tmp + n + 1) - tmp - 1;
    for(int i = 1;i <= n;i++)
        a[i] = lower_bound(tmp + 1,tmp + len + 1,a[i]) - tmp;
    build();
    init();
    for(int i = 1;i <= m;i++){
        int l,r;
        scanf("%d%d", &l, &r);
        l = (l + ans - 1) % n + 1;
        r = (r + ans - 1) % n + 1;
        if(l > r)
            swap(l,r);
        ans = tmp[query(l,r)];
        printf("%d\n",ans);
    }
}

这其中有一个易错点（我在本题中没犯但是在例题 6 中犯了）。

预处理 p 数组的代码：

for(int i = 1;i <= block_cnt;i++){
    int Max = INT_MAX,Max_cnt = 0;
    memset(cnt,0,sizeof cnt);
    for(int j = i;j <= block_cnt;j++){
        for(int k = b[j].l;k <= b[j].r;k++){
        cnt[a[k]]++;
            if(cnt[a[k]] > Max_cnt || (cnt[a[k]] == Max_cnt && a[k] < Max)){
                Max = a[k];
                Max_cnt = cnt[a[k]];
            }
        }
        p[i][j] = Max;
    }
}

其中 Max 不能删掉直接用 p[i][j] 打擂台，因为 cnt 数组是第 i \sim j 个块的计数器，但是我们只扫描了第 j 个块，所以直接用 p[i][j] 打擂台最终得到的结果是第 j 个块中的众数，并不是 i \sim j 的众数。

例题 4：Yuno loves sqrt technology III

如果用和上题一样的思路，我们会得到这样的代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9,SqrtN = 7e2 + 50;
int n,m,ans;
int a[N];
int block_cnt,block_len;
struct block{
    int start,end,size;
} b[SqrtN];
int belong[N];
int p[SqrtN][SqrtN];
int s[SqrtN][N];
void build(){
    block_cnt = (int)sqrt(n);
    block_len = (n + block_cnt - 1) / block_cnt;
    for (int i = 1;i <= block_cnt;i++) {
        b[i].start = n / block_cnt * (i - 1) + 1;
        b[i].end = n / block_cnt * i;
    }
    b[block_cnt].end = n;
    for (int i = 1;i <= block_cnt;i++) {
        for (int j = b[i].start;j <= b[i].end;j++)
            belong[j] = i;
        b[i].size = b[i].end - b[i].start + 1;
    }
}
int cnt[N];
void init(){
    for(int i = 1;i <= block_cnt;i++){
        for(int j = 1;j <= n;j++)
            s[i][j] = s[i - 1][j];
        for(int j = b[i].start;j <= b[i].end;j++)
            s[i][a[j]]++;
    }
    for(int i = 1;i <= block_cnt;i++){
        int Max = INT_MAX,Max_cnt = 0;
        memset(cnt,0,sizeof cnt);
        for(int j = i;j <= block_cnt;j++){
            for(int k = b[j].start;k <= b[j].end;k++){
                cnt[a[k]]++;
                if(cnt[a[k]] > Max_cnt || (cnt[a[k]] == Max_cnt && a[k] < Max)){
                    Max = a[k];
                    Max_cnt = cnt[a[k]];
                }
            }
            p[i][j] = Max;
        }
    }
}
int query(int l,int r){
    int pos_l = belong[l],pos_r = belong[r];
    int Max = INT_MAX,Max_cnt = 0;
    memset(cnt,0,sizeof cnt);
    int ret = p[pos_l + 1][pos_r - 1],ret_cnt = s[pos_r - 1][ret] - s[pos_l][ret];
    if(pos_l == pos_r){
        for(int i = l;i <= r;i++){
            cnt[a[i]]++;
            if(cnt[a[i]] > Max_cnt || (cnt[a[i]] == Max_cnt && a[i] < Max)){
                Max = a[i];
                Max_cnt = cnt[a[i]];
            }
        }
        return Max;
    }
    for(int i = l;i <= b[pos_l].end;i++)
        cnt[a[i]]++;
    for(int i = b[pos_r].start;i <= r;i++)
        cnt[a[i]]++;
    ret_cnt += cnt[ret];
    for(int i = l;i <= b[pos_l].end;i++){
        int val = cnt[a[i]] + s[pos_r - 1][a[i]] - s[pos_l][a[i]];
        if(val > Max_cnt || (val == Max_cnt && a[i] < Max)){
            Max = a[i];
            Max_cnt = val;
        }
    }
    for(int i = b[pos_r].start;i <= r;i++){
        int val = cnt[a[i]] + s[pos_r - 1][a[i]] - s[pos_l][a[i]];
        if(val > Max_cnt || (val == Max_cnt && a[i] < Max)){
            Max = a[i];
            Max_cnt = val;
        }
    }
    if(Max_cnt > ret_cnt || (Max_cnt == ret_cnt && Max < ret))
        ret = Max;
    return s[pos_r - 1][ret] - s[pos_l][ret] + cnt[ret];
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i++)
        scanf("%d", &a[i]);
    build();
    init();
    for(int i = 1;i <= m;i++){
        int l,r;
        scanf("%d%d", &l, &r);
        l ^= ans;
        r ^= ans;
        if(l > r)
            swap(l,r);
        ans = query(l,r);
        printf("%d\n",ans);
    }
}

但如果这份代码都能过，这就不叫 Ynoi 了（雾）。

上面的代码空间复杂度 O(n \sqrt{n})，本题 n \leq 5 \times 10 ^ 5，空间限制 62.5MB，交上去就会得到 Memory Limit Enough（MLE）！

代码空间复杂度瓶颈在 s 数组上，考虑优化掉它。

所以怎样优化？

因为本题只要求区间众数出现的次数，我们并不关心具体值，所以我们并不需要打擂台，可以考虑这样的算法：

我们将每个数 a_i 的下标放入桶中。

如果这句话很难理解，可以看个例子：

有这么一个序列 1 1 4 5 1 4 1 9 1 9 8 10，

则我们得到的桶如下：

1:1 2 5 7 9
2:（空）
3:（空）
4:3 6
5:4
6:（空）
7:（空）
8:11
9:8 10
10:12

上述操作可以用可变数组 vector 实现，下文记为 id。

同时，我们记录每个数 a_i 在其所在桶的下标 pos_i

还是这个例子：1 1 4 5 1 4 1 9 1 9 8 10

其对应的 pos 数组如下：

a:   1 1 4 5 1 4 1 9 1 9 8 10
pos: 0 1 0 0 2 1 3 0 4 1 0 0 

注意 vector 中的下标是从 0 开始的。

这有什么用呢？

算了还是结合代码讲吧：

先把框架写出来：

int query(int l,int r){
    int pos_l = belong[l],pos_r = belong[r];
    if(pos_l == pos_r){//还是一样的块内暴力
        int ret = 0;
        for(int i = l;i <= r;i++)
            ret = max(ret,++cnt[a[i]]);
        for(int i = l;i <= r;i++)//注意清空方式！
            cnt[a[i]] = 0;
        return ret;
    }
    int ret = mode_cnt[pos_l + 1][pos_r - 1];//区间众数的出现次数
  //遍历左右散块
    for(int i = l;i <= b[pos_l].r;i++)
        //TODO
    for(int i = b[pos_r].l;i <= r;i++)
        //TODO
    return ret;
}

接下来填写 TODO 内的内容。

当我们扫到一个数 a_i，我们不需要知道它是否可以取代当前众数（因为我们不知道当前的众数是什么），我们只关心其出现次数是否超过当前的 ret。

怎么判断呢？这个时候我们预处理的桶和 pos 数组就有用了。

如果 a_i 在区间中的出现次数超过当前的 ret，那么其充要条件为在 a_i 所在桶内存在第 pos_i + ret 个数存在且下标小于 r。但我们不确定区间中是否还有更多的 a_i，所以我们在满足上方不等式的前提下不断将 ret 加 1。

for(int i = l;i <= b[pos_l].r;i++)
    for(;pos[i] + ret < id[a[i]].size()/*第pos[i] + ret个a[i]存在（防止越界）*/ && 
        id[a[i]][pos[i] + ret] <= r/*第pos[i] + ret个a[i]在[l,r]区间内（已经保证了pos[i] + ret>=l）*/;ret++);

右侧应该是同理的，只需要把条件反过来即可。

怎么说呢……我觉得这份代码可以套到上题中，但我没试过。如果有大佬实现了，欢迎私信与我交流（如果不行也欢迎告诉我）！

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9,SqrtN = 733;
int n,m,ans;
int a[N],tmp[N],len;
int block_cnt,block_len;
struct block{
    int l,r;
} b[SqrtN];
int belong[N];
int mode_cnt[SqrtN][SqrtN];//区间众数在区间中的出现次数
vector<int> id[N];//id[i]：所有值为i的数的下标 
int pos[N];//pos[i]：a[i]是所在的vector的第pos[i]个数（从0开始） 
void build(){
    block_cnt = block_len = (int)sqrt(n);
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = b[i].l + block_len - 1;
    }
    b[block_cnt].r = n;
    for(int i = 1;i <= block_cnt;i++)
        for(int j = b[i].l;j <= b[i].r;j++)
           belong[j] = i;
}
int cnt[N];
void init(){
    for(int i = 1;i <= block_cnt;i++){
        int Mode_cnt = 0;
        memset(cnt,0,sizeof cnt);
        for(int j = i;j <= block_cnt;j++){
            for(int k = b[j].l;k <= b[j].r;k++)
                Mode_cnt = max(Mode_cnt,++cnt[a[k]]);
            mode_cnt[i][j] = Mode_cnt;
        }
    }
    memset(cnt,0,sizeof cnt);   
}
int query(int l,int r){
    int pos_l = belong[l],pos_r = belong[r];
    if(pos_l == pos_r){
        int ret = 0;
        for(int i = l;i <= r;i++)
            ret = max(ret,++cnt[a[i]]);
        for(int i = l;i <= r;i++)
            cnt[a[i]] = 0;
        return ret;
    }
    int ret = mode_cnt[pos_l + 1][pos_r - 1];
    for(int i = l;i <= b[pos_l].r;i++)
        for(;pos[i] + ret < id[a[i]].size()/*第pos[i] + ret个a[i]存在（防止越界）*/ && 
            id[a[i]][pos[i] + ret] <= r/*第pos[i] + ret个a[i]在[l,r]区间内（已经保证了pos[i] + ret>=l）*/;ret++);
    for(int i = b[pos_r].l;i <= r;i++)
        for(;pos[i] - ret >= 0/*防止越界*/ && id[a[i]][pos[i] - ret] >= l;ret++);
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        tmp[i] = a[i];
    }
    sort(tmp + 1,tmp + n + 1);
    len = unique(tmp + 1,tmp + n + 1) - tmp - 1;
    for(int i = 1;i <= n;i++){
        a[i] = lower_bound(tmp + 1,tmp + len + 1,a[i]) - tmp;
        id[a[i]].push_back(i);
        pos[i] = id[a[i]].size() - 1;
    }
    build();
    init();
    while(m--){
        int l,r;
        cin >> l >> r;
        l ^= ans;r ^= ans;if(l > r)swap(l,r);
        ans = query(l,r);
        cout << ans << '\n';
    }
    return 0;
}

例题 5：作诗

先考虑暴力，暴力的话就开一个桶，每次加入一个数的时候，判断其出现次数变成了奇数还是偶数，如果变成了偶数将答案加 1，如果变成了奇数且不是 1（是 1 的话说明之前是 0，不是正偶数），就将答案减 1。

如何优化？

和前两题一样的套路，先维护前 i 个块中数 j 的出现次数 cnt[i][j] 以及第 i \sim j 块中出现次数为正偶数次的数的个数 valid[i][j]。

然后初始设返回值为 valid[pos_l + 1][pos_r - 1]，开一个桶 bucket，每次加入一个数 a_i 就将 bucket[a[i]] 加 1，并判断当前 a_i 在区间内的出现次数 bucket[a[i] + cnt[pos_r - 1][a[i]] - cnt[pos_l][a[i]] 是否变为奇数或偶数，然后对答案进行对应的加减即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9,SqrtN = 355;
int n,c,m;
int a[N];
int ans;
struct block{
    int l,r;
} b[SqrtN];
int block_len,block_cnt;
int belong[N];
void build_block(){
    block_len = block_cnt = (int)sqrt(n);
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = b[i].l + block_len - 1;
    }
    b[block_cnt].r = n;
    for(int i = 1;i <= block_cnt;i++)
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;
}
int cnt[SqrtN][N];//cnt[i][j]：数j在前i个块中出现了多少次 
int valid[SqrtN][SqrtN];//第i到第j个块中合法的数有多少个 
int bucket[N];//桶 
void init(){
    for(int i = 1;i <= block_cnt;i++){
        for(int j = 1;j <= c;j++)
            cnt[i][j] += cnt[i - 1][j];
        for(int j = b[i].l;j <= b[i].r;j++)
            cnt[i][a[j]]++;
    }
    for(int i = 1;i <= block_cnt;i++){
        memset(bucket,0,sizeof bucket);
        int tmp = 0;
        for(int j = i;j <= block_cnt;j++){
            for(int k = b[j].l;k <= b[j].r;k++){
                bucket[a[k]]++;
                if((bucket[a[k]] & 1) && (bucket[a[k]] > 1))
                    tmp--;
                else if(!(bucket[a[k]] & 1))
                    tmp++;
            }
            valid[i][j] = tmp;
        }
    } 
    memset(bucket,0,sizeof bucket);
}

int query(int l,int r){
    int pos_l = belong[l],pos_r = belong[r];
    if(pos_l == pos_r){
        int ret = 0;
        for(int i = l;i <= r;i++){
            bucket[a[i]]++;
            if((bucket[a[i]] & 1) && (bucket[a[i]] > 1))
                ret--;
            else if(!(bucket[a[i]] & 1))
                ret++;
        }
        for(int i = l;i <= r;i++)
            bucket[a[i]] = 0;
        return ret;
    }
    int ret = valid[pos_l + 1][pos_r - 1];
    #define tot (bucket[a[i]] + cnt[pos_r - 1][a[i]] - cnt[pos_l][a[i]])
    for(int i = l;i <= b[pos_l].r;i++){
        bucket[a[i]]++;
        if((tot & 1) && (tot > 1))
            ret--;
        else if(!(tot & 1))
            ret++;
    }
    for(int i = b[pos_r].l;i <= r;i++){
        bucket[a[i]]++;
        if((tot & 1) && (tot > 1))
            ret--;
        else if(!(tot & 1))
            ret++;
    }
    for(int i = l;i <= b[pos_l].r;i++)
        bucket[a[i]] = 0;
    for(int i = b[pos_r].l;i <= r;i++)
        bucket[a[i]] = 0;
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> c >> m;
    build_block();
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    init();
    for(int i = 1;i <= m;i++){
        int l,r;
        cin >> l >> r;
        l = (l + ans) % n + 1;
        r = (r + ans) % n + 1;
        if(l > r)
            swap(l,r);
        ans = query(l,r);
        cout << ans << '\n';
    }
    return 0;
}

例题 6：歴史の研究

没错这就是回滚莫队板子，但是我不会回滚莫队，所以就只能写在线的分块解法了。

在线分块解法其实与前三题也是类似的。维护 p[i][j] 表示第 i \sim j 块内最大的重要度，以及 s[i][j] 表示前 i 个块中 j 的出现次数。

对于块内暴力，就每次加入离散化后的 a[i]，然后用 bucket[a[i]] * tmp[a[i]]（tmp[a[i]] 是 a[i] 在离散化之前的数值）更新答案。

对于一般情况是类似的，只用把所有的 bucket[a[i]] 换成 bucket[a[i]] + cnt[pos_r - 1][a[i]] - cnt[pos_l][a[i]] 就是在区间内当前 a[i] 的数量。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9,SqrtN = 359;
int n,q;
int a[N];
int tmp[N],top;
struct block{
    int l,r;
} b[SqrtN];
int block_len,block_cnt;
int belong[N];
void build_block(){
    block_len = block_cnt = (int)sqrt(n);
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = b[i].l + block_len - 1;
    }
    b[block_cnt].r = n;
    for(int i = 1;i <= block_cnt;i++)
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;
}
int s[SqrtN][N];//前i个块中每个事件类型的出现次数
int p[SqrtN][SqrtN];//第i~j个块中最重要的事件类型的重要程度
int bucket[N];
void init(){
    for(int i = 1;i <= block_cnt;i++){
        for(int j = b[i].l;j <= b[i].r;j++)
            bucket[a[j]]++;
        for(int j = 1;j <= top;j++)
            s[i][j] = bucket[j];
    }
  //这里当时写错了，不能用p[i][j]代替Max打擂台
    for(int i = 1;i <= block_cnt;i++){
        memset(bucket,0,sizeof bucket);
        int Max = 0;
        for(int j = i;j <= block_cnt;j++){
            for(int k = b[j].l;k <= b[j].r;k++){
                bucket[a[k]]++;
                Max = max(Max,bucket[a[k]] * tmp[a[k]]);
            }
            p[i][j] = Max;
        }
    }
    memset(bucket,0,sizeof bucket);
}
int query(int l,int r){
    int pos_l = belong[l],pos_r = belong[r];
    int ret = 0;
    if(pos_r == pos_l){
        for(int i = l;i <= r;i++){
            bucket[a[i]]++;
            ret = max(ret,bucket[a[i]] * tmp[a[i]]);
        }
        //清空
        for(int i = l;i <= r;i++)
            bucket[a[i]] = 0;
        return ret;
    }
    ret = p[pos_l + 1][pos_r - 1];
    for(int i = l;i <= b[pos_l].r;i++){
        bucket[a[i]]++;
        ret = max(ret,(bucket[a[i]] + s[pos_r - 1][a[i]] - s[pos_l][a[i]]) * tmp[a[i]]);
    }
    for(int i = b[pos_r].l;i <= r;i++){
        bucket[a[i]]++;
        ret = max(ret,(bucket[a[i]] + s[pos_r - 1][a[i]] - s[pos_l][a[i]]) * tmp[a[i]]);
    }

    //清空
    for(int i = l;i <= b[pos_l].r;i++)
        bucket[a[i]] = 0;
    for(int i = b[pos_r].l;i <= r;i++)
        bucket[a[i]] = 0;
    return ret;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> q;
    build_block();
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        tmp[++top] = a[i];
    }
    sort(tmp + 1,tmp + top + 1);
    top = unique(tmp + 1,tmp + top + 1) - tmp - 1;
    for(int i = 1;i <= n;i++)
        a[i] = lower_bound(tmp + 1,tmp + top + 1,a[i]) - tmp;
    init();
    while(q--){
        int l,r;
        cin >> l >> r;
        cout << query(l,r) << '\n';
    }
    return 0;
}

例题 7：Fotile 模拟赛 L

本题的区间查询可以拆成整块内部的最大异或对和散块对整个区间的贡献，然后按照和上述题目类似的方法预处理整块的答案即可。

题解放这了。

例题 8：魔术

本题中的操作序列具有可合并性（所以可以用线段树写，但我懒），即可以求出 [l,k] 的影响和 [k + 1,r] 的影响得到 [l,r] 的影响（影响用一个长度为 10 的数组 arr 表示 arr_i 表示影响后第 i 位是影响前的第几位）。

所以预处理出第 i \sim j 个块的影响 effect[i][j]，在询问的时候先暴力左散块，再执行整块的影响，最后暴力右散块（注意在没有整块的时候要暴力，否则会出现 pos_l + 1 > pos_r - 1 的情况，从而导致错误）。

#include<bits/stdc++.h>
using namespace std;
const int N = 10,M = 1e5 + 9,Sqrt = 359;
int n,m;
struct Arr{
    int a[N];
    void reset(){
        for(int i = 0;i < N;i++)
            a[i] = i;
    }
    void print(){
        for(int i = 0;i < N;i++)
            cout << a[i] << ' ';
        cout << '\n';
    }
};
Arr arr,tmp;
struct OPTION{
    int x,y;
} op[M];
struct block{
    int l,r;
} b[Sqrt];
int block_len,block_cnt;
int belong[M];
void build_block(){
    block_len = block_cnt = sqrt(n);
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = b[i].l + block_len - 1;
    }
    b[block_cnt].r = n;
    for(int i = 1;i <= block_cnt;i++)
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;
}
Arr effect[Sqrt][Sqrt];
void init(){
    for(int i = 1;i <= block_cnt;i++)
        for(int j = i;j <= block_cnt;j++)
            effect[i][j].reset();
    for(int i = 1;i <= block_cnt;i++){
        tmp.reset();
        for(int j = i;j <= block_cnt;j++){
            for(int k = b[j].l;k <= b[j].r;k++)
                swap(tmp.a[op[k].x],tmp.a[op[k].y]);
            effect[i][j] = tmp;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> op[i].x >> op[i].y;
    build_block();
    init();
    while(m--){
        arr.reset();
        int l,r;
        cin >> l >> r;
        int pos_l = belong[l],pos_r = belong[r];
        if(pos_r - pos_l <= 1){
            for(int i = l;i <= r;i++)
                swap(arr.a[op[i].x],arr.a[op[i].y]);
            arr.print();
            continue;
        }
        for(int i = l;i <= b[pos_l].r;i++)
            swap(arr.a[op[i].x],arr.a[op[i].y]);
        tmp = arr;
        for(int i = 0;i < N;i++)
            tmp.a[i] = arr.a[effect[pos_l + 1][pos_r - 1].a[i]];
        arr = tmp;
        for(int i = b[pos_r].l;i <= r;i++)
            swap(arr.a[op[i].x],arr.a[op[i].y]);
        arr.print();
    }
    return 0;
}

例题 9：Gripping Story 及双倍经验 磁力块

分块优化搜索。

首先考虑暴力做法，初始只有一个机械臂，我们暴力的把所有能抓过来的机械臂都抓过来，再分别尝试抓过来的机械臂。

这显然是一个 bfs 的过程，复杂度为 O(n ^ 2)，无法通过题目。

分块本身就是一个优雅的暴力，所以我们考虑本题使用分块优化。

不妨先取块长为 \sqrt{n}。

我们接下来分析：暴力有什么问题？

我们发现，暴力法每次都要把所有机械臂遍历一遍，无论其是否被抓走，这导致很多已经被抓走的机械臂被重复遍历了很多次，考虑从这个角度优化。

可以发现这么一个性质：设第 i 个机械臂到 (x,y) 的距离为 dis_i，如果 dis 和 m 都是单调不减的，我们显然可以维护一个指针，每次向右移动指针抓取机械臂直到不能抓为止。

在本例中，指针是不用向左移的，即每个机械臂都只会遍历一次，所以总复杂度是 O(n) 的。

但出题人会这么良心吗？不会的！

不过，这给我们一个启发：我们可以让每个块内都有类似的性质，即我们对每个块维护一个上例中的指针，使这个指针不用左移。

上例中 dis 和 m 是严格单调的，但是我们无法通过排序使 dis 和 m 都单调。

本题关键来了：

形式化来讲，记 belong_i 为第 i 个机械臂所在块的编号，对于任意 i < j，若 belong_i < belong_j，则 m_i \leq m_j；若 belong_i = belong_j，则 dis_i \leq dis_j。

这个思路巧妙在哪？

分块遵循的都是整体维护，块内暴力原则，那本题中的整体是什么？

很显然，有了整体的 m 单调，我们可以确定我们需要查询哪些块，不查询哪些块。

具体来说，我们可以对每个块维护一个 Max 表示最重的机械臂重量。我们从左往右暴力查找（也可以二分，但只起到优化常数的效果），当查找到第一个 Max_k > p 时，说明 1 \sim k - 1 块中所有机械臂的 m 都满足要求，第 k + 1 \sim n 块中所有机械臂的 m 都不满足要求，第 k 块无法确定，需要暴力 O(\sqrt{n}) 查询。

对于前 k - 1 块，就可以用上述移动指针的方式查询，每个块均摊是 O(1) 的，所以这部分查询复杂度也是 O(\sqrt{n}) 的。

综上，我们得到了一个 O(n\sqrt{n}) 的算法。

很奇怪的是我的代码中常量 N 的大小需要比题目中的 n 开大 4 倍，否则会 RE，有大佬可以解释的欢迎留言！

#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 1e6 + 9,SqrtN = 1e6 + 9;
int n;
struct Data{
    int x,y,m,p;
    ll r,dis;//dis存的是真实距离的平方，所以将读入的 r 也全部平方
} a[N];
struct block{//存储块的结构体
    int l,r;//块的左右边界，注意本代码中直接将 l 当作文中提到的指针使用
} b[SqrtN];
int belong[N];
int block_cnt,block_len;
int Max[SqrtN];
bool vis[N];
ll sq(int k){
    return (ll)k * k;
}
ll dist(Data m1,Data m2){
    int x1 = m1.x,y1 = m1.y,x2 = m2.x,y2 = m2.y;
    return sq(x1 - x2) + sq(y1 - y2);
}
bool cmp1(Data m1,Data m2){
    return m1.m < m2.m;
}
bool cmp2(Data m1,Data m2){
    return m1.dis < m2.dis;
}
void block_sort(int block_id){//块内按dis排序
    int l = b[block_id].l,r = b[block_id].r;
    sort(a + l,a + r + 1,cmp2);
}
void build_block(){
    block_cnt = block_len = (int)sqrt(n);
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = block_len * i;
    }
    b[block_cnt].r = n;
    for(int i = 1;i <= block_cnt;i++){
        block_sort(i);
        for(int j = b[i].l;j <= b[i].r;j++){
            Max[i] = max(Max[i],a[j].m);
            belong[j] = i;
        }
    }
}
queue<Data>q;
int ans;
void attract(Data u){
    int pos = n + 1;
    for(int i = 1;i <= block_cnt;i++)
        if(Max[i] > u.p){
            pos = i;
            break;
        }
    for(int i = 1;i <= pos - 1;i++){
        while(b[i].l <= b[i].r && dist(a[0],a[b[i].l]) <= u.r){
            int j = b[i].l;
            if(!vis[j]){            
                ans++;
                q.push(a[j]);
                vis[j] = true;//这个加不加无所谓
            }
            b[i].l++;//移动指针
        }
    }
    if(pos == n + 1)
        return;
    for(int i = b[pos].l;i <= b[pos].r;i++)
        if(a[i].m <= u.p && dist(a[0],a[i]) <= u.r && !vis[i]){
            ans++;
            vis[i] = true;//暴力取走的必须标记，否则可能会在移动指针时被重复计算
            q.push(a[i]);
        }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> a[0].x >> a[0].y >> a[0].p >> a[0].r >> n;
    for(int i = 1;i <= n;i++)
        cin >> a[i].x >> a[i].y >> a[i].m >> a[i].p >> a[i].r;
    for(int i = 0;i <= n;i++){
        a[i].r = sq(a[i].r);
        a[i].dis = dist(a[0],a[i]);
    }
    sort(a + 1,a + n + 1,cmp1);//整体满足m单调
    build_block();
    vis[0] = true;
    q.push(a[0]);
    while(!q.empty() && ans < n){
        Data u = q.front();
        q.pop();
        attract(u);
    }
    cout << ans;
    return 0;
}