猫史档案馆

 

 

 

 

 

 

序列上的分块问题

 

 

 

 

回顾&引入

 

 

• 树状数组：二进制划分与倍增思想
• 线段树分治：分治思想
• 它们把序列中的元素聚合成“段”并维护，每个区间的信息可以快速由几个已有的“段”合成。
• 通过适当的划分，预处理一部分，用空间换时间，时空平衡——分块

 

 

分块算法是一种很常见的根号算法，一般它的时间复杂度会带根号。 
分块和线段树的区别在于，分块算法可以维护一些线段树维护不了的东西，例如单调队列等，线段树能维护的东西必须能够进行信息合并，而分块则不需要。不过，它们也有共同点，分块和线段树一样，分块需要支持类似标记合并的东西。 
简单来说，分块算法就是优化过后的喵。

 

 

 

 

模板代码

 

 

 

1.区间加法，单点查值

 

 

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 ai，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若 opt=0，表示将位于 [l,r] 的之间的数字都加 c。

若 opt=1，表示询问 ar 的值（ l 和 c 忽略）。

对于每次询问，输出一行一个数字表示答案。

 

样例输入：

4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0

 

样例输出：

2
5

 

 

 

 

• 大段维护，局部朴素
•  
• 对于每次区间操作：
• 不完整的块的O(√n)个元素怎么处理
• O(√n)个整块怎么处理
• 要预处理什么信息（复杂度不能超过后面的操作）

 

首先是add操作，将[l,r]之间的元素都加c,对于整块的内容来说，直接维护一个lazy标记即可，lazy标记就记录这个整块中被add了多少（注意不是记录加了多少次，是记录该整块中所有加的值的总和）;而对于非整块来说，因为块内的元素并不是太多，喵也是可以。接着就是quary操作，这里比较简单的就是，它是个单点查询，故查询函数的返回值就是a[r]+(a[r]所在块中的lazy值)。

预处理和维护内容：先要把n给分成各个小块，经由其他大佬们的分析，分成每个块中最多放sqrt(n)个元素的时间复杂是最小的，在这里我们就不必再多考虑了直接拿来用就是。用blong[i]来记录原数组第i个元素在第几个块中；L[x]记录第x个块的左边界，R[x]记录第x个块的右边界；当然也少不了去维护lazy数组，lazy[x]记录的就是第x块被add了多少的值。

 

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50010;
int n,m,block,L[N],R[N],blong[N],num;
ll a[N],lazy[N];
/*
a[i]原数列元素
block块的大小
num块的个数 
blong[i]表示属于哪一块
L[i]表示第i块的左边界
R[i]表示第i块的右边界 
lazy[i]对第i块的懒惰标记 
*/
void build()
{
	block=sqrt(n);//每个块的大小，sqrt(n)时复杂度最低 
	if(n%block==0) num = n/block;
	else num = n/block+1;  //最后一个快可能不够block个 
	for(int i=1;i<=num;i++)
	{
		L[i]=(i-1)*block+1,R[i]=i*block;//每个块的左右边界	
	} 
	R[num] = n; //最后一块特殊处理
	for(int i=1;i<=n;i++)
	{
		blong[i]=(i-1)/block + 1;//块的个数从1开始，So不应写成i/block 
	}
	 
}
void add(int l,int r,ll c )
{
	if(blong[l]==blong[r])//在同一块中，直接喵处理 
	{
		for(int i=l;i<=r;i++)
		{
			a[i]+=c;
		}
		return; 
	}
	for(int i=l;i<=R[blong[l]];i++)//左侧不完整快 
	{
		a[i]+=c;
	}
	for(int i=blong[l]+1;i<=blong[r]-1;i++)//处理中间的完整快 
	{
		lazy[i] += c; 
	} 
	for(int i=L[blong[r]];i<=r;i++)//右侧不完整块 
	{
		a[i]+=c;
	} 
} 
ll quary(int x)
{
	return a[x]+lazy[blong[x]];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build();
	m=n;
	while(m--)
	{
		int op,l,r;
		ll c;
		scanf("%d%d%d%lld",&op,&l,&r,&c);
		if(op==0)
		{
			add(l,r,c);
		}
		else{
			printf("%lld\n",quary(r));
		}
	}
	return 0;
}

 

 

 

 

 

