天使玩偶:CDQ分治&KD-tree

2024-03-08 15:04:16

这道好(du)题(liu)还是很不错的挺锻炼代码能力和不断优化卡常的能力的。

对于每次询问我都可以将其分出方向然后写也就是针对于4个方向左下左上右下右上

这样的话就成功转换了问题求4次三维偏序即可水题啊。

然后打完代码就提交 T飞了

//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<utility>
#include<queue>
#include<deque>
#include<vector>
#include<stack>
#include<algorithm>
#include<set>
#include<bitset>
#include<map>
#define INF 2147483646
#define ll long long
#define ldb long double
#define x(i) t[i].x
#define y(i) t[i].y
#define k(i) t[i].k
#define t(i) t[i].t
#define id(i) t[i].id
using namespace std;
char buf[1<<15],*ft,*fs;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void put(int x)
{
    x<0?x=-x,putchar('-'):0;
    int num=0;char ch[50];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar(10);return;
}
const int MAXN=300002,maxn=1000001;
int n,m,tot,num,cnt;
struct wy
{
    int x,y;
    int t,k;
    int id;
}t[MAXN<<1],tmp[MAXN<<1];
int ans[MAXN],c[maxn+10];//树状数组维护前缀最大值！
//注意时间戳也得排序 我的思维漏洞！
int cmp(wy x,wy y)//左下
{
    if(x.x==y.x&&x.y==x.y)return x.t<y.t;
    return x.x==y.x?x.y<y.y:x.x<y.x;
}
int cmp1(wy x,wy y)//左上
{
    if(x.x==y.x&&x.y==x.y)return x.t<y.t;
    return x.x==y.x?x.y>y.y:x.x<y.x;
}
int cmp2(wy x,wy y)//右下
{
    if(x.x==y.x&&x.y==x.y)return x.t<y.t;
    return x.x==y.x?x.y<y.y:x.x>y.x;
}
int cmp3(wy x,wy y)//右上
{
    if(x.x==y.x&&x.y==x.y)return x.t<y.t;
    return x.x==y.x?x.y>y.y:x.x>y.x;
}
inline int max(int x,int y){return x>y?x:y;}
void add(int x,int y)
{
    if(y==INF){for(;x<=maxn;x+=x&(-x))c[x]=-INF;return;}
    for(;x<=maxn;x+=x&(-x))c[x]=max(c[x],y);
    return;
}
inline int ask(int x)
{
    int sum=-INF;
    for(;x;x-=x&(-x))sum=max(sum,c[x]);
    return sum;
}
void CDQ(int l,int r,int p)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    CDQ(l,mid,p);
    CDQ(mid+1,r,p);
    int i=l,j=mid+1;
    if(p==0)
    {
        for(int k=l;k<=r;++k)
        {
            if(j>r||(i<=mid&&t(i)<=t(j)))
            {
                if(k(i)!=1)add(y(i),x(i)+y(i));
                tmp[k]=t[i];
                ++i;
            }
            else
            {
                if(k(j)==0){tmp[k]=t[j];++j;continue;}
                //if(id(j)==1)cout<<x(j)<<' '<<y(j)<<endl;
                int maxx=ask(y(j));
                if(maxx==-INF){tmp[k]=t[j];++j;continue;}
                ans[id(j)]=min(ans[id(j)],y(j)+x(j)-maxx);
                tmp[k]=t[j];
                ++j;
            }
        }
        for(int k=l;k<=r;k++)
        {
            if(k<=mid&&k(k)!=1)add(y(k),INF);
            t[k]=tmp[k];
        }
    }
    else
    {
        for(int k=l;k<=r;++k)
        {
            if(j>r||(i<=mid&&t(i)<=t(j)))
            {
                if(k(i)!=1)add(maxn-y(i),x(i)-y(i));
                tmp[k]=t[i];
                ++i;
            }
            else
            {
                if(k(j)==0){tmp[k]=t[j];++j;continue;}
                int maxx=ask(maxn-y(j));
                if(maxx==-INF){tmp[k]=t[j];++j;continue;}
                //cout<<maxx<<endl;
                ans[id(j)]=min(ans[id(j)],x(j)-y(j)-maxx);
                tmp[k]=t[j];
                ++j;
            }
        }
        for(int k=l;k<=r;k++)
            {
                if(k<=mid&&k(k)!=1)add(maxn-y(k),INF);
                t[k]=tmp[k];
            }
    }
    return;
}
void CDQ1(int l,int r,int p)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    CDQ1(l,mid,p);
    CDQ1(mid+1,r,p);
    int i=l,j=mid+1;
    if(p==0)
    {
        for(int k=l;k<=r;++k)
        {
            if(j>r||(i<=mid&&t(i)<=t(j)))
            {
                if(k(i)!=1)add(y(i),y(i)-x(i));
                tmp[k]=t[i];
                ++i;
            }
            else
            {
                if(k(j)==0){tmp[k]=t[j];++j;continue;}
                //if(id(j)==1)cout<<x(j)<<' '<<y(j)<<endl;
                int maxx=ask(y(j));
                if(maxx==-INF){tmp[k]=t[j];++j;continue;}
                ans[id(j)]=min(ans[id(j)],y(j)-x(j)-maxx);
                tmp[k]=t[j];
                ++j;
            }
        }
        for(int k=l;k<=r;k++)
        {
            if(k<=mid&&k(k)!=1)add(y(k),INF);
            t[k]=tmp[k];
        }
    }
    else
    {
        for(int k=l;k<=r;++k)
        {
            if(j>r||(i<=mid&&t(i)<=t(j)))
            {
                if(k(i)!=1)add(maxn-y(i),-x(i)-y(i));//此处不要想当然的写
                tmp[k]=t[i];
                ++i;
            }
            else
            {
                if(k(j)==0){tmp[k]=t[j];++j;continue;}
                int maxx=ask(maxn-y(j));
                if(maxx==-INF){tmp[k]=t[j];++j;continue;}
                ans[id(j)]=min(ans[id(j)],-maxx-x(j)-y(j));//变形要正确啊！
                tmp[k]=t[j];
                ++j;
            }
        }
        for(int k=l;k<=r;k++)
            {
                if(k<=mid&&k(k)!=1)add(maxn-y(k),INF);
                t[k]=tmp[k];
            }
    }
    return;
}
int main()
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    memset(ans,10,sizeof(ans));
    n=read();m=read();num=n;
    for(int i=1;i<=n;i++)x(i)=read(),y(i)=read();
    for(int i=1;i<=m;i++)
    {
        int p=read();
        x(++num)=read();y(num)=read();
        if(p==2)k(num)=1,id(num)=++cnt;
        t(num)=++tot;
    }
    //for(int i=1;i<=num;i++)cout<<x(i)<<' '<<y(i)<<' '<<t(i)<<' '<<k(i)<<endl;
    for(int i=1;i<=maxn;i++)c[i]=-INF;
    sort(t+1,t+1+num,cmp);//左下
    CDQ(1,num,0);//左下 
    //for(int i=1;i<=cnt;i++)cout<<ans[i]<<endl;
    for(int i=1;i<=maxn;i++)c[i]=-INF;
    sort(t+1,t+1+num,cmp1);//左上
    CDQ(1,num,1);//左上 
    //for(int i=1;i<=cnt;i++)cout<<ans[i]<<endl;
    for(int i=1;i<=maxn;i++)c[i]=-INF;
    sort(t+1,t+1+num,cmp2);//右下
    CDQ1(1,num,0);//右下 
    //for(int i=1;i<=cnt;i++)cout<<ans[i]<<endl;
    for(int i=1;i<=maxn;i++)c[i]=-INF;
    sort(t+1,t+1+num,cmp3);//右上
    CDQ1(1,num,1);//右上
    //for(int i=1;i<=cnt;i++)cout<<ans[i]<<endl;
    for(int i=1;i<=cnt;i++)put(ans[i]);
    return 0;
}

