2019南京网络赛A(离散化 离线 树状数组)

The beautiful values of the palace

二维子矩阵和(坐标太大).

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
using namespace std;
const int N=1e6+5;
typedef long long ll;
struct matrix{
    ll TD(ll x,ll y,ll n){
        ll r=0;
        if(x<=y&&x+y<=n+1){
            r=x;return 4LL*(r-1)*n-4*(r-1)*(r-1)+1+y-r;
        }
        if(x<=y & x+y >= n+1) {   
            r = n- y + 1;
            return 4LL*(r-1)*n - 4*(r-1)*(r-1) + 1 + n-2*r + 1 + x - r;
        }
        if(x>=y & x+y >= n+1) {   
            r = n - x +1;
            return 4LL*(r-1)*n - 4*(r-1)*(r-1) + 1 + 3*n-6*r + 3 - y + r;
        }
        if(x>=y & x+y <= n+1) {   
            r = y;   
            return 4LL*(r-1)*n - 4*(r-1)*(r-1) + 1 + 4*n-8*r + 4  - x + r;
        }
    }
    void DT(int &i,int &j,int n){
        int t=i;
        i=n-j+1,j=n-t+1;
    }
}MIT;
int getnum(ll n){
    int ans=0;
    while(n)ans+=n%10,n/=10;
    return ans;
}
struct qin_peng{
    int id,x,y,val,flag;
    bool friend operator<(qin_peng a,qin_peng b){
        return a.x<b.x;
    }
}QR[N<<2],P[N];
ll ans[N]={0},sum[N]={0};
void up(int x,int val){for(int i=x;i<N;i+=i&(-i))sum[i]+=val;}
ll Q(int x){
    ll ans=0;
    for(int i=x;i;i&=i-1)ans+=sum[i];
    return ans;
}
int main(){
    int t;cin>>t;
    while(t--){
        me(sum,0);
        int n,m,q;
        sc("%d%d%d",&n,&m,&q);
        for(int i=1;i<=m;i++){
            int x,y;
            sc("%d%d",&x,&y);
            MIT.DT(x,y,n);
            swap(x,y);
            ll num=MIT.TD(x,y,n);
            int val=getnum(num);
            P[i]={i,x,y,val,0};
        }
        int cnt=0;
        for(int i=1;i<=q;i++){
            int x1,y1,x2,y2;
            sc("%d%d%d%d",&x2,&y2,&x1,&y1);
            MIT.DT(x2,y2,n);swap(x2,y2);
            MIT.DT(x1,y1,n);swap(x1,y1);
            QR[++cnt]={i,x2,y2,0,1};
            QR[++cnt]={i,x1-1,y2,0,-1};
            QR[++cnt]={i,x2,y1-1,0,-1};
            QR[++cnt]={i,x1-1,y1-1,0,1};
        }
        sort(P+1,P+1+m);sort(QR+1,QR+1+cnt);
        int ptr=1;
        for(int i=1;i<=cnt;i++){
            while(ptr<=m&&P[ptr].x<=QR[i].x){
                up(P[ptr].y,P[ptr].val);
                ++ptr;
            }
            ans[QR[i].id]+=1LL*QR[i].flag*Q(QR[i].y);
        }
        for(int i=1;i<=q;i++)printf("%lld\n",ans[i]),ans[i]=0;
    }    
}