模板二

 

 

 

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 ai，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若 opt=0，表示将位于 [l,r] 的之间的数字都加 c。

若 opt=1，表示询问 [l,r] 中，小于 c2 的数字的个数。

对于每次询问，输出一行一个数字表示答案。

 

样例输入：

4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2

 

样例输出：

3
0
2

 

 

 

 

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50010;
int n,m,L[N],R[N],block,num,blong[N];
ll a[N],lazy[N];
vector<ll> v[N];
void build()
{
    block=sqrt(n);//每个块的大小，sqrt(n)时复杂度最低 
    if(n%block==0) num = n/block;
    else num = n/block + 1;  //最后一个块可能不够block个 
    for(int i=1;i<=n;i++)
    {
        blong[i]=(i-1)/block + 1;//块的个数从1开始，So不应写成i/block 
        v[blong[i]].push_back(a[i]);
    }
    for(int i=1;i<=num;i++)
    {
        L[i]=(i-1)*block+1,R[i]=i*block;//每个块的左右边界
    } 
    R[num] = n; //最后一块特殊处理  
    for(int i=1;i<=num;i++)
    {
        sort(v[i].begin(),v[i].end());
    }
}
void resort(int x)//对x块进行排序
{
    v[x].clear();
    for(int i=L[x];i<=R[x];i++)
    {
        v[x].push_back(a[i]);   
    } 
    sort(v[x].begin(),v[x].end());
} 
void update(int l,int r,ll c)
{
    if(blong[l]==blong[r])
    {
        for(int i=l;i<=r;i++)
        {
            a[i]+=c;
        }
        resort(blong[l]);
        return;
    }
    for(int i=l;i<=R[blong[l]];i++)
    {
        a[i]+=c;
    }
    for(int i=blong[l]+1;i<=blong[r]-1;i++)
    {
        lazy[i]+=c;
    }
    for(int i=L[blong[r]];i<=r;i++)
    {
        a[i]+=c;
    }
    resort(blong[l]);
    resort(blong[r]);
}
int quary(int l,int r,ll c)
{
    int ans=0;
    if(blong[l]==blong[r])
    {
        for(int i=l;i<=r;i++)
        {
            if(a[i]+lazy[blong[i]]<c)
            ans++;
        }
        return ans;
    }
    for(int i=l;i<=R[blong[l]];i++)
    {
        if(a[i]+lazy[blong[i]]<c)
        ans++;
    }
    for(int i=blong[l]+1;i<=blong[r]-1;i++)
    {
        //我么要查询的是a[i]+lazy[blong[i]]>=c的第一个位置（vector下标是从零开始的）
        //移项后也就是a[i]>=c-lazy[blong[i]]啦，注意此a[i](指vector容器中的元素)非彼a[i]（指原数组)
        ans += lower_bound(v[i].begin(),v[i].end(),c-lazy[i])-v[i].begin();
    }
    for(int i=L[blong[r]];i<=r;i++)
    {
        if(a[i]+lazy[blong[i]]<c)
        ans++;
    }
    return ans;
}
inline int read()
{
    int 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;
}
inline ll Read(){
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=Read();
    build();
    m=n;
    while(m--)
    {
        int op,l,r;
        ll c;
        op=read(),l=read(),r=read();c=Read();
        if(op==0) update(l,r,c);
        else printf("%d\n",quary(l,r,c*c));
    }
    return 0;
}

 

 

 

 

 

模板三

 

 

 

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，区间求和。

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 ai，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若 opt=0，表示将位于 [l,r] 的之间的数字都加 c。

若 opt=1，表示询问 [l,r] 的所有数字的和 mod(c+1) 。

对于每次询问，输出一行一个数字表示答案。

 

样例输入：

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

 

样例输出：

