2019 南京网络赛A

南京网络赛自闭现场

https://nanti.jisuanke.com/t/41298

二维偏序经典题型

二维前缀和！！！

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define sc(x) scanf("%lld",&x);

int T;

#define P pair<int,int>

#define fi first

#define se second

#define maxn 1000000+10

int n,m,p;

int A[maxn];

int B[maxn];

int C[maxn];

int D[maxn];

int Ans[maxn];

map<int,int> mp;

struct Q{

int x,y,z,w;

}q[maxn];

P E[maxn];

int f(int x)

{

    int ans=;

    while(x)

    {

        ans+=(x%);

        x/=;

    }

    return ans;

}

int cal(int x,int y)

{

    int s=n*n;

    int _t=(n+)/;

    if(x==_t&&y==_t){

        //return s;

        return f(n*n);

    }

    int _a=max(abs(x-_t),abs(y-_t));///距中心点距离

    int _x=(_a*+);

    int sx=_t-_a;

    int sy=_t-_a;

    int ck=_a+_t-;///出口

   // cout<<endl<<x<<" "<<y<<" "<<ck<<" ck "<<_a<<" "<<_t<<endl;

    s-=(_x-)*(_x-);///减去内圈

    if(y-_t==_a&&x<=ck) ///顶行

    {

        s-=(ck-x);

        //cout<<endl<<"F"<<x<<' '<<y<<' '<<s<<' '<<f(s)<<endl;

        return f(s);

    }

    else

    {

        s-=(_x-);

        //cout<<s<<" "<<_x<<" "<<y<<endl;

        if(_t-x==_a)

        {

            s-=_x+sx-y-;

          //  cout<<s<<endl;

            return f(s);

        }

        else

        {

            s-=_x-;

            if(_t-y==_a)

            {

                s-=x-sx-;

                  return f(s);

            }

            else

            {

                s-=_x-;

                if(x-_t==_a)

                {

                    s-=y-sy-;

                       return f(s);

                }

            }

        }

    }

}

int V[maxn];

void add(int x,int val)

{

    while(x<=maxn){

        V[x]+=val;

        x+=(x&-x);

    }

}

int get(int x)

{

   // if(x==0)return 0;

    int ans=;

    //ans+=V[0];

    while(x){

        ans+=V[x];

        x-=(x&-x);

    }

    return ans;

}

bool cmp(int x,int y)

{

    if(A[x]==A[y])return B[x]<B[y];

    return A[x]<A[y];

}

void init()

{

    for(int i=;i<maxn;i++){

        Ans[i]=V[i]=;

        mp.clear();

    }

}

signed main()

{

    sc(T);

     while(T--)

     {

         init();

         sc(n);

         sc(m);

         sc(p);

         int a,b,c,d;

         for(int i=; i<=m; i++)

         {

             sc(A[i]);

             sc(B[i]);

             C[i]=i;

             D[i]=cal(A[i],B[i]);

             mp[D[i]]=;

         }

         sort(C+,C+m+,cmp);

         int _k=;

         for(int i=;i<p;i++){

             sc(a);sc(b);sc(c);sc(d);

             q[i].x=a;

             q[i].y=b;

             q[i].z=c;

             q[i].w=d;

             E[_k++]=P(a-,b-);

             E[_k++]=P(a-,d);

             E[_k++]=P(c,b-);

             E[_k++]=P(c,d);

         }

         sort(E,E+_k);

         int sz=unique(E,E+_k)-E;

         int j=;

         for(int i=;i<sz;){

            //cout<<i<<sz<<'\n';

            while(j<=m&&E[i].fi>=A[C[j]]){

                add(B[C[j]],D[C[j]]);

                j++;

            }

            Ans[i]=get(E[i].se);

           // Ans1[i]=get(E[i].se-1);

            i++;

         }

         for(int i=;i<p;i++){

            P x=P(q[i].x-,q[i].y-);

            P y=P(q[i].z,q[i].w);

            P w=P(q[i].x-,q[i].w);

            P z=P(q[i].z,q[i].y-);

            int an=Ans[lower_bound( E,E+sz,x)-E];

             //cout<<x.fi<<' '<<an<<'\n';

            an-=Ans[lower_bound( E,E+sz,w)-E];

            an-=Ans[lower_bound( E,E+sz,z)-E];

            cout<<Ans[lower_bound(E,E+sz,y)-E]+an<<'\n';

           //  cout<<Ans[lower_bound(E,E+sz,y)-E]<<'\n';

         }

     }

}