分块学习笔记

标签: -----------算法总结-------------

分块算法的基本思想是通过适当的划分,预处理一部分的信息并保存下来,用空间换取时间,达到时空平衡。

分块1
给定长度为N的数列A,然后输入M行操作指令。
第一类指令形如“C l r d”,表示把数列中第l~r个数都加d。
第二类指令形如“Q X”,表示询问数列中第x个数的值。
对于每个询问,输出一个整数表示答案。
区间修改,单点查询

ll sum[N];
int pos[N];
ll add[N];
ll a[N];
int L[N];
int R[N];
ll query(int id){
    int p = pos[id];
    return a[id] + add[p];
}
void Add(int l,int r,ll d){
    if(l > r) swap(l,r);
    int p1 = pos[l],p2 = pos[r];
    if(p1 == p2){
        for(int i = l;i <= r;++i) a[i] += d;
        sum[p1] += 1LL*(r - l + 1) * d;
        return ;
    }
    for(int i = l;i <= R[p1];++i) a[i] += d;
    sum[p1] += 1LL*(R[p1] - l + 1) * d;
    for(int i = L[p2];i <= r;++i) a[i] += d;
    sum[p2] += 1LL*(r - L[p2] + 1)*d;
    for(int i = p1+1;i <= p2- 1;++i) sum[i] += 1LL*(R[i] - L[i] + 1)*d,add[i] += d;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i) scanf("%lld",&a[i]);
    //分块
    int t = sqrt(n);
    for(int i = 1;i <= t;++i){
        L[i] = (i-1)*t + 1;
        R[i] = i*t;
    }
    if(R[t] < n) t++,L[t] = R[t-1] + 1,R[t] = n;
    for(int i = 1;i <= t;++i){
        for(int j = L[i];j <= R[i];++j){
            pos[j] = i;
            sum[i] += a[j];
        }
    }
    
    for(int i = 1;i <= m;++i){
        char c;
        scanf("%s",&c);
        if(c == 'Q'){
            int b;
            scanf("%d",&b);
            printf("%lld\n",query(b));
        }
        else {
            int l,r;ll d;
            scanf("%d%d%lld",&l,&r,&d);
            Add(l,r,d);
        }
    }
}

分块2
给定一个长度为N的数列A,以及M条指令,每条指令可能是以下两种之一:
1、“C l r d”,表示把 A[l],A[l+1],…,A[r] 都加上 d。
2、“Q l r”,表示询问 数列中第 l~r 个数的和。
对于每个询问,输出一个整数表示答案。
区间修改,区间查询

ll add[500];
ll pos[N];
ll sum[500];
ll a[N];
int L[500],R[500];
ll query(int l,int r){
    if(l > r) swap(l,r);
    int p1 = pos[l],p2 = pos[r];
    ll ans = 0;
    if(p1 == p2){
        for(int i = l;i <= r;++i){
            ans += a[i];
        }
        return ans + (r - l + 1) * add[p1];
    }
    for(int i = l;i <= R[p1];++i) ans += a[i];
    ans += 1LL*(R[p1] - l + 1) * add[p1];
    for(int i = L[p2];i <= r;++i) ans += a[i];
    ans += 1LL*(r - L[p2] + 1) * add[p2];
    for(int i = p1 + 1;i <= p2-1;++i) ans += sum[i] + (R[i] - L[i] + 1)*add[i];
    return ans;
}
void  Add(int l,int r,int d){
    if(l > r) swap(l,r);
    int p1 = pos[l],p2 = pos[r];
    if(p1 == p2){
        for(int i = l;i <= r;++i) a[i] += d;
        sum[p1] += 1LL*(r - l + 1) * d;
        return ;
    }
    for(int i = l;i <= R[p1];++i) a[i] += d;
    sum[p1] += 1LL*(R[p1] - l + 1) * d;
    for(int i = L[p2];i<= r;++i) a[i] += d;
    sum[p2] += 1LL*(r - L[p2] + 1) * d;
    for(int i = p1+1;i<=p2-1;++i) add[i] += d;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i) scanf("%lld",&a[i]);
    int t = sqrt(n);
    for(int i = 1;i <= t;++i){
        L[i] = (i-1)*t + 1;
        R[i] = i*t;
    }
    if(R[t] < n) t++,L[t] = R[t-1] + 1,R[t] = n;
    for(int i = 1;i <= t;++i){
        for(int j = L[i];j <= R[i];++j){
            pos[j] = i;
            sum[i] += a[j];
        }
    }
    char Q;int l,r,d;
    for(int i = 1;i <= m;++i){
        scanf("%s",&Q);
        if(Q == 'Q'){
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(l,r));
        }
        else {
            scanf("%d%d%d",&l,&r,&d);
            Add(l,r,d);
        }
    }
}

