我是靠谱客的博主 虚心烤鸡，最近开发中收集的这篇文章主要介绍HDU - 5517 Triple(三维偏序-二维树状数组/CDQ分治)二维树状数组CDQ分治，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
题目链接：点击查看
题目大意：给出 n 个二元对 ( a , b ) 和 m 个三元对 ( c , d , e )，对于所有 b == e 的二元对和三元对，可以通过某种运算形成一个新的三元对 ( a , c , d ) ，现在问所有的 ( a , c , d ) 中，有多少个三元对满足，不存在另一个三元对 ( a1 , c1 , d1 ) 满足 a1 >= a && c1 >= c && d1 >= d
题目分析：首先需要分析出来，对于所有的二元对 ( a , b ) 来说，对于每个 b ，我们只需要映射一下其最大的 a 即可，因为假设存在两个二元对 ( a1 , b ) 和 ( a2 , b ) 满足 a1 > a2，其能组成的所有三元对中，( a1 , c , d ) 和 ( a2 , c , d ) 一定满足 a1 >= a2 && c >= c && d >= d，故 a2 一定没有贡献，知道了这一点后，又因为 m 最大才为 1e5，所以最后可以做出贡献的三元对最多也只有 1e5 个，我们只需要对这些三元对进行讨论即可
将这些新的三元对储存起来后， 剩下的就是一个简单的三维偏序问题了，又因为 c 和 d 的范围都非常小，所以可以用二维树状数组来解决，时间复杂度为 nlog^2n，也可以用朴素的 CDQ分治 解决，时间复杂度同为 nlog^2n，不过显然前者的常数要小很多，表现的更加优秀
稍微讲一下二者该如何解决吧，二维树状数组应该比较好理解，说是树套树，其实就是在原有的一维数组和循环的基础上，多套了一层循环罢了，维护的是 ( 0 , 0 ) ~ ( x , y ) 这个二维矩阵中点的个数，这样一来就可以将三维偏序中的第二维和第三维抽象成二维矩阵上的点表示，在第一维降序排序的基础上，对于某个点 ( x , y ) ，如果 ( x , y ) ~ ( 1000 , 1000 ) 中存在点的话，那就说明肯定存在这一个三元组的每一项都分别大于当前的这一项，故不符合条件，反之符合条件
然后就是CDQ分治，这个没什么好说的了，按照第一维降序排序，第二维放在归并排序中仍然降序，第三维用树状数组维护，分别记录每个位置的贡献即可
最后就是特判一下无解的情况，以及对于所有相同位置的点，需要压缩成一个点，不然会相互影响
代码：
二维树状数组
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=1e5+100;
struct Node
{
int a,b,c,num;
Node(int a,int b,int c,int num):a(a),b(b),c(c),num(num){}
bool operator==(const Node& t)const
{
return a==t.a&&b==t.b&&c==t.c;
}
};
vector<Node>node1,node2;
int b[N],num[N],c[1100][1100];
int lowbit(int x)
{
return x&(-x);
}
int add(int x,int y)//(x,y)的位置加1
{
for(int i=x;i<=1000;i+=lowbit(i))
for(int j=y;j<=1000;j+=lowbit(j))
c[i][j]++;
}
int ask(int x,int y)//返回(0,0)~(x,y)的矩阵和
{
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
ans+=c[i][j];
return ans;
}
int query(int x,int y)//返回(x,y)~(1000,1000)的矩阵和
{
return ask(1000,1000)-ask(x-1,1000)-ask(1000,y-1)+ask(x-1,y-1);
}
void init()
{
node1.clear();
node2.clear();
memset(b,0,sizeof(b));
memset(num,0,sizeof(num));
memset(c,0,sizeof(c));
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);
int w;
cin>>w;
int kase=0;
while(w--)
{
init();
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(b[y]<x)
{
b[y]=x;
num[y]=1;
}
else if(b[y]==x)
num[y]++;
}
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(b[z])
node1.push_back(Node(b[z],x,y,num[z]));
}
if(node1.empty())
{
printf("Case #%d: 0n",++kase);
continue;
}
sort(node1.begin(),node1.end(),[&](Node a,Node b)
{
if(a.a!=b.a)
return a.a>b.a;
if(a.b!=b.b)
return a.b>b.b;
return a.c>b.c;
});
node2.push_back(node1[0]);
for(int i=1;i<node1.size();i++)
{
if(node2.back()==node1[i])
node2.back().num+=node1[i].num;
else
node2.push_back(node1[i]);
}
int ans=0;
for(int i=0;i<node2.size();i++)
{
if(!query(node2[i].b,node2[i].c))
ans+=node2[i].num;
add(node2[i].b,node2[i].c);
}
printf("Case #%d: %dn",++kase,ans);
}
return 0;
}CDQ分治
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=1e5+100;
struct Node
{
int a,b,c,num,id;
Node():a(0),b(0),c(0){}
Node(int a,int b,int c,int num):a(a),b(b),c(c),num(num){}
bool operator==(const Node& t)const
{
return a==t.a&&b==t.b&&c==t.c;
}
}t[N];
vector<Node>node1,node2;
int b[N],num[N],c[1100],vis[N];
int lowbit(int x)
{
return x&(-x);
}
int add(int x,int val)
{
for(int i=x;i<=1000;i+=lowbit(i))
c[i]+=val;
}
int ask(int x)
{
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
ans+=c[i];
return ans;
}
bool cmp(Node a,Node b)
{
if(a.b!=b.b)
return a.b>b.b;
return a.c>b.c;
}
void CDQ(int l,int r)
{
if(l==r)
return;
int mid=l+r>>1;
CDQ(l,mid);
CDQ(mid+1,r);
for(int i=l;i<=r;i++)
t[i]=node2[i];
sort(t+l,t+mid+1,cmp);
sort(t+mid+1,t+r+1,cmp);
int p=l,q=mid+1;
while(p<=mid&&q<=r)
{
if(t[p].b>=t[q].b)
{
add(t[p].c,1);
p++;
}
else
{
vis[t[q].id]+=ask(1000)-ask(t[q].c-1);
q++;
}
}
while(p<=mid)
{
add(t[p].c,1);
p++;
}
while(q<=r)
{
vis[t[q].id]+=ask(1000)-ask(t[q].c-1);
q++;
}
for(int i=l;i<=mid;i++)
add(t[i].c,-1);
}
void init()
{
node1.clear();
node2.clear();
memset(b,0,sizeof(b));
memset(num,0,sizeof(num));
memset(c,0,sizeof(c));
memset(vis,0,sizeof(vis));
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);
int w;
cin>>w;
int kase=0;
while(w--)
{
init();
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(b[y]<x)
{
b[y]=x;
num[y]=1;
}
else if(b[y]==x)
num[y]++;
}
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(b[z])
node1.push_back(Node(b[z],x,y,num[z]));
}
if(node1.empty())
{
printf("Case #%d: 0n",++kase);
continue;
}
sort(node1.begin(),node1.end(),[&](Node a,Node b)
{
if(a.a!=b.a)
return a.a>b.a;
if(a.b!=b.b)
return a.b>b.b;
return a.c>b.c;
});
node2.push_back(Node());
for(int i=0;i<node1.size();i++)
{
if(node2.back()==node1[i])
node2.back().num+=node1[i].num;
else
{
node2.push_back(node1[i]);
node2.back().id=node2.size()-1;
}
}
int nn=node2.size()-1;
CDQ(1,nn);
int ans=0;
for(int i=1;i<=nn;i++)
if(!vis[node2[i].id])
ans+=node2[i].num;
printf("Case #%d: %dn",++kase,ans);
}
return 0;
}
最后
以上就是虚心烤鸡为你收集整理的HDU - 5517 Triple(三维偏序-二维树状数组/CDQ分治)二维树状数组CDQ分治的全部内容，希望文章能够帮你解决HDU - 5517 Triple(三维偏序-二维树状数组/CDQ分治)二维树状数组CDQ分治所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![三元逆序对 求i<j<k && a[i]>a[j]>a[k] 的对数 树状数组Codeforces 61E Enemy is weak](/uploads/reation/bcimg1.png)
发表评论 取消回复