stable_sort 保平安。

解析

dp方程顯而易見，關鍵就是如何進行這個四維偏序的轉移。

考慮三維偏序（比如攔截導彈）我們是如何做的？
先按照第一維排序，然后分治解決前一半，接下來把前一半的第一維看成0，第二維看成1，按照第二維排序后，用所有的0對1進行轉移。

本題也延續(xù)這樣的思想，先按照第一維排序，前一半看成0，后一半看成1，然后再對其進行一次三維偏序的轉移，有所不同就是只有打上0標記的才可以加入樹狀數(shù)組，打上1標記的才可以接受轉移。

換句話說，就是只能讓0,0向1,1轉移。

注意排序一定要排徹底！
stable_sort 是好東西，在常數(shù)可以接受的情況下大大降低寫錯的風險。
其實主要出錯就是重點的時候，注意一下把cmp函數(shù)寫好也不會有問題。

代碼

（畢竟是模板，就貼的是不用 stable_sort 也能過的）

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") using namespace std;const int N=8e4+100; const int C=205; const int mod=998244353;inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } int n,m; #define pr pair<ll,ll> #define mkp make_pair pr f[N]; int q[N],cnt; void operator += (pr &a,pr b){if(a.first<b.first) a=b;else if(a.first==b.first) (a.second+=b.second)%=mod; } inline void add(int p,pr o){for(;p<=cnt;p+=p&-p) f[p]+=o;return; } inline pr ask(int p){pr res=mkp(0,1);for(;p;p-=p&-p) res+=f[p];return res; } inline void clear(int p){for(;p<=cnt;p+=p&-p) f[p]=mkp(0,1); } struct node{int x[5],v;pr dp;bool op; }p[N]; inline void print(node o,bool op=1){printf("[(%d %d %d %d) dp=(%lld %lld) v=%d op=%d] ",o.x[1],o.x[2],o.x[3],o.x[4],o.dp.first,o.dp.second,o.v,o.op);if(op) putchar('\n');return; } bool cmp1 (const node &a,const node &b){if(a.op!=b.op) return a.op>b.op;if(a.x[1]!=b.x[1]) return a.x[1]<b.x[1];else if(a.x[2]!=b.x[2]) return a.x[2]<b.x[2];else if(a.x[3]!=b.x[3]) return a.x[3]<b.x[3];else if(a.x[4]!=b.x[4]) return a.x[4]<b.x[4];else return a.dp<b.dp; } bool cmp2 (const node &a,const node &b){if(a.x[2]!=b.x[2]) return a.x[2]<b.x[2];else if(a.x[3]!=b.x[3]) return a.x[3]<b.x[3];else if(a.x[4]!=b.x[4]) return a.x[4]<b.x[4];else if(a.x[1]!=b.x[1]) return a.x[1]<b.x[1];else return a.op>b.op; } bool cmp3 (const node &a,const node &b){if(a.x[3]!=b.x[3]) return a.x[3]<b.x[3];else if(a.x[4]!=b.x[4]) return a.x[4]<b.x[4];else if(a.x[1]!=b.x[1]) return a.x[1]<b.x[1];else if(a.x[2]!=b.x[2]) return a.x[2]<b.x[2];else return a.dp<b.dp; }void solve2(int l,int r){if(l==r){//p[l].dp+=mkp(p[l].v,1);return;}int mid=(l+r)>>1;solve2(l,mid);sort(p+l,p+mid+1,cmp3);sort(p+mid+1,p+r+1,cmp3); int pl=l;for(int i=mid+1;i<=r;i++){while(pl<=mid&&p[pl].x[3]<=p[i].x[3]){if(p[pl].op){add(p[pl].x[4],p[pl].dp);}++pl;}if(!p[i].op){pr o=ask(p[i].x[4]);o.first+=p[i].v;if(o.first!=p[i].v) p[i].dp+=o;}}for(int i=l;i<pl;i++){if(p[i].op) clear(p[i].x[4]);}//printf(" solve2: ");//for(int i=l;i<=r;i++) print(p[i],i==r);sort(p+mid+1,p+r+1,cmp2);solve2(mid+1,r);return; } void solve1(int l,int r){if(l==r) return;int mid=(l+r)>>1;solve1(l,mid);//sort(p+l,p+mid+1,cmp2);//sort(p+mid+1,p+r+1,cmp2);for(int i=l;i<=mid;i++) p[i].op=1;for(int i=mid+1;i<=r;i++) p[i].op=0;sort(p+l,p+r+1,cmp2);//printf("\nsolve1: ");//for(int i=l;i<=r;i++) print(p[i],i==r);solve2(l,r);sort(p+l,p+r+1,cmp1);solve1(mid+1,r);return; }signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifn=read();m=read();for(int i=1;i<=n;i++){for(int j=1;j<=4;j++) p[i].x[j]=read();p[i].v=read();q[++cnt]=p[i].x[4];p[i].dp=mkp(p[i].v,1);}sort(q+1,q+1+cnt);cnt=unique(q+1,q+1+cnt)-q-1;for(int i=1;i<=n;i++){p[i].x[4]=lower_bound(q+1,q+1+cnt,p[i].x[4])-q;}sort(p+1,p+1+n,cmp1);solve1(1,n);pr ans=mkp(0,1);for(int i=1;i<=n;i++) ans+=p[i].dp;printf("%lld\n%lld\n",ans.first,ans.second);return 0; } /* */

總結

以上是生活随笔為你收集整理的P4849 寻找宝藏（模板：四维偏序）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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