数列分块入门系列
1、
在这里插入图片描述

int L[500],R[500];
ll a[N];
int pos[N];
ll add[500];
void divided(int n){
    int t = sqrt(n);
    for(int i = 1;i <= t;++i) L[i] = (i - 1)*t + 1,R[i] = i*t;
    if(R[t] < n) t++,L[t] = R[t-1] + 1,R[t] = n;
    for(int i = 1;i <= t;++i){
        for(int j = L[i];j <= R[i];++j) pos[j] = i;
    }
}
void Add(int l,int r,int d){
    int p = pos[l],q = pos[r];
    if(p == q){
        for(int i = l;i <= r;++i) a[i] += d;
    }
    else {
        for(int i = l;i <= R[p];++i) a[i] += d;
        for(int i = L[q];i <= r;++i) a[i] += d;
        for(int i = p+1;i<=q-1;++i) add[i] += d;
    }
}
ll query(int x){
    int p = pos[x];
    return a[x] + add[p];
}
int main(){
    int n,l,r,d;
    int op;
    scanf("%d",&n);
    for(int i = 1;i <= n;++i) scanf("%lld",&a[i]);
    divided(n);
    for(int i = 1; i <= n;++i){
        scanf("%d%d%d%d",&op,&l,&r,&d);
        if(!op) Add(l,r,d);
        else printf("%lld\n",query(r));
    }
}

2、
在这里插入图片描述

int L[500],R[500];
ll a[N];
int pos[N];
ll add[500];
vector<int> Q[500];
void divided(int n){
    int t = sqrt(n);
    for(int i = 1;i <= t;++i) L[i] = (i - 1)*t + 1,R[i] = i*t;
    if(R[t] < n) t++,L[t] = R[t-1] + 1,R[t] = n;
    for(int i = 1;i <= t;++i){
        for(int j = L[i];j <= R[i];++j) pos[j] = i,Q[i].push_back(a[j]);
        sort(Q[i].begin(),Q[i].end());
    }
}
void Add(int l,int r,int d){
    int p = pos[l],q = pos[r];
    if(p == q){
        for(int i = l;i <= r;++i) a[i] += d;
        Q[p].clear();
        for(int i = L[p];i <= R[p];++ i) Q[p].push_back(a[i]);
        sort(Q[p].begin(),Q[p].end());
    }
    else {
        for(int i = l;i <= R[p];++i) a[i] += d;
        Q[p].clear();
        for(int i = L[p];i <= R[p];++ i) Q[p].push_back(a[i]);
        sort(Q[p].begin(),Q[p].end());
        for(int i = L[q];i <= r;++i) a[i] += d;
        Q[q].clear();
        for(int i = L[q];i <= R[q];++ i) Q[q].push_back(a[i]);
        sort(Q[q].begin(),Q[q].end());
        for(int i = p+1;i<=q-1;++i) add[i] += d;
    }
}
ll query(int l,int r,ll d){
   int p = pos[l],q = pos[r];
   ll ans = 0;
   if(p == q){
       for(int i = l;i <= r;++i) if(a[i] + add[p] < d) ans ++;
       return ans;
   }
   for(int i = l;i <= R[p];++i) if(a[i] + add[p]<d) ans ++;
   for(int i = L[q];i <= r;++i) if(a[i] + add[q] < d) ans ++;
   for(int i = p +1 ;i <= q - 1;++i){
       int S = Q[i].size();
       int l1 = -1,r1 = S -1;
       while(l1 < r1){
           int mid = l1 + r1 + 1>> 1;
           if(Q[i][mid] >= d-add[i]) r1 = mid - 1;
           else l1 =mid;
       }
       if(l1 != -1) ans += l1 + 1;
   }
   return ans;
}
int main(){
    int n,l,r;ll d;
    int op;
    scanf("%d",&n);
    for(int i = 1;i <= n;++i) scanf("%lld",&a[i]);
    divided(n);
    for(int i = 1; i <= n;++i){
        scanf("%d%d%d%lld",&op,&l,&r,&d);
        if(!op) Add(l,r,d);
        else printf("%lld\n",query(l,r,d*d));
    }
}

