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

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

时间：2022-11-19 15:35:11浏览次数：85  
标签：分块 LOJ ll 九题 int maxn build 区间 block

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

区间开方，区间求和题。

显然，针对区间维护开方操作很难做到，于是考虑其值的性质，显然，int范围内的值最多开方6次就会变为1，之后再开方依然为1，于是考虑暴力维护一个区间内的值是否全部为1即可，全部为1标记上之后再遇到O(1)处理即可。复杂度大概就为O(n*6+n*sqrt(n))

代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1e5)+5;
int a[maxn];
int sum[maxn];
int bel[maxn];
int L[maxn],R[maxn];
bool 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]=i*block;
        for(int j=L[i];j<=R[i];j++){
            bel[j]=i;
            sum[i]+=a[j];
        }
    }
}
void update(int l,int r){
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            if(tag[bel[i]])break;
            sum[bel[i]]=sum[bel[i]]-a[i]+int(sqrt(a[i]));
            a[i]=int(sqrt(a[i]));
        }
    }
    else{
        for(int i=l;i<=R[bel[l]];i++){
            if(tag[bel[i]])break;
            sum[bel[i]]=sum[bel[i]]-a[i]+int(sqrt(a[i]));
            a[i]=int(sqrt(a[i]));
        }
        for(int i=L[bel[r]];i<=r;i++){
            if(tag[bel[i]])break;
            sum[bel[i]]=sum[bel[i]]-a[i]+int(sqrt(a[i]));
            a[i]=int(sqrt(a[i]));
        }
        for(int i=bel[l]+1;i<bel[r];i++){
            bool fg=1;
            for(int j=L[i];j<=R[i];j++){
                if(tag[i])break;
                sum[i]=sum[i]-a[j]+int(sqrt(a[j]));
                a[j]=int(sqrt(a[j]));
                if(a[j]>1)fg=0;
            }
            if(fg)tag[i]=1;
        }
    }
}
void calc(int l,int r){
    int ans=0;
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            ans+=a[i];
        }
    }
    else{
        for(int i=l;i<=R[bel[l]];i++){
            ans+=a[i];
        }
        for(int i=L[bel[r]];i<=r;i++){
            ans+=a[i];
        }
        for(int i=bel[l]+1;i<bel[r];i++){
            ans+=sum[i];
        }
    }
    cout<<ans<<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++){
        int opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(opt){
            calc(l,r);
        }
        else{
            update(l,r);
        }
    }
    return 0;
}

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

区间乘法，区间加法，单点询问

类似线段树的实现操作，注意先乘后加。当时我调bug花了很久，主要原因是在处理离散块的时候我直接对a数组进行了修改操作，导致标记数组出错，解决方法为直接对离散块所属的完整块进行下放标记的操作（暴力但是可行）

代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1e5)+5;
const int modd=(1e4)+7;
int a[maxn];
int bel[maxn];
int L[maxn],R[maxn];
int tag1[maxn];
int tag2[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);
        tag1[i]=0;
        tag2[i]=1;
        for(int j=L[i];j<=R[i];j++){
            bel[j]=i;
        }
    }
}
void pushdown(int p){
    int l=L[bel[p]],r=R[bel[p]];
    for(int i=l;i<=r;i++){
        a[i]=(a[i]*tag2[bel[p]]+tag1[bel[p]])%modd;
    }
    tag1[bel[p]]=0;
    tag2[bel[p]]=1;
}
void add(int l,int r,int c){
    if(bel[l]==bel[r]){
        pushdown(l);
        for(int i=l;i<=r;i++){
            a[i]=(a[i]+c)%modd;
        }
    }
    else{
        pushdown(l);
        for(int i=l;i<=R[bel[l]];i++){
            a[i]=(a[i]+c)%modd;
        }
        pushdown(r);
        for(int i=L[bel[r]];i<=r;i++){
            a[i]=(a[i]+c)%modd;
        }
        for(int i=bel[l]+1;i<bel[r];i++){
            tag1[i]=(tag1[i]+c)%modd;
        }
    }
}
void multiply(int l,int r,int c){
    if(bel[l]==bel[r]){
        pushdown(l);
        for(int i=l;i<=r;i++){
            a[i]=(a[i]*c)%modd;
        }
    }
    else{
        pushdown(l);
        for(int i=l;i<=R[bel[l]];i++){
            a[i]=(a[i]*c)%modd;
        }
        pushdown(r);
        for(int i=L[bel[r]];i<=r;i++){
            a[i]=(a[i]*c)%modd;
        }
        for(int i=bel[l]+1;i<bel[r];i++){
            tag1[i]=(tag1[i]*c)%modd;
            tag2[i]=(tag2[i]*c)%modd;
        }
    }
}
void calc(int i){
    int ans=(a[i]*tag2[bel[i]]+tag1[bel[i]])%modd;
    cout<<ans<<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++){
        int opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(opt==0){
            add(l,r,c);
        }
        if(opt==1){
            multiply(l,r,c);
        }
        if(opt==2){
            calc(r);
        }
    }
    return 0;
}

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

