BZOJ 1176&2683&4066

传送门 传送门 传送门

题目大意：单点加，矩阵查询。
直接上 kdtree 就好了，定期暴力重构。

1176 题代码：

#include<bits/stdc++.h>

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
template<typename T> T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))

namespace kd
{
    const int D=2,inf=1000000000;

    char dnow;

    struct point
    {
        int d[D],val;
        int operator[](int x){return d[x];}
    };

    inline bool operator<(point a,point b)
    {
        return a[dnow]<b[dnow];
    }

    inline int dis(point a,point b){int ret=0;for(int i=0;i<D;i++)ret+=abs(a[i]-b[i]);return ret;}

    struct kdnode
    {
        point p;
        int sum,l[D],r[D],lc,rc;
    };

    int ans,tm=2;
    point q1,q2,Q,*P;
    kdnode t[200010];

    inline void update(int k)
    {
        for(int i=0;i<D;i++)
        {
            if(t[k].lc)repl(t[k].l[i],t[t[k].lc].l[i]),repr(t[k].r[i],t[t[k].lc].r[i]);
            if(t[k].rc)repl(t[k].l[i],t[t[k].rc].l[i]),repr(t[k].r[i],t[t[k].rc].r[i]);
        }
        t[k].sum=t[k].p.val+t[t[k].lc].sum+t[t[k].rc].sum;
    }
    inline void init(int x)
    {
        for(int i=0;i<D;i++)t[x].l[i]=t[x].r[i]=t[x].p[i];t[x].sum=t[x].p.val;
    }
    int build(int l,int r,char now)
    {
        if(now==D)now=0;
        dnow=now;
        int mid=(l+r)>>1,x=tm++;
        std::nth_element(P+l,P+mid,P+r+1);
        t[x].p=P[mid];
        t[x].lc=t[x].rc=0;
        init(x);
        if(l<mid)t[x].lc=build(l,mid-1,now+1);
        if(r>mid)t[x].rc=build(mid+1,r,now+1);
        update(x);return x;
    }
    void insert(int k,char now)
    {
        if(now==D)now=0;
        if(Q[now]>=t[k].p[now])
        {
            if(t[k].rc)
                insert(t[k].rc,now+1);
            else
            {
                t[k].rc=tm++;t[t[k].rc].p=Q;
                init(t[k].rc);
            }
        }
        else
        {
            if(t[k].lc)
                insert(t[k].lc,now+1);
            else
            {
                t[k].lc=tm++;t[t[k].lc].p=Q;
                init(t[k].lc);
            }
        }
        update(k);
    }
    void query(int k,char now)
    {
        if(now==D)now=0;
        bool tag=1;
        for(int i=0;i<D;i++)
            if(q1.d[i]>t[k].l[i]||q2.d[i]<t[k].r[i])
                tag=0;
         if(tag){ans+=t[k].sum;return;}
        tag=1;
        for(int i=0;i<D;i++)
            if(q1.d[i]>t[k].p.d[i]||q2.d[i]<t[k].p.d[i])
                tag=0;
        if(tag)ans+=t[k].p.val;
        tag=1;
        for(int i=0;i<D;i++)
            if(now==i)
            {
                if(q1.d[i]>t[k].p.d[i]||q2.d[i]<t[k].l[i])tag=0;
            }
            else
            {
                if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].l[i])tag=0;
            }
        if(tag&&t[k].lc)query(t[k].lc,now+1);
        tag=1;
        for(int i=0;i<D;i++)
            if(now==i)
            {
                if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].p.d[i])tag=0;
            }
            else
            {
                if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].l[i])tag=0;
            }
        if(tag&&t[k].rc)query(t[k].rc,now+1);
    }
    inline void build(point *p,int n){P=p;build(0,n-1,0);}
    inline int query(point a,point b){ans=0;q1=a,q2=b;query(1,0);return ans;}
    inline void insert(point p){Q=p;insert(1,0);}
}

kd::point pp[200000];

int main()
{
    int cx,n=0,opt;
    kd::point a,b;
    scanf("%d%*d",&cx);
    while(1)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d%d",&pp[n].d[0],&pp[n].d[1],&pp[n].val);
            kd::insert(pp[n++]);
        }
        else if(opt==2)
        {
            scanf("%d%d%d%d",&a.d[0],&a.d[1],&b.d[0],&b.d[1]);
            printf("%d\n",kd::query(a,b)+cx*(a.d[1]-a.d[0]+1)*(b.d[1]-b.d[0]+1));
        }
        else return 0;
        if(n>0&&n%10000==0)kd::tm=1,kd::build(pp,n);
    }
}

过不了就适当调参

日期： 2016-12-11

标签： BZOJ kdtree

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/97/ 查看。