3、
在这里插入图片描述

ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int L[1000],R[1000];
ll a[N];
int pos[N];
ll add[1000];
vector<ll> Q[1000];
void divided(int n){
    int t = sqrt(n);
    for(int i = 1;i <= t;++i) L[i] = (i - 1)*t + 1,R[i] = i*t;
    if(R[t] < n) t++,L[t] = R[t-1] + 1,R[t] = n;
    for(int i = 1;i <= t;++i){
        for(int j = L[i];j <= R[i];++j) pos[j] = i,Q[i].push_back(a[j]);
        sort(Q[i].begin(),Q[i].end());
    }
}
void Add(int l,int r,int d){
    int p = pos[l],q = pos[r];
    if(p == q){
        for(int i = l;i <= r;++i) a[i] += d;
        Q[p].clear();
        for(int i = L[p];i <= R[p];++ i) Q[p].push_back(a[i]);
        sort(Q[p].begin(),Q[p].end());
    }
    else {
        for(int i = l;i <= R[p];++i) a[i] += d;
        Q[p].clear();
        for(int i = L[p];i <= R[p];++ i) Q[p].push_back(a[i]);
        sort(Q[p].begin(),Q[p].end());
        for(int  i =L[q];i <= r;++i) a[i] += d;
        Q[q].clear();
        for(int i = L[q];i <= R[q];++ i) Q[q].push_back(a[i]);
        sort(Q[q].begin(),Q[q].end());
        for(int i = p+1;i<=q-1;++i) add[i] += d;
    }
}
ll query(int l,int r,ll d){
   int p = pos[l],q = pos[r];
   ll ans = -1e11;
   if(p == q){
       for(int i = l;i <= r;++i) if(a[i] + add[p] < d) ans = max(ans,a[i] +add[p]);
       if(ans <= -1e10) return -1;
       else return ans;
   }
   for(int i = l;i <= R[p];++i) if(a[i] + add[p]<d)  ans = max(ans,a[i] +add[p]);
   for(int i = L[q];i <= r;++i) if(a[i] + add[q] < d)  ans = max(ans,a[i] +add[q]);
   for(int i = p +1 ;i <= q - 1;++i){
       int S = Q[i].size();
       int l1 = -1,r1 = S -1;
       while(l1 < r1){
           int mid = l1 + r1 + 1>> 1;
           if(Q[i][mid] >= d-add[i]) r1 = mid - 1;
           else l1 =mid;
       }
       if(l1 != -1) ans = max(ans,Q[i][l1] +add[i]);
   }
   if(ans <= -1e10) return -1;
   else return ans;
}
int main(){
    int n,l,r;ll d;
    int op;
    scanf("%d",&n);
    for(int i = 1;i <= n;++i) a[i] = read();
    divided(n);
    for(int i = 1; i <= n;++i){
        op= read();l=read();r=read();d = read();
        if(!op) Add(l,r,d);
        else printf("%lld\n",query(l,r,d));
    }
}

4、
在这里插入图片描述

ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int L[1000],R[1000];
ll a[N];
int pos[N];
ll add[1000];
ll sum[1000];
vector<ll> Q[1000];
void divided(int n){
    int t = sqrt(n);
    for(int i = 1;i <= t;++i) L[i] = (i - 1)*t + 1,R[i] = i*t;
    if(R[t] < n) t++,L[t] = R[t-1] + 1,R[t] = n;
    for(int i = 1;i <= t;++i){
        for(int j = L[i];j <= R[i];++j) pos[j] = i,sum[i] += a[j];
    }
}
void Add(int l,int r,ll d){
    if(l > r) swap(l,r);
    int p = pos[l],q = pos[r];
    if(p == q) {
        for(int i = l;i <= r;++i) a[i] += d;
        sum[p] += (r - l + 1) * d;
        return ;
    }   
    for(int i = l;i <= R[p];++i) a[i] += d;
    sum[p] += (R[p] - l + 1) * d;
    for(int i = L[q];i <= r;++i) a[i] += d;
    sum[q] += (r - L[q]+ 1)*d;
    for(int i = p + 1;i <= q - 1;++i) add[i] += d;
}
ll query(int l,int r,ll mod){
    if(l > r) swap(l,r);    
    int p = pos[l],q = pos[r];
    ll ans= 0;
    if(p == q){
        for(int i = l;i <= r;++i) ans = (ans + a[i]+add[p]) % mod;
        return ans;
    }
    for(int i = l;i <= R[p];++i) ans = (ans + a[i] + add[p]) % mod;
    for(int i = L[q];i <= r;++i) ans = (ans + a[i] + add[q]) % mod;
    for(int i = p + 1;i <= q - 1;++i) ans = (ans + sum[i] + add[i]*(R[i] - L[i]+1))% mod;
    return ans;
}
int main(){
    int n,l,r;ll d;
    int op;
    scanf("%d",&n);
    for(int i = 1;i <= n;++i) a[i] = read();
    divided(n);
    for(int i = 1; i <= n;++i){
        op= read();l=read();r=read();d = read();
        if(!op) Add(l,r,d);
        else printf("%lld\n",query(l,r,d+1));
    }
}

