专栏首页算法修养HDU 5618 Jam's problem again(三维偏序,CDQ分治,树状数组,线段树)

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 条评论
登录 后参与评论

相关文章

  • LeetCode 1632. Rank Transform of a Matrix

    思路是贪心,将所有的元素从小到大排序。并且维护两个数组,一个数组代表每一行的当前已经填上的最大的rank,比如nrank[0]=2 表示第0行,目前已经填到了r...

    ShenduCC
  • LeetCode 13 Roman to Integer

    ShenduCC
  • LeetCode Contest 180

    ShenduCC
  • 第7章 套接字选项

    这一章是一个无比巨大的巨坑!!! 套接字选项相关函数: #include <sys/socket.h> int getsockopt(int sock, i...

    _gongluck
  • 指针详解(一)

    C语言可谓是因为指针而拥有了其他的语言所不拥有的作用,但是却又因为指针导致它对于初学者而言是一个很难克服的难题。接下来我们直切主体——指针。

    石的三次方
  • 一套帮助你理解C语言的测试题(转)

          原文链接:http://www.nowamagic.net/librarys/veda/detail/775

    xuyaowen
  • C语言实现计算器(指针+函数)

    输入两个整数a和b,及+,-,*,/中的任意一字符。根据输入字符对整数a和b做相应的算术运算,如输入+,程序就给出a与b之和,输入-,就给出a和b之差,输入*,...

    小Bob来啦
  • 一遍记住Java常用的八种排序算法

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    Java旅途
  • 学生时代所学的一些 C 语言知识点回顾(1)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    耕耘实录
  • ICPC Asia Shenyang 2019 Dudu's maze

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    用户2965768

扫码关注云+社区

领取腾讯云代金券