所谓分块,就是将原序列处理成各个小块,目的是尽量地达到处理和询问之间的平衡。对于分块类问题,常常可以提取出“在给定区间内进行操作,或询问区间内满足给定条件的元素等”。接下来,例题。
首先是男神hzwer的博客链接 hzwer
因为下述题目皆由此改变。
问题 A: 小Z的课堂检测
时间限制: 1 Sec
内存限制: 128 MB
题目描述
大家都知道小Z的课总是十分快的(鬼知道为什么),然后我们阿M同学总是在上课时处于神游状态亦或是休眠状态,所以她对小Z到底讲了什么是一无所知。然而,小Z总是很坏地打断阿M的休眠状态,并问她问题。作为阿M的开黑好伙伴,你当然不希望阿M同学翻车(不然下一个回答问题的人就是你啦)。所以你需要编写个程序帮助阿M求小Z对于知识点到底讲的档次有多深。已知小Z在课上总会扯到涉及到N个知识点,小Z会进行M个动作(讲课或是提问阿M)。由于小Z比较古灵精怪,所以小Z的讲课时只会讲连续的知识点,并且对于这段区间内的知识点都提升一样的档次。而且,小Z也比较懒,所以小Z只会问阿M关于某一个知识点的了解程度。
输入
第一行读入N,表示小Z要涉及到N个知识点
第二行读入A[1],A[2]……A[N-1],A[N]表示小Z上几节课已经把第i个知识点的 难度提升到A[i]的难度
第三行读入M,表示小Z要进行M个动作
接下来M行,读入Choice
若Choice=1,则表示小Z要讲课啦
接下来读入L,R,X 表示小Z要对L到R这些连续的知识点提升难度X
若Choice=2,则表示小Z要提问啦
接下来读入K,表示小Z问阿M第K个知识点他已经讲到哪个难度了
输出
每行输出一个数表示阿M应该回答的正确答案
样例输入
10
1 2 3 4 5 6 7 8 9 10
5
1 2 3 4
2 3
1 3 4 5
2 5
1 5 8 5
7
5 3 7 7 5 8 5
9
1 2 7 -1
2 1
2 2
1 2 3 1
1 2 7 2
2 2
1 3 3 -1
2 3
2 1
样例输出
7
5
5
2
5
8
5
数据范围
对于50%的数据,N<=1000,M<=1000
对于100%的数据,N<=100000,M<=100000 |X|<=50000
|A[i]|<=50000;
简单思路:
首先是最暴力的思路,对于每次修改暴力for一遍,我们不难发现,这样做,并不是所有的修改在后面的过程中都会被询问到,所以我们考虑分块。
我们假设序列长n,每块大小为m,所以共有n/m个块。
对于每段修改[l,r],同样分块后,最多处理得到n/m个完整的块,和左右两段不完整的块,图示如下:
所以每次修改的时间复杂度为O(n/m+m),由基本不等式,易得,当n/m=m=sqrt(n)时,我们得到的块的大小是比较合理的。
对于查询x,ans=a[x]+tag[bl[x]]。
代码实现:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll tag[500005],bl[500005],a[500005];
ll cho,n,m,del,l,r,x,blo;
void deal(ll l,ll r,ll del)
{
for (int i=l;i<=min(r,blo*bl[l]);i++) a[i]+=del;
if (bl[l]!=bl[r])
for (int i=(bl[r]-1)*blo+1;i<=r;i++) a[i]+=del;
for (int i=bl[l]+1;i<=bl[r]-1;i++) tag[i]+=