题目链接：https://nanti.jisuanke.com/t/41298
题目大意：


有m个点通过给出n*n矩阵的坐标，得到权值：将原数所有数位上的数相加。

对于q个询问，输出 左下角为(x1,y1)，右上角为(x2，y2)的矩阵区域内所有可用点的权值经过处理后的和。 预处理一下O(n)。

对于每一次询问，都是一个矩形区域。 我们考虑二维前缀和，其答案相当于ans(x2,y2) - ans(x2,y1-1) - ans(x1-1,y2) + ans(x-1,y-1)，其中ans(x,y)代表1—— x，1——y矩形区域中所有值的和。

但是二维显然会爆空间，所以我们考虑如何降维。 我们可以将一个询问拆解成4个，用flag为1或-1标记此次询问的前缀和是要加还是减。 之后我们可以运用扫描线的方法，先按照x排序，然后对y进行映射，用树状数组维护映射后y上的值。用一条竖直 的扫描线不断向右扫，遇到一个询问点就查询一次。 但是这样我们使用扫描线是要将所有的点当作修改操作的，而不能提前加入树状数组，否则答案会出问题。 所以我们将所有的m个点和4*q个询问加入操作合集，

查询flag为-1或1，修改flag为2，按照先x、次先y、再次先修 改的顺序排序，用一条平行于y轴的线从左向右扫过整个横坐标区间，用树状数组维护当前投影到y轴上的值。每当 遇到修改操作，直接add树状数组中的值进行维护，遇到查询操作直接从树状数组中查询。 理论时间复杂度为O((m+4 * q)log(m+4 * q))；

思考：非常巧妙的思路：就是把查询，添加全部转化成操作。然后直接处理每一个操作就ok。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll cal(int x, int y, int n)//蛇形填数a[i][j]
{
	int layer = min(min(x, y), n - max(x, y) + 1);
	if ((layer << 1) > n)
	{
		return 1LL * n * n;
	}
	long long st = 1LL * n * n - 1LL * (n - (layer << 1) + 2) * (n - (layer << 1) + 2) + 1;
	if (x >= y)
	{
		return st + ((n - layer) << 1) + 2 - x - y;
	}
	return st + ((n - (layer << 1) + 1) << 1) + x + y - (layer << 1);
}

const int maxn=1e6+5;
const int maxm=1e5+5;

struct quest{
    int x, y, flag, id;
}q[maxm<<3];

int ans[maxm], sum[maxn];

void add(int p, int y)//p位置+y
{
    while(p<=maxm)
    {
        sum[p]+=y;
        p+=(p&-p);
    }
}

int cx(int p)         //前缀和
{
    int ans=0;
    while(p)
    {
        ans+=sum[p];
        p-=(p&-p);
    }
    return ans;
}

struct point{
    int x, y, ans;
}p[maxm];

bool cmp(quest a, quest b){
    return (a.x<b.x)||(a.x==b.x&&a.y<b.y)||(a.x == b.x && a.y == b.y && a.flag > b.flag);
}

int work(ll x){
    int ret=0;
    while(x){
        ret+=x%10;
        x/=10;
    }
    return ret;
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--){

        memset(sum, 0, sizeof(sum));
        memset(ans, 0, sizeof(ans));
        int n, m ,Q;
        scanf("%d%d%d", &n, &m, &Q);
        
        //把添加转化成操作
        for(int i=1; i<=m; i++){
            scanf("%d%d", &p[i].x, &p[i].y);
            ll pk=cal(p[i].x, p[i].y, n);
            p[i].ans=work(pk);
            q[4*Q+i].x=p[i].x;
            q[4*Q+i].y=p[i].y;
            q[4*Q+i].id=Q+i;
            q[4*Q+i].flag=2;
        }
        int cut=4*Q+m;
        
        //把添加转化成操作
        for(int i=1; i<=Q; ++i){
            int x, y, xx, yy;
            scanf("%d%d%d%d", &x, &y, &xx, &yy);
            q[4*(i-1)+1].x=x-1; q[4*(i-1)+1].y=y-1; q[4*(i-1)+1].id=i; q[4*(i-1)+1].flag = 1;
            q[4*(i-1)+2].x=xx; q[4*(i-1)+2].y=yy; q[4*(i-1)+2].id=i; q[4*(i-1)+2].flag = 1;
            q[4*(i-1)+3].x=x-1; q[4*(i-1)+3].y=yy; q[4*(i-1)+3].id=i; q[4*(i-1)+3].flag = -1;
            q[4*(i-1)+4].x=xx; q[4*(i-1)+4].y=y-1; q[4*(i-1)+4].id=i; q[4*(i-1)+4].flag = -1;
        }
        sort(q+1, q+cut+1, cmp);
        
        //运行所以的操作
        for(int i=1; i<=cut; ++i){
            if(q[i].flag==2){
                int now=q[i].id-Q;
                add(q[i].y, p[now].ans);
            }
            else{
                ans[q[i].id]+=q[i].flag*cx(q[i].y);
            }
        }
        for(int i=1; i<=Q; ++i){
            printf("%d\n", ans[i]);
        }
    }

	return 0;
}
/* 1 3 4 1 1 1 2 2 3 3 2 3 1 1 1 1 */