View Code

都别管我我要写4次CDQ 我要sort 4次然后不出意料只拿到50分。

原因是sort的次数多了常数是别人的近乎4倍（有的人一次sort都不做按照时间直接排）

然后脑残的写了这么段代码一直T 照着书上的标程改了一下是一种比较简洁的做法。

但是其CDQ的每层都需要sort 一下比较浪费时间但是还是能拿到60分的开O2 能A呢。

然后学了一下书上的做法发现真心简单代码复杂度时间复杂度空间复杂度包括常数都远远低于我

// luogu-judger-enable-o2
//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<utility>
#include<queue>
#include<deque>
#include<vector>
#include<stack>
#include<algorithm>
#include<set>
#include<bitset>
#include<map>
#define INF 2147483646
#define ll long long
#define ldb long double
#define x(i) t[i].x
#define y(i) t[i].y
#define t(i) t[i].t
#define id(i) t[i].id
using namespace std;
char buf[1<<15],*ft,*fs;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void put(int x)
{
    x<0?x=-x,putchar('-'):0;
    int num=0;char ch[50];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar(10);return;
}
const int MAXN=600002,maxn=1000010;
int n,m,cnt,num,tot,h;
int ans[MAXN],c[maxn],maxx;
struct wy
{
    int x,y;
    int t;
    int id;
    friend int operator <(const wy &a,const wy &b)
    {
        return a.x==b.x?a.y<b.y:a.x<b.x;//此时排序不用时间戳(经过实验
        //考虑一次CDQ 分治 时间复杂度 ≈(n+m)*log(n+m)^3左右
    }
}t[MAXN],tmp[MAXN];
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
inline void add(int x,int y){for(;x<=maxx;x+=x&(-x))c[x]=max(c[x],y);}
inline int abs(int x){return x<0?-x:x;}
inline int ask(int x)
{
    int maxx1=-INF;
    for(;x;x-=x&(-x))maxx1=max(maxx1,c[x]);
    return maxx1;
}
inline void remove1(int x)
{
    for(;x<=maxx;x+=x&(-x))c[x]=-INF;
    return;
}
void calculate(int st,int en,int w,int kx,int ky)//属性
{
    for(int i=st;i!=en;i+=w)
    {
        int yy=(ky==1?tmp[i].y:maxx-tmp[i].y);
        int sum=kx*tmp[i].x+ky*tmp[i].y;
        if(tmp[i].t==1)add(yy,sum);
        else 
        {
            int an=ask(yy);
            if(an==-INF)continue;
            ans[tmp[i].id]=min(ans[tmp[i].id],sum-an);
        }
        //if(tmp[i].id==2)cout<<sum<<' '<<ask(yy)<<endl;
    }
    for(int i=st;i!=en;i+=w)if(tmp[i].t==1)remove1(ky==1?tmp[i].y:maxx-tmp[i].y);
}
void CDQ(int l,int r)
{
    int mid=(l+r)>>1;
    if(l<mid)CDQ(l,mid);
    if(mid+1<r)CDQ(mid+1,r);
    h=0;
    for(int i=l;i<=r;i++)if((i<=mid&&t[i].t==1)||(i>mid&&t[i].t==2))tmp[++h]=t[i];
    sort(tmp+1,tmp+1+h);
    calculate(1,h+1,1,1,1);//左下
    calculate(1,h+1,1,1,-1);//左上
    calculate(h,0,-1,-1,1);//右下
    calculate(h,0,-1,-1,-1);//右上
}
int main()
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    n=read();m=read();num=n;
    for(int i=1;i<=n;++i)
    {
        x(i)=read();
        y(i)=read();
        t(i)=1;
        maxx=max(maxx,y(i));
    }
    for(int i=1;i<=m;++i)
    {
        t(++num)=read();
        x(num)=read();
        y(num)=read();
        id(num)=t(num)==2?++cnt:0;
        maxx=max(maxx,y(num));
    }
    //put(cnt);
    ++maxx;//巧妙一招
    for(int i=1;i<=maxx;++i)c[i]=-INF;
    memset(ans,10,sizeof(ans));
    CDQ(1,num);
    for(int i=1;i<=cnt;i++)put(ans[i]);
    return 0;
}

