首页 > 其他分享 >LOJ数列分块入门九题（上）

LOJ数列分块入门九题（上）

时间：2022-11-17 20:44:49浏览次数：57  
标签：分块 LOJ ll 九题 int maxn build block

一转眼，已经有整整一年没有在博客园写博客了。How time flys.

最近突然想起其实我不太擅长分块算法，又想起去年暑假有位同学同我提起过LOJ的数列九题，说来惭愧，打了这么久题今天才打算做这个系列，甚至连LOJ的账号都没有注册。。。于是今天花费了半天时间敲题，但是更尴尬的是只打了前四题，分块细节真的是相当繁琐。

分块是一种优雅的暴力，时间复杂度为根号n量级，虽然同线段树树状数组之类的logn量级的复杂度无法相提并论，但是在大多数情况下，分块都可以比较好地替代线段树。其代码量较少且逻辑相较线段树而言更清晰尤其是可以进行块内二分之类的操作，从而有的时候比线段树更有优势。

分块，顾名思义，就是将数列分为多块进行考虑，在进行区间修改或者区间查询操作时，使用分块算法，我们可以直接处理区间中的块，再处理零散块。我们可以将数列划分为根号n个块，从而将时间复杂度降低至根号n。

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

区间加法，单点查值，分块水题（变量名想半天）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(5e4)+5;
ll a[maxn];
ll l[maxn];
ll r[maxn];
ll bel[maxn];
ll lazy_add[maxn];
void build(ll n){
    ll block=sqrt(n);
    ll num=n/block;
    if(n%block)num++;
    for(int i=1;i<=num;i++){
        l[i]=(i-1)*block+1;
        r[i]=min(n,i*block);
        lazy_add[i]=0;
    }
    for(int i=1;i<=n;i++){
        bel[i]=(i-1)/block+1;
    }
}
void add(ll L,ll rr,ll c){
    ll s=bel[L]+1;
    ll t=bel[rr]-1;
    for(int i=L;i<=min(rr,r[s-1]);i++){
        a[i]+=c;
    }
    if(bel[L]==bel[rr])return;
    for(int i=l[t+1];i<=rr;i++){
        a[i]+=c;
    }
    for(int i=s;i<=t;i++){
        lazy_add[i]+=c;
    }
}
void calc(ll x){
    ll p=bel[x];
    for(int i=l[p];i<=r[p];i++){
        a[i]+=lazy_add[p];
    }
    lazy_add[p]=0;
    cout<<a[x]<<endl;
}
int main(){
    ll n;
    cin>>n;
    build(n);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        ll opt,L,rr,c;
        cin>>opt>>L>>rr>>c;
        if(!opt){
            add(L,rr,c);
        }
        else{
            calc(rr);
        }
    }
    return 0;
}

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

块内二分即可（线段树不行），注意边角的处理

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(5e4)+5;
int L[maxn],R[maxn];
int bel[maxn];
ll a[maxn];
ll b[maxn];
ll tmp[maxn];
ll tag[maxn];
void build(int n){
    int block=sqrt(n);
    int num=n/block;
    if(n%block)num++;
    for(int i=1;i<=num;i++){
        L[i]=(i-1)*block+1;
        R[i]=min(n,i*block);
        sort(a+L[i],a+R[i]+1);
        for(int j=L[i];j<=R[i];j++){
            bel[j]=i;
        }
    }
}
void update(int l,int r,ll c){
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++)b[i]+=c;
        for(int i=L[bel[l]];i<=R[bel[l]];i++){
            tmp[i]=b[i];
        }
        sort(tmp+L[bel[l]],tmp+R[bel[l]]+1);
        for(int i=L[bel[l]];i<=R[bel[l]];i++){
            a[i]=tmp[i];
        }
    }
    else{
        for(int i=l;i<=R[bel[l]];i++){
            b[i]+=c;
        }
        for(int i=L[bel[l]];i<=R[bel[l]];i++){
            tmp[i]=b[i];
        }
        sort(tmp+L[bel[l]],tmp+R[bel[l]]+1);
        for(int i=L[bel[l]];i<=R[bel[l]];i++){
            a[i]=tmp[i];
        }
        for(int i=L[bel[r]];i<=r;i++){
            b[i]+=c;
        }
        for(int i=L[bel[r]];i<=R[bel[r]];i++){
            tmp[i]=b[i];
        }
        sort(tmp+L[bel[r]],tmp+R[bel[r]]+1);
        for(int i=L[bel[r]];i<=R[bel[r]];i++){
            a[i]=tmp[i];
        }
        for(int i=bel[l]+1;i<bel[r];i++){
            tag[i]+=c;
        }
    }
}
void calc(int l,int r,ll c){
    ll ans=0;
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            if(b[i]+tag[bel[l]]<c)ans++;
        }
    }
    else{
        for(int i=l;i<=R[bel[l]];i++){
            if(b[i]+tag[bel[l]]<c)ans++;
        }
        for(int i=L[bel[r]];i<=r;i++){
            if(b[i]+tag[bel[r]]<c)ans++;
        }
        for(int i=bel[l]+1;i<bel[r];i++){
            ans+=lower_bound(a+L[i],a+R[i]+1,c-tag[i])-a-L[i];
        }
    }
    cout<<ans<<endl;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    build(n);
    for(int i=1;i<=n;i++){
        ll opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(!opt){
            update(l,r,c);
        }
        else{
            calc(l,r,c*c);
        }
    }
    return 0;
}

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

