題目鏈接：點(diǎn)擊查看

題目大意：給出 n 個(gè)二元對(duì) ( a , b ) 和 m 個(gè)三元對(duì) ( c , d , e )，對(duì)于所有 b == e 的二元對(duì)和三元對(duì)，可以通過(guò)某種運(yùn)算形成一個(gè)新的三元對(duì) ( a , c , d ) ，現(xiàn)在問(wèn)所有的 ( a , c , d ) 中，有多少個(gè)三元對(duì)滿足，不存在另一個(gè)三元對(duì) ( a1 , c1 , d1 ) 滿足 a1 >= a && c1 >= c && d1 >= d

題目分析：首先需要分析出來(lái)，對(duì)于所有的二元對(duì) ( a , b ) 來(lái)說(shuō)，對(duì)于每個(gè) b ，我們只需要映射一下其最大的 a 即可，因?yàn)榧僭O(shè)存在兩個(gè)二元對(duì) ( a1 , b ) 和 ( a2 , b ) 滿足 a1 > a2，其能組成的所有三元對(duì)中，( a1 , c , d ) 和 ( a2 , c , d ) 一定滿足 a1 >= a2 && c >= c && d >= d，故 a2 一定沒(méi)有貢獻(xiàn)，知道了這一點(diǎn)后，又因?yàn)?m 最大才為 1e5，所以最后可以做出貢獻(xiàn)的三元對(duì)最多也只有 1e5 個(gè)，我們只需要對(duì)這些三元對(duì)進(jìn)行討論即可

將這些新的三元對(duì)儲(chǔ)存起來(lái)后， 剩下的就是一個(gè)簡(jiǎn)單的三維偏序問(wèn)題了，又因?yàn)?c 和 d 的范圍都非常小，所以可以用二維樹狀數(shù)組來(lái)解決，時(shí)間復(fù)雜度為 nlog^2n，也可以用樸素的 CDQ分治 解決，時(shí)間復(fù)雜度同為 nlog^2n，不過(guò)顯然前者的常數(shù)要小很多，表現(xiàn)的更加優(yōu)秀

稍微講一下二者該如何解決吧，二維樹狀數(shù)組應(yīng)該比較好理解，說(shuō)是樹套樹，其實(shí)就是在原有的一維數(shù)組和循環(huán)的基礎(chǔ)上，多套了一層循環(huán)罷了，維護(hù)的是 ( 0 , 0 ) ~ ( x , y?) 這個(gè)二維矩陣中點(diǎn)的個(gè)數(shù)，這樣一來(lái)就可以將三維偏序中的第二維和第三維抽象成二維矩陣上的點(diǎn)表示，在第一維降序排序的基礎(chǔ)上，對(duì)于某個(gè)點(diǎn) ( x , y ) ，如果 ( x , y ) ~ ( 1000 , 1000 ) 中存在點(diǎn)的話，那就說(shuō)明肯定存在這一個(gè)三元組的每一項(xiàng)都分別大于當(dāng)前的這一項(xiàng)，故不符合條件，反之符合條件

然后就是CDQ分治，這個(gè)沒(méi)什么好說(shuō)的了，按照第一維降序排序，第二維放在歸并排序中仍然降序，第三維用樹狀數(shù)組維護(hù)，分別記錄每個(gè)位置的貢獻(xiàn)即可

最后就是特判一下無(wú)解的情況，以及對(duì)于所有相同位置的點(diǎn)，需要壓縮成一個(gè)點(diǎn)，不然會(huì)相互影響

代碼：

二維樹狀數(shù)組

#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: 0\n",++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;elsenode2.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: %d\n",++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: 0\n",++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: %d\n",++kase,ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 5517 Triple(三维偏序-二维树状数组/CDQ分治)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。