HDU 5618 Jam's problem again(三维偏序,CDQ分治,树状数组,线段树)

Jam's problem again

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 640    Accepted Submission(s): 210

Problem Description

Jam like to solve the problem which on the 3D-axis,given  points  If two point such as  and , the bigger one level add  Ask for the each level of the point.

Input

The first line is  means  Case For each case The first line is  means the number of Point and next there are  line, each line has 

Output

Output with N line,each line has one number means the lever of point

Sample Input

1
4
10 4 7
10 6 6
8 2 5
7 3 10

Sample Output

1
1
0
0
三维偏序,即要求一个三维的点比这个点的小的点有多少个。如果是一维的我们可以怎么做呢?很简单排个序就可以了。如果是二维的呢,同时要求x1<x2和y1<y2点(x1,y1)比点(x2,y2)小。我们可以想到二维树状数组可以很高效率的解决这个问题,但是数据要是有10万,就开不来二维树状数组了。那么可以降维来做。一维排序,二维用树状数组或者线段树来解决,也可以用CDQ分治来做。例如用树状数组,那么按照x排序之后,在树状数组里插入y,边插入边询问,就可以n*logn的效率得到答案。三维的情况呢,同理,第三维可以继续用树状数组或者线段树,但是用树状数组就相当于一个二维树状数组显然会超内存。所以我们可以用动态线段树,不会超内存。如果了用了CDQ分治,那么可以这样一维排序,二维CDQ分治,三维树状数组也可以一维排序,二维CDQ分治,三维CDQ分治
一维排序,二维树状数组,三维线段树#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
typedef long long int LL;
const int maxn=1e5;
struct Node
{
    int x,y,z;
    int id;
    int num;
}a[maxn+5];
int n;
int rt[maxn+5];
int ls[maxn*50];
int rs[maxn*50];
int sum[maxn*50];
int p;
int ans1,ans2;
int newnode()
{
    ls[p]=rs[p]=sum[p]=0;
    return p++;
}
int lowbit(int x)
{
    return x&(-x);
}
int cmp(Node a,Node b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    else
    {
        if(a.y!=b.y)
            return a.y<b.y;
        else
            return a.z<b.z;
    }
}
int cmp2(Node a,Node b)
{
    return a.id<b.id;
}
void insert(int &node,int l,int r,int tag)
{
    if(!node)
        node=newnode();
    if(l==r)
    {
        sum[node]++;
        return;
    }
    sum[node]++;
    int mid=(l+r)>>1;
    if(tag<=mid)
        insert(ls[node],l,mid,tag);
    else
        insert(rs[node],mid+1,r,tag);
}
int query(int &node,int l,int r,int tag)
{
    if(!node) return 0;
    if(r<=tag)
    {
        return sum[node];
    }
    int mid=(l+r)>>1;
    if(tag<=mid) return query(ls[node],l,mid,tag);
    else return sum[ls[node]]+query(rs[node],mid+1,r,tag);
}
int find(int y,int z)
{
    int res=0;
    for(int i=y;i>=1;i-=lowbit(i))
    {
        res+=query(rt[i],1,ans2,z);
    }
    return res;
}
void update(int y,int z)
{
    for(int i=y;i<=maxn;i+=lowbit(i))
    {
        insert(rt[i],1,ans2,z);
    }
}
void init(int y,int z)
{
    memset(rt,0,sizeof(rt));
    for(int i=1;i<=y;i++)
    {
        rt[i]=i;
        ls[i]=rs[i]=sum[i]=0;
    }
    p=y+1;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
         ans1=0;  ans2=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
            ans1=max(ans1,a[i].y);
            ans2=max(ans2,a[i].z);
            a[i].id=i;a[i].num=0;
        }
         sort(a+1,a+n+1,cmp);
        for(int i=n-1;i>=1;i--)
        {
            if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z)
                a[i].num=a[i+1].num+1;
        }

        init(ans1,ans2);
        for(int i=1;i<=n;i++)
        {
            a[i].num+=find(a[i].y,a[i].z);
            update(a[i].y,a[i].z);

        }
        sort(a+1,a+n+1,cmp2);
        for(int i=1;i<=n;i++)
        {
            printf("%d\n",a[i].num);
        }
    }
    return 0;
}
一维排序,二维CDQ分治,三维树状数组include <iostream>
 #include <stdlib.h>
 #include <math.h>
 #include <algorithm>
 #include <stdio.h>
 #include <string.h>

 using namespace std;
 typedef long long int LL;
 const int maxn=1e5;
 int n;
 struct Node
 {
     int x,y,z;
     int id;
     int num;
 }a[maxn+5],b[maxn+5];
 int c[maxn+5];
 int cmp(Node a,Node b)
 {
     if(a.x==b.x&&a.y==b.y)
        return a.z<b.z;
     if(a.x==b.x)
        return a.y<b.y;
     return a.x<=b.x;
 }
 int cmp2(Node a,Node b)
 {
     return a.id<b.id;
 }
 int lowbit(int x)
 {
     return x&(-x);
 }
 void insert(int x,int y)
 {
     for(int i=x;i<=maxn;i+=lowbit(i))
        c[i]+=y;
 }
 int sum(int x)
 {
     int s=0;
     for(int i=x;i>=1;i-=lowbit(i))
        s+=c[i];
     return s;
 }
 void fun(int l,int r)
 {
     if(l==r) return;
     int mid=(l+r)>>1;
     int j=l;
     int k=mid+1;
     fun(l,mid);
     fun(mid+1,r);
     for(int i=l;i<=r;i++)
     {
         if((a[j].y<=a[k].y||k>r)&&j<=mid)
         {
             b[i]=a[j++];
             insert(b[i].z,1);
         }
         else
         {
             b[i]=a[k++];
             b[i].num+=sum(b[i].z);
         }
     }
     for(int i=l;i<=r;i++)
     {
         if(i<=mid)
            insert(a[i].z,-1);
         a[i]=b[i];
     }
 }
 int main()
 {
     int t;
     scanf("%d",&t);
     while(t--)
     {
         memset(c,0,sizeof(c));
         scanf("%d",&n);
         for(int i=1;i<=n;i++)
         {
             scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
             a[i].id=i;a[i].num=0;
         }
         sort(a+1,a+n+1,cmp);
         for(int i=n-1;i>=1;i--)
         {
             if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z)
                a[i].num=a[i+1].num+1;
         }
         fun(1,n);
         sort(a+1,a+n+1,cmp2);
         for(int i=1;i<=n;i++)
         {
             printf("%d\n",a[i].num);
         }
     }
     return 0;
 }
