乐趣区

关于c++:专题日志-数列分块2

jiezi

数列分块专题 No.2

分块利用推广来啦
如果还不理解分块请先学习 ” 数列分块 1 ″ -> 点这里学习

放上题号 – LOJ 6278 数列分块入门 2
挂上链接 – https://loj.ac/problem/6278
题面 – 给出一个数列，2 种操作，区间加法和询问区间内小于某个值的元素个数

Now，进入正题

这题较之分块 1 的题区别就在于单点查值变成了区间询问小于某值的元素个数

这下可犯难了，数列是无序的呀，挨个比拟，O(n^2)，必定超时；排序也不行，打乱了原先的程序，就找不到题目给定的区间了 ……

这时分块又派上了用场，” 大段保护，小段奢侈 ” 的核心思想仍旧

然而如何 ” 大段保护 ” 呢？既然咱们不能排序整个数列，那咱们无妨将每个每个分块排序，瞧下数据，50000 级别，O(n*logn)的 sort 就能够满足需要。

void reset(int x){ve[x].clear();
    for(int i=(x-1)*blo+1;i<=min(x*blo,N);i++)
        ve[x].push_back(v[i]);
    sort(ve[x].begin(),ve[x].end());
    // 对于一个分块的批改并排序（因为 vector 内元素不可批改, 所以清零后从新放入）}

排完序后就很明了了，对于每个分块咱们应用 O(logn)二分查找 (lower_bound 函数) 来求其小于某值的元素个数。

for(int i=bl[a]+1;i<=bl[b]-1;i++){int x=c-atag[i]; // 先减去区间对立加量, 反映了宏观晋升宏观 
    ans+=lower_bound(ve[i].begin(),ve[i].end(),x)-ve[i].begin(); // 二分查找求数量}

“ 小段奢侈 ” 即头尾有余一个分块的局部应用挨个比拟的办法

for(int i=a;i<=min(bl[a]*blo,b);i++)
    if(v[i]+atag[bl[a]]<c)
        ans++;
    
if(bl[a]!=bl[b])
    for(int i=(bl[b]-1)*blo+1;i<=b;i++)
        if(v[i]+atag[bl[b]]<c)
            ans++;

区间加法和之前根本一样，如果还不理解分块请先学习 ” 数列分块 1 ″ -> 点这里学习
但记得 ” 小段保护 ” 后排序

for(int i=a;i<=min(bl[a]*blo,b);i++)
    v[i]+=c;
reset(bl[a]); //"小段" 内单点批改后记得把所在分块批改排序 
    
if(bl[a]!=bl[b]){for(int i=(bl[b]-1)*blo+1;i<=b;i++)
        v[i]+=c;
    reset(bl[b]); // 同理 
}

到这里就根本完结啦~ 最初附上残缺代码 (C++) 和精心设计的注解

// LOJ 6278 - 数列分块练习 2
// https://loj.ac/problem/6278
// 分块(vector) 

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int N,blo;
int v[50005],bl[50005],atag[50005];
vector<int> ve[505];

void reset(int x){ve[x].clear();
    for(int i=(x-1)*blo+1;i<=min(x*blo,N);i++)
        ve[x].push_back(v[i]);
    sort(ve[x].begin(),ve[x].end());
    // 对于一个分块的批改并排序（因为 vector 内元素不可批改, 所以清零后从新放入）}

void add(int a,int b,int c){for(int i=a;i<=min(bl[a]*blo,b);i++)
        v[i]+=c;
    reset(bl[a]); //"小段" 内单点批改后记得把所在分块批改排序 
    
    if(bl[a]!=bl[b]){for(int i=(bl[b]-1)*blo+1;i<=b;i++)
            v[i]+=c;
        reset(bl[b]); // 同理 
    }
    
    for(int i=bl[a]+1;i<=bl[b]-1;i++)
        atag[i]+=c;
}

int query(int a,int b,int c){
    int ans=0;
    for(int i=a;i<=min(bl[a]*blo,b);i++)
        if(v[i]+atag[bl[a]]<c)
            ans++;
    // 右边有余一块的中央进行 "奢侈" 
    
    if(bl[a]!=bl[b])
        for(int i=(bl[b]-1)*blo+1;i<=b;i++)
            if(v[i]+atag[bl[b]]<c)
                ans++;
    // 左边 
    
    for(int i=bl[a]+1;i<=bl[b]-1;i++){int x=c-atag[i]; // 先减去区间对立加量, 反映了宏观晋升宏观 
        ans+=lower_bound(ve[i].begin(),ve[i].end(),x)-ve[i].begin(); // 二分查找求数量}
    
    return ans;
}

int main(){ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    blo=sqrt(N);
    
    for(int i=1;i<=N;i++)
       cin >> v[i];
    
    for(int i=1;i<=N;i++){bl[i]=(i-1)/blo+1;
        ve[bl[i]].push_back(v[i]);
    }
    
    for(int i=1;i<=bl[N];i++)
        sort(ve[i].begin(),ve[i].end());
    
    for(int i=1;i<=N;i++){
        int F, L, R, C;
        cin >> F >> L >> R >> C;
        if(F==0) add(L,R,C); // 区间加法 
        if(F==1) cout << query(L,R,C*C) << endl; // 区间查问 
    }
    
    return 0;
}

如有疑难可在评论区提出

留个赞再走呗~

退出移动版