View Code

比较难受因为这浪费了我很多的时间然后最后还是T 开了O2 死T一个点（原因是我是个NC啊。。。

开O2 过了不算什么我要不开O2 过

点开题解发现我的第一个代码的思想及其接近其题解中跑的最快的。

所以发现可以不用sort 于是顺利不开O2 第一个代码顺利得到80分。

发现可以加一个优化是能不加到树状数组里就不加到需要的时候再加还有一些卡常的东西

最终不开O2 直接A （一直T的那个点是因为下标为0 树状数组原地GG了。。。）

//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<utility>
#include<queue>
#include<deque>
#include<vector>
#include<stack>
#include<algorithm>
#include<set>
#include<bitset>
#include<map>
#define INF 2147483646
#define ll long long
#define ldb long double
#define x(i) t[i].x
#define y(i) t[i].y
#define k(i) t[i].k
#define t(i) t[i].t
#define id(i) t[i].id
#define R register
using namespace std;
//char buf[1<<15],*ft,*fs;
//inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void put(int x)
{
    x<0?x=-x,putchar('-'):0;
    int num=0;char ch[50];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar(10);return;
}
const int maxn=1000010;
int n,m,tot,num,cnt,maxx1,maxx2;
struct wy
{
    int x,y;
    int k,id;
    inline bool operator <(const wy &w)const
    {
        return x<w.x;
    }
}t[maxn],tmp[maxn],a[maxn];
int ans[maxn],c[maxn+10];
inline int max(int x,int y){return x>y?x:y;}
inline void add(int x,int y)
{
    
    for(;x<=maxx1;x+=x&(-x))
    {
        if(c[x]>y)break;
        else c[x]=y;
    }
    return;
}
inline void remove1(int x)
{
    for(;x<=maxx1;x+=x&(-x))if(c[x])c[x]=0;
    return;
}
inline int ask(int x)
{
    int sum=-INF;
    for(;x;x-=x&(-x))sum=max(sum,c[x]);
    return sum;
}
inline void CDQ(int l,int r)
{
    int mid=(l+r)>>1;
    if(l<mid)CDQ(l,mid);
    if(r>mid+1)CDQ(mid+1,r);
    R int i=l,j=mid+1;
    for(j=mid+1;j<=r;j++)
    {
        if(k(j)==1)
        {    
            for(;i<=mid&&x(i)<=x(j);i++)
                if(k(i)==0)add(y(i),x(i)+y(i));
            int maxx=ask(y(j));
            maxx==0?0:ans[id(j)]=min(ans[id(j)],y(j)+x(j)-maxx);
            
        }
    }
    for(j=l;j<i;j++)if(k(j)==0)remove1(y(j));
    i=l,j=mid+1;
    for(R int k=l;k<=r;++k)
    {
        if(j>r||(i<=mid&&t[i]<t[j]))tmp[k]=t[i],++i;
        else tmp[k]=t[j],++j;
    }
    for(R int k=l;k<=r;++k)t[k]=tmp[k];
    return;
}
int main()
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    n=read();m=read();num=n;
    for(R int i=1;i<=n;++i){x(i)=read()+1,y(i)=read()+1;maxx1=max(maxx1,y(i));maxx2=max(maxx2,x(i));}
    for(R int i=1;i<=m;++i)
    {
        int p=read();
        x(++num)=read()+1;y(num)=read()+1;
        if(p==2)k(num)=1,id(num)=++cnt;
        maxx1=max(maxx1,y(num));
        maxx2=max(maxx2,x(num));
    }
    ++maxx1;++maxx2;
    for(R int i=1;i<=cnt;++i)ans[i]=INF;
    for(R int i=1;i<=num;++i)a[i]=t[i];
    CDQ(1,num);//左下 
    for(R int i=1;i<=num;++i)t[i]=a[i],y(i)=maxx1-y(i);
    CDQ(1,num);//左上 
    for(R int i=1;i<=num;++i)t[i]=a[i],x(i)=maxx2-x(i);
    CDQ(1,num);//右下 
    for(R int i=1;i<=num;++i)t[i]=a[i],x(i)=maxx2-x(i),y(i)=maxx1-y(i);
    CDQ(1,num);//右上
    for(R int i=1;i<=cnt;++i)put(ans[i]);
    return 0;
}

View Code

当然为了能够完美的A掉这道题我决定去学一个更强的东西 KD-tree.

然后在抄了20min代码后觉定放弃尧神说没多大卵用。。。

所以这篇博文到此啦，关键是不断优化的思想少开O2

码农公寓

相关文章