题解 P3755 【[CQOI2017]老C的任务】
题意简述：
平面内有N个点，每个点有一个值Pi和坐标(xi,yi)，有M次查询，查询以(x1,y1)和(x2,y2)为两对角顶点的矩形内部点的值之和。
Solution:
本题做法很多：
CDQ分治，KD-tree等算法和数据结构可以解决本题。
这里介绍一种更加通俗易懂的解法，分块，借鉴了洛谷中@最后一颗星辰 的题解。
不过我觉得那篇题解略微简述，在此作详细的补充和解释。
对于暴力算法，二维前缀和可以解决部分数据，但是N,M太大，数组开不下，我们只能考虑另外的解法。
首先是预处理，先以所有点的x坐标为第一关键字排序，按照数列分块的老套路，把每sqrt(N)个点分为一块，共sqrt(N)+1块。
这时候用数组存下每块的点，统计功率的前缀和，保存下来，具体地：
我们将数组去重，这样方便进行查找，因为只需要看排序后的x坐标数组，若求出xi在排序后数组的某个位置px，那么px/t1(t1是每块的长度)便是属于第几块了，这是一个显然的事情，可以配合代码理解！
n=read();ask=read();
t1=sqrt(n);t2=n/t1+1;
for(ll i=1;i<=n;i++)
{
xx[i]=read();yy[i]=read();zz[i]=read();
dx[i]=xx[i];
}
sort(dx+1,dx+n+1);
ll tx=unique(dx+1,dx+n+1)-dx-1;//去重后的数组长度
for(ll i=1;i<=n;i++)
{
ll px=lower_bound(dx+1,dx+tx+1,xx[i])-dx;//大于等于xx[i]的第一个位置(这里实际上就是查找了xx[i]的位置，因为必然存在)
ll Z=px/t1+1;
a[Z][++js[Z]].x=xx[i];
a[Z][js[Z]].y=yy[i];
a[Z][js[Z]].p=zz[i];
}
for(ll i=1;i<=t2;i++)
{
sort(a[i]+1,a[i]+js[i]+1,cmp2);
for(ll j=1;j<=js[i];j++)
{
sum[i][j]=sum[i][j-1]+a[i][j].p;//处理每块的基站功率的前缀和,sum[i][j]表示第i块前j个基站功率的和（方便统计答案）
b[i][j]=a[i][j].y;
}
}再来看查询，对于一个矩形，可以先计算中间的部分，再计算旁边的部分。
为什么会有“中间”和“旁边”之分呢？我们对点数组进行分块的时候，对于一个给定的矩形，可能会有点没有在一个完整块中，这时候就需要我们再次统计这些点。
具体地：对于两端的点，枚举块内每个点，判断是否在矩形内部，如果在则统计答案。
对于中间的点，二分查找左右界点，二分查找上下界点（这里有很多细节需要注意）。
计算出边界后加上之前统计的每块功率前缀和即可。
该算法的时间复杂度为:O(Nsqrt(n)log2(n))，优化常数可以AC此题。
易错点：
二分查找时，边界的取或者不取需要特别注意！！！
要判断点是否是同一块，若不是，由于前面计算了块p的贡献，再计算一次块q的贡献(同一块无需再计算)。
好了，这道直奔主题的分块题就到此结束了，注释在代码里写得比较清楚。
#include<bits/stdc++.h>
#define N 100010
#define Q 1005
#define ll long long
using namespace std;
struct M
{
ll x,y,p;
}a[Q][Q];//a[i][j]:分块后的第i块的第j个数，num[i](js[i])表示第i块的数的个数(这里看好久才看出来)
ll ask,dx[N],xx[N],yy[N],zz[N],t1,t2,a1,a2,b1,b2,n,js[N],l[N],r[N],sum[Q][Q],b[Q][Q];//t1:块数 t2:块的长度 sum:一个块的前缀功率之和
ll cmp1(M A,M B)
{
if(A.x<B.x) return 1;
else return 0;
}
ll cmp2(M A,M B)
{
if(A.y<B.y) return 1;
else return 0;
}
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main()
{
n=read();ask=read();
t1=sqrt(n);t2=n/t1+1;
for(ll i=1;i<=n;i++)
{
xx[i]=read();yy[i]=read();zz[i]=read();
dx[i]=xx[i];
}
sort(dx+1,dx+n+1);
ll tx=unique(dx+1,dx+n+1)-dx-1;//去重后的数组长度
for(ll i=1;i<=n;i++)
{
ll px=lower_bound(dx+1,dx+tx+1,xx[i])-dx;//大于等于xx[i]的第一个位置(这里实际上就是查找了xx[i]的位置，因为必然存在)
ll Z=px/t1+1;
a[Z][++js[Z]].x=xx[i];
a[Z][js[Z]].y=yy[i];
a[Z][js[Z]].p=zz[i];
//a[Z][]
}
for(ll i=1;i<=t2;i++)
{
sort(a[i]+1,a[i]+js[i]+1,cmp2);
for(ll j=1;j<=js[i];j++)
{
sum[i][j]=sum[i][j-1]+a[i][j].p;//处理每块的基站功率的前缀和,sum[i][j]表示第i块前j个基站功率的和（方便统计答案）
b[i][j]=a[i][j].y;
}
}
for(ll i=1;i<=ask;i++)
{
a1=read();b1=read();a2=read();b2=read();
ll px1=lower_bound(dx+1,dx+tx+1,a1)-dx;
ll px2=upper_bound(dx+1,dx+tx+1,a2)-dx;/////二分查找左右边界点
// cout<<px1<<" "<<px2<<endl<<endl;
ll ans=0;
ll p=px1/t1+1,q=px2/t1+1;
for(ll j=p+1;j<=q-1;j++)//中部查找
{
ll py1=lower_bound(b[j]+1,b[j]+js[j]+1,b1)-b[j];
ll py2=upper_bound(b[j]+1,b[j]+js[j]+1,b2)-b[j]-1;///上下界点查找
ans=ans+sum[j][py2]-sum[j][py1-1];
}
for(ll j=1;j<=js[p];j++)//js[p]：块p的大小
//两端查找
{
if(a[p][j].x>=a1&&a[p][j].y>=b1&&a[p][j].x<=a2&&a[p][j].y<=b2)
{
ans=ans+a[p][j].p;
}
}
if(p!=q) //是否位于同一块内部,若不是，由于前面计算了块p的贡献，再计算一次块q的贡献(同一块无需再计算)
{
for(ll j=1;j<=js[q];j++)
{
if(a[q][j].x>=a1&&a[q][j].y>=b1&&a[q][j].x<=a2&&a[q][j].y<=b2)
{
ans=ans+a[q][j].p;//在范围内，加上基站功率数
}
}
}
printf("%lld\n",ans);
}
return 0;
}