前一题修改一下即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1e5)+5;
int L[maxn],R[maxn];
int bel[maxn];
ll a[maxn];
ll b[maxn];
ll tmp[maxn];
ll tag[maxn];
void build(int n){
    int block=sqrt(n);
    int num=n/block;
    if(n%block)num++;
    for(int i=1;i<=num;i++){
        L[i]=(i-1)*block+1;
        R[i]=min(n,i*block);
        sort(a+L[i],a+R[i]+1);
        for(int j=L[i];j<=R[i];j++){
            bel[j]=i;
        }
    }
}
void update(int l,int r,ll c){
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++)b[i]+=c;
        for(int i=L[bel[l]];i<=R[bel[l]];i++){
            tmp[i]=b[i];
        }
        sort(tmp+L[bel[l]],tmp+R[bel[l]]+1);
        for(int i=L[bel[l]];i<=R[bel[l]];i++){
            a[i]=tmp[i];
        }
    }
    else{
        for(int i=l;i<=R[bel[l]];i++){
            b[i]+=c;
        }
        for(int i=L[bel[l]];i<=R[bel[l]];i++){
            tmp[i]=b[i];
        }
        sort(tmp+L[bel[l]],tmp+R[bel[l]]+1);
        for(int i=L[bel[l]];i<=R[bel[l]];i++){
            a[i]=tmp[i];
        }
        for(int i=L[bel[r]];i<=r;i++){
            b[i]+=c;
        }
        for(int i=L[bel[r]];i<=R[bel[r]];i++){
            tmp[i]=b[i];
        }
        sort(tmp+L[bel[r]],tmp+R[bel[r]]+1);
        for(int i=L[bel[r]];i<=R[bel[r]];i++){
            a[i]=tmp[i];
        }
        for(int i=bel[l]+1;i<bel[r];i++){
            tag[i]+=c;
        }
    }
}
void calc(int l,int r,ll c){
    ll ans=-1e9;
    bool fg=0;
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            if(b[i]+tag[bel[l]]<c)ans=max(ans,b[i]+tag[bel[l]]),fg=1;
        }
    }
    else{
        for(int i=l;i<=R[bel[l]];i++){
            if(b[i]+tag[bel[l]]<c)ans=max(ans,b[i]+tag[bel[l]]),fg=1;
        }
        for(int i=L[bel[r]];i<=r;i++){
            if(b[i]+tag[bel[r]]<c)ans=max(ans,b[i]+tag[bel[r]]),fg=1;
        }
        for(int i=bel[l]+1;i<bel[r];i++){
            int p=lower_bound(a+L[i],a+R[i]+1,c-tag[i])-a-1;
            if(a[p]+tag[i]<c)ans=max(ans,a[p]+tag[i]),fg=1;
        }
    }
    if(fg)cout<<ans<<endl;
    else cout<<-1<<endl;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    build(n);
    for(int i=1;i<=n;i++){
        ll opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(!opt){
            update(l,r,c);
        }
        else{
            calc(l,r,c);
        }
    }
    return 0;
}

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