1
4

 

 

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50010;
ll a[N],n;
//b[i]=a[i]-a[i-1] 
ll tr1[N],tr2[N];//sum1用来维护 b[i]的前缀和，sum2用来维护i*b[i]的前缀和 
ll lowbit(ll x)
{
    return x & -x;
}
void add(ll tr[],ll x,ll c)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        tr[i]+=c;
    }
}
ll getsum(ll tr[],ll x)
{
    ll res=0;
    for(int i=x;i;i-=lowbit(i))
    {
        res+=tr[i];
    } 
    return res; 
}
ll getans(ll x)
{
    return (x+1)*getsum(tr1,x)-getsum(tr2,x);
}
int main()
{
    scanf("%lld",&n);
    ll m=n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        ll c=a[i]-a[i-1];
        add(tr1,i,c);
        add(tr2,i,i*c);
    }
    while(m--)
    {
        ll op,l,r,c;
        scanf("%lld%lld%lld%lld",&op,&l,&r,&c);
        if(op==1)
        {
            printf("%lld\n",(getans(r)-getans(l-1))%(c+1));
        }
        else{
            add(tr1,l,c),add(tr2,l,l*c);
            add(tr1,r+1,-c),add(tr2,r+1,-c*(r+1));
        }
    }
    return 0;
}

 

 

 

 

 

模板四

 

 

 

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 ai，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若 opt=0，表示将位于 [l,r] 的之间的数字都加 c。

若 opt=1，表示询问 [l,r] 中 c 的前驱的值（不存在则输出 −1 ）。

对于每次询问，输出一行一个数字表示答案。

 

 

 

 

 

 

模板五

 

 

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间开方，区间求和。

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 ai，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若 opt=0，表示将位于 [l,r] 的之间的数字都开方。对于区间中每个 ai(l≤i≤r, ai←⌊ai−−√⌋

若 opt=1，表示询问 [l,r] 的所有数字的和 。

对于每次询问，输出一行一个数字表示答案。

 

 

 

 

 

模板六

 

 

给出一个长为 n 的数列，以及 n 个操作，操作涉及单点插入，单点询问，数据随机生成。

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 ai，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若 opt=0，表示在第 l 个数字前插入数字 r ( c 忽略）。

若 opt=1，表示询问 ar 的值 ( l 和 c 忽略）。

对于每次询问，输出一行一个数字表示答案。

 

 

 

 

 

模板七

 

 

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间乘法，区间加法，单点询问。

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 ai，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若 opt=0，表示将位于 [l,r] 的之间的数字都加 c。

若 opt=1，表示将位于 [l,r] 的之间的数字都乘 c。

若 opt=2，表示询问 ar 的值 mod 10007 ( l 和 c 忽略）

对于每次询问，输出一行一个数字表示答案。

 

 

 

 

 

 

模板八

 

 

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c。

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 ai，以空格隔开。

接下来输入 n 行询问，每行输入三个数字 l、r、c，以空格隔开。

表示先查询位于 [l,r] 的数字有多少个是 c，再把位于 [l,r] 的数字都改为 c。

对于每次询问，输出一行一个数字表示答案。

 

 

 

 

 

习题：作诗

 

 

原题链接：https://www.luogu.com.cn/problem/P4135

 

 

 

 

分块思想定了就好办了。

注意这题无良卡时间和空间（虽然很大程度和bzoj老爷机有关）

我们还是预处理两个数组：

1.sum[i][j]：i元素在前j块出现的次数。

2.ans[i][j]：i～j块的正偶数个数的个数。

显然预处理之后对于询问我们就有了如下算法：

1.跨度<=2个块长度：直接喵。

2.跨度>2个块长度：显然区间一定跨过了至少一些/个连续的块，这些连续的块的正偶数个数的个数，先更新到cur（即最终答案中），然后枚举非整块区间内的数i，统计i在非整块区间内的个数t，如果：

1.连续的块内没有i：那么我们判断t的奇偶即可，如果是偶数，cur++。

2.连续的块内有i：

　　设连续的块内i的个数为c。

　　1.c偶数，t奇数：cur--；

　　2.c奇数，t奇数：cur++；

返回cur即可。

Q1：ans数组怎么处理？

A1：我们可以很轻松处理sum数组，然后用和上面的方法一样的思想求解ans即可。

大致如下：

1.ans[i][j]=a[i][j-1]；

(1.1：清空数组，注意只清当前块的数，不然TLE没话说）

2.统计j块元素的出现个数；

3.如同上面的方法判断即可。