区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c。

这题我折腾了挺久。思路为标记每个区间是否为同一个值，若是则标记为该值，否则标记为1e11。之后在分块的模板中再分三种情况进行分析。1.该区间全部为c，2.该区间全部为另外一个值，3.该区间的值不统一。注意点：在离散块情况2进行修改操作时需要先进行标记下放操作。

代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1e5)+5;
ll a[maxn];
ll tag[maxn];
ll bel[maxn];
ll L[maxn],R[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);
        tag[i]=1e11;
        for(int j=L[i];j<=R[i];j++){
            bel[j]=i;
        }
    }
}
void pushdown(int p){
    for(int i=L[p];i<=R[p];i++){
        a[i]=tag[p];
    }
}
void ope(ll l,ll r,ll c){
    ll ans=0;
    if(bel[l]==bel[r]){
        if(tag[bel[l]]==c){
            ans+=r-l+1;
        }
        else if(tag[bel[l]]!=1e11){
            pushdown(bel[l]);
            for(int i=l;i<=r;i++){
                a[i]=c;
            }
            tag[bel[l]]=1e11;
        }
        else{
            for(int i=l;i<=r;i++){
                if(a[i]==c)ans++;
                else a[i]=c;
            }
        }
    }
    else{
        if(tag[bel[l]]==c){
            ans+=R[bel[l]]-l+1;
        }
        else if(tag[bel[l]]!=1e11){
            pushdown(bel[l]);
            for(int i=l;i<=R[bel[l]];i++){
                a[i]=c;
            }
            tag[bel[l]]=1e11;
        }
        else{
            for(int i=l;i<=R[bel[l]];i++){
                if(a[i]==c)ans++;
                else a[i]=c;
            }
        }
        if(tag[bel[r]]==c){
            ans+=r-L[bel[r]]+1;
        }
        else if(tag[bel[r]]!=1e11){
            pushdown(bel[r]);
            for(int i=L[bel[r]];i<=r;i++){
                a[i]=c;
            }
            tag[bel[r]]=1e11;
        }
        else{
            for(int i=L[bel[r]];i<=r;i++){
                if(a[i]==c)ans++;
                else a[i]=c;
            }
        } 
        for(int i=bel[l]+1;i<bel[r];i++){
            if(tag[i]==c){
                ans+=(R[i]-L[i]+1);
            }
            else if(tag[i]==1e11){
                for(int j=L[i];j<=R[i];j++){
                    if(a[j]==c)ans++;
                    else a[j]=c;
                }
                tag[i]=c;
            }
            else{
                tag[i]=c;
            }
        }
    }
    cout<<ans<<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 l,r,c;
        cin>>l>>r>>c;
        ope(l,r,c);
    }
    return 0;
}

 

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

相关文章

  • LOJ数列分块入门九题（上）
    一转眼，已经有整整一年没有在博客园写博客了。Howtimeflys.最近突然想起其实我不太擅长分块算法，又想起去年暑假有位同学同我提起过LOJ的数列九题，说来惭愧，打了这么久题今......
  • 势能分块模板
    分块:把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这个路......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99