一维排序,二维CDQ分治,三维CDQ分治#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
typedef long long int LL;
const int maxn=1e5;
struct Node
{
    int x,y,z;
    int id,num;
    int tag;
  
}a[maxn+5],b[maxn+5],c[maxn+5];
int ans[maxn+5];
int n;

int cmp(Node a,Node b)
{
    if(a.x==b.x&&a.y==b.y)
        return a.z<b.z;
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
int cmp2(Node a,Node b)
{
    return a.id<b.id;
}
void fun2(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    fun2(l,mid);
    fun2(mid+1,r);
    int j=l;
    int k=mid+1;
    int res=0;
    for(int i=l;i<=r;i++)
    {
        if((b[j].z<=b[k].z||k>r)&&j<=mid)
        {
            c[i]=b[j++];
            if(!c[i].tag)
                res++;
        }
        else
        {
            c[i]=b[k++];
            if(c[i].tag)
                c[i].num+=res,ans[c[i].id]+=res;
        }
    }
    for(int i=l;i<=r;i++)
        b[i]=c[i];
}
void fun1(int l,int r)
{

    if(l==r)
        return;
    int mid=(l+r)>>1;
    fun1(l,mid);
    fun1(mid+1,r);
    int j=l;
    int k=mid+1;
    for(int i=l;i<=r;i++)
    {
        if((a[j].y<=a[k].y||k>r)&&j<=mid)
        {
             b[i]=a[j++];
             b[i].tag=0;
        }
        else
        {
             b[i]=a[k++];
             b[i].tag=1;
        }
    }
    for(int i=l;i<=r;i++)
        a[i]=b[i];

    fun2(l,r);
    
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
            a[i].num=0;
            a[i].tag=0;
            a[i].id=i;
         
        }
        memset(ans,0,sizeof(ans));

        sort(a+1,a+n+1,cmp);
        for(int i=n-1;i>=1;i--)
            if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z)
                a[i].num=a[i+1].num+1,ans[a[i].id]=ans[a[i+1].id]+1;

        fun1(1,n);
        sort(a+1,a+n+1,cmp2);
        for(int i=1;i<=n;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

BZOJ 3097: Hash Killer I【构造题,思维题】

3097: Hash Killer I Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge Su...

21860
来自专栏算法修养

UVALive 6933 Virus synthesis(回文树)

Viruses are usually bad for your health. How about ghting them with... other vir...

36470
来自专栏ml

HDUOJ-----A == B ?

A == B ? Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

30760
来自专栏小樱的经验随笔

HDU 1000 A + B Problem(指针版)

A + B Problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

28340
来自专栏算法修养

HDU 2476 String painter(区间DP)

String painter Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/327...

35280
来自专栏ml

HDUOJ-------(1022)Train Problem I

Train Problem I Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

31770
来自专栏数据结构与算法

POJ 2891 Strange Way to Express Integers

Description Elina is reading a book written by Rujia Liu, which introduces a ...

34870
来自专栏HansBug's Lab

2292: 【POJ Challenge 】永远挑战

2292: 【POJ Challenge 】永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 553 ...

30860
来自专栏ml

hdu 4034 Graph (floyd的深入理解)

Graph Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Jav...

375110
来自专栏ml

HDUOJ----剪花布条

剪花布条 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

364120

扫码关注云+社区

领取腾讯云代金券