分块例题1

题面描述

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

输入格式

第一行输入一个数字 n

第二行输入 n 个数字，第 i 个数字为a[i]，以空格隔开

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

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

若 opt = 1，表示询问 a[r] 的值（l 和 c 忽略）

输出格式

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

样例

这个题是可以用树状数组和线段树写的，但他让用分块，分块着实不是很会，分块也就是一个数据结构，这个也可以暴力做，分块与暴力的区别，就是把暴力预处理成了几个块，到时候能调用就直接掉，不行再暴力QAQ而且分块的代码也不短QAQ

代码

#include<bits/stdc++.h>
using namespace std;
int pos[510010],a[510010],l1[510010],r1[510010],add[510010],t;
void ch(int l,int r,int d)
{
	//cout<<a[1]<<"                  "<<endl;
	int p=pos[l],q=pos[r];
	if(p==q)
	{
		for(int i=l;i<=r;i++)
		{a[i]+=d;
		//cout<<a[i]<<endl;
		}
		
	}
	else
	{
		for(int i=p+1;i<=q-1;i++)
		add[i]+=d;
		for(int i=l;i<=r1[p];i++)
		{
			a[i]+=d;
		//cout<<a[i]<<endl;
		}
		//a[i]+=d;
		for(int i=l1[q];i<=r;i++)
		{
			a[i]+=d;
		//cout<<a[i]<<endl;
		}
	//	a[i]+=d;
	}
 } 
 int ask(int x)
 {
 	return a[x]+add[pos[x]];
 }
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	t=sqrt(n);
	for(int i=1;i<=t;i++)
	{
		l1[i]=(i-1)*sqrt(n)+1;
		r1[i]=i*sqrt(n);
	}
	if(r1[t]<n)
	{
		t++;
		l1[t]=r1[t-1]+1;
		r1[t]=n;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=l1[i];j<=r1[i];j++)
		{
			pos[j]=i;
		 } 
	}
	for(int i=1;i<=n;i++)
	{
		int opt,l,r,c;
		cin>>opt>>l>>r>>c;
		if(opt==0)
		ch(l,r,c);
		if(opt==1)
		{
//			for(int i=1;i<=n;i++)
//			cout<<a[i]<<' ';
//			cout<<endl;
			cout<<ask(r)<<endl;
		}
	}
}