思路： 我只是想写一下cdq…… 二维偏序 一维排序 一维cdq分治 （我忘了归并排序怎么写了,,,） 写了个sort… 复杂度是O(nlog^2n)
//By SiriusRen #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=100050; #define int long long int n,m,k,recy[N],f[N]; struct Node{int x,y,p;}node[N]; bool cmp(Node a,Node b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;} struct Temp{int op,k,id;Temp(){}Temp(int x,int y,int z){op=x,k=y,id=z;}}temp[N]; bool Cmp(Temp a,Temp b){if(a.k!=b.k)return a.k<b.k;return a.op>b.op;} void cdq(int l,int r){ if(l>=r){f[l]=max(node[l].p,f[l]);return;} int mid=(l+r)>>1,top=0,maxx=0; cdq(l,mid); for(int i=l;i<=mid;i++)temp[++top]=Temp(1,node[i].y,i); for(int i=mid+1;i<=r;i++)temp[++top]=Temp(0,node[i].y,i); sort(temp+1,temp+1+top,Cmp); for(int i=1;i<=top;i++){ if(temp[i].op)maxx=max(f[temp[i].id],maxx); else f[temp[i].id]=max(f[temp[i].id],maxx+node[temp[i].id].p); } cdq(mid+1,r); } signed main(){ scanf("%lld%lld%lld",&n,&m,&k); for(int i=1;i<=k;i++)scanf("%lld%lld%lld",&node[i].x,&node[i].y,&node[i].p),recy[i]=node[i].y; sort(node+1,node+1+k,cmp); cdq(1,k); for(int i=1;i<=k;i++)f[k]=max(f[k],f[i]); printf("%lld\n",f[k]); }