设f[i]是已经走到i号点的值。

先要给第四维离散化、然后去重

第一维排序，第二维cdq分治，第三维cdq分治，第四维树状数组，找到满足j(x,y,z,w)<=i(x,y,z,w)的j，给i统计答案就可以。

然后在做的时候可以直接统计左区间内部答案、统计左区间给右区间造成的答案，但是一定要在这两个做完以后再统计右区间内部的答案，因为用右区间的某个j去更新i时，那个j是会被前面的区间影响的

然后就被卡常了QAQ...分治里一定要写尽量少的sort啊...

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #define LL long long int 9 #define inf 0x3f3f3f3f 10 #define lowbit(x) ((x)&(-(x))) 11 using namespace std; 12 const int maxn=80080,mod=998244353; 13 14 LL rd(){ 15 LL x=0;char c=getchar();int neg=1; 16 while(c<'0'||c>'9'){ if(c=='-') neg=-1;c=getchar();} 17 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 18 return x*neg; 19 } 20 21 struct Node{ 22 int x,y,z,w,i; 23 LL v;bool b; 24 }tmp1[maxn],tmp2[maxn],tmp3[maxn],arr1[maxn]; 25 int N,M,mv[maxn],fv[maxn]; 26 LL ma[maxn],fa[maxn]; 27 const int sizN=sizeof(Node); 28 29 inline void change(int x,LL y,int z){ 30 if(z==0){ 31 while(x&&x<=M) ma[x]=mv[x]=0,x+=lowbit(x); 32 return; 33 } 34 while(x&&x<=M){ 35 if(ma[x]
            
             a) re=mv[x],a=ma[x]; 48 else if(ma[x]==a) re=(re+mv[x])%mod; 49 x-=lowbit(x); 50 }return re; 51 } 52 53 inline bool cmpw(Node a,Node b){ return a.w
             
              =r) return; 66 //printf("!%d %d\n",l,r); 67 int m=l+r>>1,p=l,q=m+1,t=l; 68 cdq2(l,m);sort(tmp1+l,tmp1+m+1,cmpz); 69 memcpy(tmp3+m+1,tmp1+m+1,sizN*(r-m));sort(tmp1+m+1,tmp1+r+1,cmpz); 70 while(p<=m&&q<=r){ 71 if(tmp1[p].z<=tmp1[q].z){ 72 if(!tmp1[p].b){ 73 change(tmp1[p].w,fa[tmp1[p].i],fv[tmp1[p].i]); 74 }p++; 75 }else{ 76 if(tmp1[q].b){ 77 LL a=querya(tmp1[q].w)+tmp1[q].v;int v=queryv(tmp1[q].w); 78 if(v){ 79 if(a>fa[tmp1[q].i]) fa[tmp1[q].i]=a,fv[tmp1[q].i]=v; 80 else if(a==fa[tmp1[q].i]) fv[tmp1[q].i]=(fv[tmp1[q].i]+v)%mod; 81 } 82 } 83 q++; 84 } 85 }while(q<=r){ 86 if(tmp1[q].b){ 87 LL a=querya(tmp1[q].w)+tmp1[q].v;int v=queryv(tmp1[q].w); 88 if(v){ 89 if(a>fa[tmp1[q].i]) fa[tmp1[q].i]=a,fv[tmp1[q].i]=v; 90 else if(a==fa[tmp1[q].i]) fv[tmp1[q].i]=(fv[tmp1[q].i]+v)%mod; 91 } 92 } 93 q++; 94 }for(int i=l;i
              
               =r) return;100 int m=l+r>>1,p=l,q=m+1,t=l;101 cdq1(l,m);sort(arr1+l,arr1+m+1,cmpy);102 memcpy(tmp2+m+1,arr1+m+1,sizN*(r-m));sort(arr1+m+1,arr1+r+1,cmpy);103 while(p<=m&&q<=r){104 if(arr1[p].y<=arr1[q].y){105 tmp1[t]=arr1[p++];tmp1[t].b=0;106 }else{107 tmp1[t]=arr1[q++];tmp1[t].b=1;108 }t++;109 }while(p<=m) tmp1[t]=arr1[p++],tmp1[t++].b=0;110 while(q<=r) tmp1[t]=arr1[q++],tmp1[t++].b=1;111 cdq2(l,r);112 memcpy(arr1+m+1,tmp2+m+1,sizN*(r-m));cdq1(m+1,r);113 }114 115 int main(){116 //freopen("xzbz.in","r",stdin);117 int i,j,k;118 N=rd(),M=rd();119 for(i=1;i<=N;i++){120 tmp1[i].i=i;tmp1[i].x=rd();tmp1[i].y=rd();121 tmp1[i].z=rd();tmp1[i].w=rd();tmp1[i].v=rd();122 }sort(tmp1+1,tmp1+N+1,cmpw);123 for(i=1,j=0;i<=N;i++){124 tmp2[i]=tmp1[i];125 if(tmp1[i].w==tmp1[i-1].w) tmp2[i].w=j;126 else tmp2[i].w=++j;127 }M=j;128 sort(tmp2+1,tmp2+N+1,cmpx);129 for(i=1,j=0;i<=N;i++){130 if(tmp2[i].x==tmp2[i-1].x&&tmp2[i].y==tmp2[i-1].y&&tmp2[i].z==tmp2[i-1].z&&tmp2[i].w==tmp2[i-1].w){131 arr1[j].v=(arr1[j].v+tmp2[i].v)%mod;132 fa[j]=arr1[j].v;133 }else{134 arr1[++j]=tmp2[i];arr1[j].i=j;135 fa[j]=arr1[j].v;fv[j]=1;136 }137 }N=j;138 cdq1(1,N);139 LL a=0;int v=0;140 for(i=1;i<=N;i++){141 if(fa[i]>a) a=fa[i],v=fv[i];142 else if(fa[i]==a) v=(v+fv[i])%mod;143 }printf("%lld\n%d",a,v);144 return 0;145 }