分块の基础，（例题）HDU1556

算法简述

把一个长度为a序列分成 a√ 份，对于每一个块分别进行处理，对于一些没有完全覆盖一个块的情况，我们暴力处理就可以了，这是一个根号级别的算法（感觉好难解释啊QAQ）

适用范围

与区间修改，区间查询有关系的一些问题，但是要维护的值不能合并，这个时候就可以用分块了（或者确定用分块不会超时，然后又比较懒233）

例题：

Problem Description N个气球排成一排，从左到右依次编号为1,2,3….N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽”牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？

Input 每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。 当N = 0，输入结束。

Output 每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。

Sample Input 3 1 1 2 2 3 3 3 1 1 1 2 1 3 0

Sample Output 1 1 1 3 2 1

这是一道区间修改＆单点查询的题目，这一题显然可以用树状数组or线段树做，但是这一题也可以用分块来解决（虽然比较慢） 首先是区间修改，可以想象一下，在分块之后被覆盖的点会被分成3个部分： 第一个部分：一个块的后面一部分被覆盖 第二个部分：一个块被完全覆盖 第三个部分：一个块的前面一部分被覆盖 显然只有第一和第三个部分都只有一个块会出现这一种情况，所以我们可以暴力去做，而对于第二个部分，我们可以用另外一个数组来存储这一个块整体的add的情况，在最后查询答案的时候再重新加上就好了。 单点查询就用当前点所在块的add值加上这个点本身的值就可以了

关于时间复杂度

第一个和第三个部分只有一个块，而一个块的大小是 a√ 的，而对于第二种情况，对于每一个块都是 O（1） 的，而一共只有 a√ 个块，所以整个算法的时间复杂度应该是 aa√ 的。

贴代码

var a:array[0..100005]of longint; b:array[0..400]of longint; i,j,k,l,n,m,x,y,z,p,t,t1,t2,pp,xx,yy:longint; procedure work; begin readln(n); if n=0 then halt; fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); t:=trunc(sqrt(n)); if t*t<n then inc(t); if t*t<n+t then p:=t else p:=t-1;//t为块的个数，p为除了最后一个块之外其他块的大小 z:=1; for i:=1 to n do begin readln(x,y); while (x mod p<>1) and (x<=y) do begin a[x]:=a[x]+z; inc(x); end; while (y mod p<>0) and (y>=x) do begin a[y]:=a[y]+z; dec(y); end; //这一部分是处理上述的第一和第三种情况的~ x:=x div p+1; y:=y div p; for j:=x to y do inc(b[j],z);//第二种情况 end; for i:=1 to n do begin y:=i; x:=y; if y mod p=0 then dec(y); y:=y div p+1; if i<n then write(a[x]+b[y],' ') else writeln(a[x]+b[y]);//把两个部分加起来后输出~ end; end; begin // assign(input,'t1'); reset(input); while true do work; // close(input); end.