题目链接：https://nanti.jisuanke.com/t/41298
题意：给一个n * n的螺旋矩阵，n保证是奇数，取一些点使其、获得价值，价值为数位和，然后再给q次查询，求矩阵中的价值总和
题解：树状数组求解，将所有有价值的点和需要处理的有关于矩形的点都先记录下来，关于矩形价值总和的点，一个矩形有四个点。例如x1,y1,x2,y2的价值总和是Sx1,x1 - Sx1- 1,y2 - Sx2,y1 - 1 + Sx2,y2，所以可以有思路先将所有的点按照y的坐标值递增排序，之后就可以保证每次求x轴上的总和就是0，0 到 i，j的价值总和，这样就可以将y处理掉，之后保存答案后输出就好了
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define eps 1e-4 #define bug printf("********* ") #define debug(x) cout<<#x"=["<<x<<"]" <<endl; typedef long long LL; typedef long long ll; const int maxn = 1e6 + 5; const int mod = 998244353; struct node{ int flag; LL x,y,id; LL val; friend bool operator < (node a,node b) { if(a.y == b.y) { if(a.x == b.x) return a.flag < b.flag; return a.x < b.x; } return a.y < b.y; } }p[maxn]; LL re_val(LL x) { LL sum = 0; while(x > 0) { sum += x % 10; x /= 10; } return sum; } LL index(LL y,LL x,LL n) { //求的n * n的矩阵中(x,y)的值是多少 LL mid = (n + 1) / 2; LL p = max(abs(x - mid), abs(y - mid)); LL ans = n * n - (1 + p) * p * 4; LL sx = mid + p, sy = mid + p; if (x == sx && y == sy) return ans; else { if (y == sy || x == sx - 2 * p) return ans + abs(x - sx) + abs(y - sy); else return ans + 8 * p - abs(x - sx) - abs(y - sy); } } LL c[maxn],ans[maxn]; void init() { memset(c,0,sizeof c); memset(ans,0,sizeof ans); } LL lowbit(LL x) { return x & -x; } LL sum(LL i) { LL res = 0; while(i) { res += c[i]; i -= lowbit(i); } return res; } LL n; void add(LL i,LL t) { while(i <= maxn) { c[i] += t; i += lowbit(i); } } int main() { int t; scanf("%d",&t); while(t--) { init(); LL m,q; scanf("%lld %lld %lld",&n,&m,&q); int cnt = 0; for(int i = 1;i <= m; i++) { LL x,y; scanf("%lld %lld",&x,&y); p[++cnt] = {0, x, y, -1, re_val(index(x,y,n))}; } for(int i = 1; i <= q; i++) { LL x1,y1,x2,y2; scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2); p[++cnt] = {1, x1 - 1, y1 - 1, i, 1}; p[++cnt] = {1, x1 - 1, y2, i, -1}; p[++cnt] = {1, x2, y1 - 1, i, -1}; p[++cnt] = {1, x2, y2, i, 1}; } sort(p + 1, p + 1 + cnt); for(int i = 1; i <= cnt; i++) { if(p[i].flag == 1) ans[p[i].id] += sum(p[i].x) * p[i].val; else add(p[i].x,p[i].val); } for(int i = 1; i <= q; i++) printf("%lld ",ans[i]); } }