区间加法，区间求和（经典线段树，不过也可以分块）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1e5)+5;
ll a[maxn];
int L[maxn],R[maxn];
int bel[maxn];
ll siz[maxn];
ll tag[maxn];
void build(int n){
    int block=sqrt(n);
    int num=n/block;
    if(n%block)num++;
    for(int i=1;i<=num;i++){
        L[i]=(i-1)*block+1;
        R[i]=min(n,i*block);
        for(int j=L[i];j<=R[i];j++){
            bel[j]=i;
            siz[i]+=a[j];
        }
    }
}
void update(int l,int r,ll c){
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            a[i]+=c;
            siz[bel[l]]+=c;
        }
    }
    else{
        for(int i=l;i<=R[bel[l]];i++){
            a[i]+=c;
            siz[bel[l]]+=c;
        }
        for(int i=L[bel[r]];i<=r;i++){
            a[i]+=c;
            siz[bel[r]]+=c;
        }
        for(int i=bel[l]+1;i<bel[r];i++){
            siz[i]+=(R[i]-L[i]+1)*c;
            tag[i]+=c;
        }
    }
}
void calc(int l,int r,ll c){
    ll ans=0;
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            ans=(ans+a[i]+tag[bel[l]])%c;
        }
    }
    else{
        for(int i=l;i<=R[bel[l]];i++){
            ans=(ans+a[i]+tag[bel[l]])%c;
        }
        for(int i=L[bel[r]];i<=r;i++){
            ans=(ans+a[i]+tag[bel[r]])%c;
        }
        for(int i=bel[l]+1;i<bel[r];i++){
            ans=(ans+siz[i])%c;
        }
    }
    cout<<ans%c<<endl;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(n);
    for(int i=1;i<=n;i++){
        ll opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(!opt){
            update(l,r,c);
        }
        else calc(l,r,c+1);
    }
    return 0;
}

 

标签：分块,LOJ,ll,九题,int,maxn,build,block
From： https://www.cnblogs.com/yokino/p/16900873.html

相关文章

  • 势能分块模板
    分块:把n分成sqrt(n)块,中间整体修改,2边暴力修改即可,修改,查询的复杂度为3sqr(n);比线段树好写一些?当然整体的修改的时候,有时候要用lz去处理, 和势能线段树......
  • Loj 6053 简单的函数 min25筛
    #6053.简单的函数先求g(n,j)目的是为了在求S(n,j)的时候可以快速获取一些质数上的点的值。所以我们只要求g(n,j)的质数处的值正确即可其他值则不需要所以我们可以让g......
  • LOJ10150
    题目描述Hecy又接了个新任务：BE处理。BE中有一类被称为GBE。以下是GBE的定义：空表达式是GBE如果表达式A是GBE，则[A]与(A)都是GBE如果A与B都是GBE，那......
  • #yyds干货盘点# 前端歌谣的刷题之路-第一百五十九题-new
     前言我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五年的时间超越他今天又是接近兄弟的一天人生难免坎坷大不了......
  • 洛谷P4168 蒲公英 分块处理区间众数模板
    题面。许久以前我还不怎么去机房的时候，一位大佬好像一直在做这道题，他称这道题目为“大分块”。其实这道题目的思想不只可以用于处理区间众数，还可以处理很多区间数值相关......
  • 【题解】P2260 [清华集训2012]模积和（数学，整除分块）
    【题解】P2260[清华集训2012]模积和比较简单的一道推式子的题。（清华集训居然会出这种水题的吗）题目链接P2260[清华集训2012]模积和题意概述求\[\sum_{i=1}^{n}\sum......
  • loj #10069. 「一本通 3.1 练习 4」Tree
    给你一个无向带权连通图，每条边是黑色或白色。求一棵最小权的恰好有K条白色边的生成树。题目保证有解  二分一个增加量md, 给每个白边权值加md,跑一下kruskal,......
  • 【题解】CF1485C Floor and Mod（二分答案，整除分块）
    【题解】CF1485CFloorandModemmm……NOIP考前两周，跟CSP考前一样（虽然最后并没有去考），写篇题解增加以下RP（雾）。提供一篇思路大体和题解区相同但用了二分写法的题解。......
  • loj#10064 黑暗城堡
     求图中的最短路径生成树有多少个？（该生成树中的任意点i，i到1的距离和 原图中的i到1的最短距离相等  跑所有点到1的单源最短路，d[i] ifd[i]==d[y]+z，那么z这个路......
  • 「LOJ2474」北校门的未来
    题目点这里看题目。你有一棵树\(T\)，初始时\(T=(V=\{1\},E=\varnothing)\)。你将要进行\(q\)次操作，每次操作的形式为以下两种之一：第一种操作：给定参数\(x,y\)，保证......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99