A.The beautiful values of the palace 掃描線+思維題

A.The beautiful values of the palace

題解：一個螺旋矩陣，我們要O(1)處理處每個位置數的值，是以必然要找規律，O(1)求每個值。規律就是首先判斷點在哪一層螺旋，然後再根據等差求和，因為每一層的數的個數都是有規律的，然後再判斷在哪一條邊上，然後就能O(1)求。然後我按照x從小到大，按照y從小到大，按照先修改再查詢的順序，但是要注意這裡需要二維求字首和的知識，我們查詢兩個點（x1,y1），（x2,y2）要拆分為四個點（x1-1,y1-1），（x2,y2），（x1-1,y2），（x2,y1-1）然後按照求二維字首和的方法求。我用x來映射y，這就是掃描線。

#include<bits/stdc++.h>
#define ll long long
#define mid (l+r)/2
#define ls o*2
#define rs o*2+1
using namespace std;
const int maxn = 1e6+10;
ll n;
ll ans[maxn],tr[maxn*4];
ll cul(int x,int y)
{
    ll ans ;
    int tx = x;
    tx = min((tx-1)*1LL,n-tx*1LL);
    tx = min(tx,y-1);
    tx = min(tx*1LL,n-y*1LL);
    ans = 4LL*tx*n - 4LL*tx*tx;
    if(n-x==tx) ans += n-y+1-tx;
    else if(y-tx==1) ans += n-tx*2LL + n-x*1LL - tx*1LL  ;
    else if(x-tx==1) ans += 2LL*(n-tx*2LL) - 1LL + y*1LL - tx*1LL - 1LL;
    else ans += 3LL*(n-tx*2LL) - 2LL + x*1LL - tx*1LL - 1LL;
    return ans ;
}
int qu_bit(ll ans)
{
    int res = 0;
    while(ans)
    {
     res += ans%10;
     ans /= 10LL;
    }
    return res;
}
struct node{
   int x,y;
   ll ans;
}p[maxn];
struct point{
   int x,y,id,flag;
}tx[maxn];
bool cmp(point a,point b)
{
    if(a.x==b.x&&a.y==b.y) return a.flag>b.flag;
    else if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
void up(int o,int l,int r,int k,ll v)
{
    if(l==r)
    {
        tr[o] += v;
        return ;
    }
    if(k>mid) up(rs,mid+1,r,k,v);
    else up(ls,l,mid,k,v);
    tr[o] = tr[ls] + tr[rs];
}
ll qu(int o,int l,int r,int ql,int qr)
{
    if(ql>qr) return 0;
    if(ql<=l&&qr>=r)  return tr[o];
    ll ans = 0;
    if(ql<=mid) ans += qu(ls,l,mid,ql,qr);
    if(qr>mid) ans += qu(rs,mid+1,r,ql,qr);
    return ans ;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        int m,q,x,y,res;
        scanf("%lld%d%d",&n,&m,&q);
        int c = 0;
        for(int i=1;i<=m;i++)
        {
           scanf("%d%d",&p[i].x,&p[i].y);
           ll tmp = cul(p[i].x,p[i].y);
           p[i].ans = qu_bit(tmp);
            ++c;
           tx[c].x = p[i].x;
           tx[c].y = p[i].y;
           tx[c].id = q+i;
           tx[c].flag = 2;
        }
        int x1,y1,x2,y2;
        for(int i=1;i<=q;i++)
        {
          scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        ++c; tx[c].x = x1-1, tx[c].y = y1-1, tx[c].flag = 1,tx[c].id=i; 
        ++c;  tx[c].x = x1-1, tx[c].y = y2, tx[c].flag = -1,tx[c].id=i; 
        ++c;  tx[c].x = x2, tx[c].y = y1-1, tx[c].flag = -1,tx[c].id=i; 
        ++c;  tx[c].x = x2, tx[c].y = y2, tx[c].flag = 1, tx[c].id=i; 
       }
       sort(tx+1,tx+1+c,cmp);
       for(int i=1;i<=q;i++) ans[i] = 0;
       for(int i=1;i<=c;i++)
       {
           if(tx[i].flag==2)
           {
              int now = tx[i].id - q;
              up(1,1,n,tx[i].y,p[now].ans);
           }
           else {
             ans[tx[i].id] += tx[i].flag*qu(1,1,n,1,tx[i].y);
           }
       }
       for(int i=1;i<=q;i++)
       printf("%lld\n",ans[i]);
       for(int i=0;i<maxn*4;i++)
       tr[i] = 0;
    }
}