2.数列分块入门 2

😊 | Powered By HeartFireY | 分块例题

#6278. 数列分块入门 2 - 题目 - LibreOJ (loj.ac)

对于区间查询：

• 对于不完整的块枚举统计即可；
• 对于完整块，要在每个整块内寻找小于一个值的元素数，这要求块内元素是有序的，才能使用二分法对块内查询，需要预处理时每块做一遍排序，复杂度 O ( n l o g n ) O(nlogn) O(nlogn)，每次查询在√n个块内二分，以及暴力 2 n 2\sqrt{n} 2n ​个元素，总复杂度 O ( n l o g n + n n l o g n ) O(nlogn + n\sqrt nlog \sqrt n) O(nlogn+nn ​logn ​)。

对于区间加，沿用 1 1 1的思路，继续维护加标记，但是不完整块从操作发生了改变：

• 对于不完整的块，修改后会使该块内数字乱序。因此对于每次区间修改的不完整块需要重新排序
• 对于完整的块直接维护加法标记即可。

#include 
using namespace std;

const int N = 5e5 + 10;
int id[N], blo, n;
int a[N], tag[N];

vector block[N];

void update(int loc){
    block[loc].clear();
    for(int i = (loc - 1) * blo + 1; i  v;
        if(op == 0) add(l, r, v);
        else if(op == 1) cout