7、
在这里插入图片描述
在这里插入图片描述

ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int L[1000],R[1000];
ll a[N];
int pos[N];
ll add[1000];
ll mul[1000];
void divided(int n){
    int t = sqrt(n);
    for(int i = 1;i <= t;++i) L[i] = (i - 1)*t + 1,R[i] = i*t;
    if(R[t] < n) t++,L[t] = R[t-1] + 1,R[t] = n;
    for(int i = 1;i <= t;++i){
        for(int j = L[i];j <= R[i];++j) pos[j] = i,mul[i] = 1;
    }
}
void Add(int l,int r,ll d){
    if(l > r) swap(l,r);
    int p = pos[l],q = pos[r];
    if(p == q) {
        for(int i = L[p];i <= R[p];++ i) a[i] = (a[i] * mul[p]) % mod;
        mul[p] = 1;
        for(int i = l;i <= r;++i) a[i] = (a[i] + d) % mod;
        return ;
    }   
    for(int i = L[p];i <= R[p];++i) a[i] = (a[i] * mul[p]) % mod;
    mul[p] = 1;
    for(int i = l;i <= R[p];++i) a[i] = (a[i] + d) % mod;
    for(int i = L[q];i <= R[q];++i) a[i] = (a[i] * mul[q]) % mod;
    mul[q] = 1;
    for(int i = L[q];i <= r;++i) a[i] = (a[i] + d) % mod;
    for(int i = p + 1;i <= q - 1;++i) add[i] += d;
}
void Mul(int l,int r,ll d){
    int p = pos[l],q = pos[r];
    if(p == q){
        for(int i = L[p];i <= R[p];++i) a[i] = (a[i]*mul[p]) % mod,a[i] = (a[i] + add[p])%mod;
        mul[p] = 1;add[p] = 0;
        for(int i = l;i <= r;++i) a[i] = (a[i] * d) % mod;
        return ;
    }
    for(int i = L[p];i <= R[p];++i) a[i] = (a[i]*mul[p]) % mod,a[i] = (a[i] + add[p])%mod;
    mul[p] = 1;add[p] = 0;
    for(int i = l;i <= R[p];++i) a[i] = (a[i] * d) % mod;

    for(int i = L[q];i <= R[q];++i) a[i] = (a[i]*mul[q]) % mod,a[i] = (a[i] + add[q])%mod;
    mul[q] = 1;add[q] = 0;
    for(int i = L[q];i <= r;++i) a[i] = (a[i] * d) % mod;

    for(int i = p + 1;i <= q - 1;++i) mul[i] = (mul[i] * d) % mod,add[i] = (add[i] * d)%mod;
}
ll query(int x){
   int p = pos[x];
   return mul[p] * a[x] + add[p];
}
int main(){
    int n,l,r;ll d;
    int op;
    scanf("%d",&n);
    for(int i = 1;i <= n;++i) a[i] = read();
    divided(n);//分块
    for(int i = 1; i <= n;++i){
        op= read();l=read();r=read();d = read();
        if(!op) Add(l,r,d);
        else if(op == 1) Mul(l,r,d);
        else printf("%lld\n",query(r)%mod);
    }
}

版权声明:本文为qq_43408238原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43408238/article/details/104259344

智能推荐

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

猜你喜欢

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...

[国家集训队]小Z的袜子(莫队)

[国家集训队]小Z的袜子 题目描述 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z把这NN只袜子从1到NN编号,然后从编号LL到RR(LL 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同...