A对于知道了解主席树性质的人来说，的确算是一个模板题目
题目在于给一个螺旋矩阵，以及一些权值，问在二维区间内权值和是多少？
对于螺旋矩阵权值来说，计算每个点的值，只需要O1计算即可。我们可以通过计算内部圈数得到计算外围的权值，再加当前圈数即可
而对于二维的区间和，我们知道其实主席树已经是二维的了，因为我们在每个节点都新开一棵线段树。并且主席树是动态开点的，这样就比较简单了。
我们考虑把所有加入有权值的点进行排序，那么区间和，转换为了二维偏序前缀和。
第一维是x，也就root[ i ]纬度，第二维是y，也就是主席树内部维护的前缀和。
我们通过lower_bound+upper_bound查询x坐标对应区间内x来说，它所在的主席树的区间的版本
然后同理我们可以查lower_bound+upper_bound查询y坐标对于区间内y来说，它在主席树上的区间和。
这样我们就能很容易的计算出答案。
注意由于我们查询区间坐标的时候
lx=lower_bound(vx.begin(),vx.end(),lx)-vx.begin()+1
rx=lower_bound(vx.begin(),vx.end(),rx）-vx.begin()
因为我们查询的是，第一个大于等于lx的，以及第一个小于等于rx，
如果这个值没有的话，rx<lx，我们必须特判情况。否则线段树会超时。
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<vector> #define LL long long using namespace std; const int maxx = 1e5+10; struct node{ int l,r; LL w; }tree[maxx*40]; int root[maxx]; struct Node{ int x,y; LL w; bool operator < (const Node & s)const{ return x<s.x; } }point[maxx]; vector<int>vx; vector<int>vy; LL n; int cnt; LL get_val(LL x,LL y){ LL k=min(x,min(n-x+1,min(y,n-y+1))); LL minn=k; k--; LL in=n-2*k; LL out=n*n-in*in; if (x==n-minn+1){ return out+n-k-y+1; }else if (y==minn){ return out+in+n-k-x; }else if (x==minn){ return out+in*2-2+y-k; }else { return out+in*3-3+x-k; } } ////主席树维护y偏序的区间和 void inserts(int l,int r,int pre,int &now,int pos,LL w){ now=++cnt; tree[now]=tree[pre]; tree[now].w+=w; if(l==r){ return ; } int mid=(l+r)>>1; if(pos<=mid)inserts(l,mid,tree[pre].l,tree[now].l,pos,w); else inserts(mid+1,r,tree[pre].r,tree[now].r,pos,w); } LL query(int L,int R,int l,int r,int ql,int qr){ //区间查询 if(ql<=l && r<=qr){ return tree[R].w-tree[L].w; } int mid=(l+r)>>1; LL ans=0; if (qr<=mid){ return query(tree[L].l,tree[R].l,l,mid,ql,qr); }else if (ql>mid){ return query(tree[L].r,tree[R].r,mid+1,r,ql,qr); }else { return query(tree[L].l,tree[R].l,l,mid,ql,qr)+query(tree[L].r,tree[R].r,mid+1,r,ql,qr); } } LL cal(LL x) { LL sum = 0; while (x) sum += x % 10, x /= 10; return sum; } int main(){ int T; int m,p; scanf("%d",&T); while(T--){ cnt=0; memset(root,0,sizeof(root)); memset(tree,0,sizeof(tree)); scanf("%lld%d%d",&n,&m,&p); vx.clear(); vy.clear(); for(int i=1;i<=m;i++){ scanf("%d%d",&point[i].x,&point[i].y); point[i].w=cal(get_val(point[i].x,point[i].y)); vx.push_back(point[i].x); vy.push_back(point[i].y); } sort(point+1,point+1+m); sort(vx.begin(),vx.end()); sort(vy.begin(),vy.end()); vy.erase(unique(vy.begin(),vy.end()),vy.end()); int sz=vy.size(); for (int i=1;i<=m;i++){ int posy=lower_bound(vy.begin(),vy.end(),point[i].y)-vy.begin()+1; inserts(1,sz,root[i-1],root[i],posy,point[i].w); } while(p--){ int lx,rx,ly,ry; scanf("%d%d%d%d",&lx,&ly,&rx,&ry); lx=lower_bound(vx.begin(),vx.end(),lx)-vx.begin()+1; rx=upper_bound(vx.begin(),vx.end(),rx)-vx.begin(); ly=lower_bound(vy.begin(),vy.end(),ly)-vy.begin()+1; ry=upper_bound(vy.begin(),vy.end(),ry)-vy.begin(); if (lx>rx || ly>ry){ printf("0 "); continue; } printf("%lld ",query(root[lx-1],root[rx],1,sz,ly,ry)); } } return 0; } /* */