题意
每张卡牌有四个属性，我们称一张卡牌能胜过另一张卡牌，当且仅当其至少有三个属性都大于另一张卡牌。
Bob 拥有 \(m\) 张卡牌，而 Alice 拥有每个属性值在 \([1,n]\) 的所有 \(n^4\) 张卡牌。
现在 Alice 想知道：她有多少张卡牌可以胜过所有 Bob 的卡牌？
思路
乍一看是巨大多数高维数点题，仔细一做发现是清新 \(O(n)\) 小 DS。很有趣！
首先我们考虑如何处理“至多一维”是输的这个限制，方法是对于每对不同的两维，要求它们不能同时是输的。即 \(a\le a_i,b\le b_i\) 不能同时成立。
那么类似 2-SAT 建图的想法，我们把这种关系描述成“若 \(a\le a_i\)，则 \(b> b_i\)”或者“若 \(b\le b_i\)，则 \(a> a_i\)”。发现这个限制关系是单向的且是可以任意定向的，保留上述两个式子的任意一个都与原来的条件等价，给了我们很多操作空间。
我们考虑先从大到小枚举 \(d\) 这一维，此时 \(d\) 的取值会对 \(a,b,c\) 的取值有一个下界限制，这个限制会不断的缩紧。相当于每次删去 \(a,b,c\) 数组的一段前缀。
我们记录下 \(a,b,c\) 数组每个位置被删除的时间 \(av,bv,cv\)，那么对于一个合法的 \((a,b,c)\) 三元组，对答案的贡献就是 \(\min(av_a,bv_b,cv_c)\)。
现在原题变成了一个带了一点权的三维问题，而本题三维的情况是很好做到 \(O(n)\) 的。具体方法是枚举一维，然后其对于第二、三维有一个下界限制，而第二维的值对于第三维也是一个下界限制。对于第二维的一个取值，第三维的取值个数可以用一个 \(\max\) 表示。而一维对另一维的限制数组具有单调性，所以用双指针求下分界点前缀和一下就可以做完了。
如何处理对于答案的贡献的那个 \(\min\) 呢？注意到 \(a,b,c\) 地位相同，所以你钦定是哪一维取到最小值，对其它维的限制也是一个下界，把这一维当作前面方法所述的第一维做就好了。
代码很好写，复制粘贴一下就没啥细节了。总时间复杂度为 \(O(n)\)。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned int ui;
ui read(){/* read */}
const ui N=500003;
ui n,m;
ui a[N],b[N],c[N],d[N];
ui amx[N],bmx[N],cmx[N];
ui av[N],bv[N],cv[N];
ui ab[N],ac[N];
ui ba[N],bc[N];
ui ca[N],cb[N];
ui ps[N],w[N];
inline void chmx(ui &x,ui v){if(x<v) x=v;}
int main(){
n=read();m=read();
for(ui i=1;i<=m;++i) a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();
for(ui i=1;i<=m;++i){
chmx(amx[d[i]],a[i]);
chmx(bmx[d[i]],b[i]);
chmx(cmx[d[i]],c[i]);
chmx(ab[a[i]],b[i]);
chmx(ac[a[i]],c[i]);
chmx(ba[b[i]],a[i]);
chmx(bc[b[i]],c[i]);
chmx(ca[c[i]],a[i]);
chmx(cb[c[i]],b[i]);
}
for(ui i=n-1;i;--i){
chmx(amx[i],amx[i+1]);
chmx(bmx[i],bmx[i+1]);
chmx(cmx[i],cmx[i+1]);
chmx(ab[i],ab[i+1]);
chmx(ac[i],ac[i+1]);
chmx(ba[i],ba[i+1]);
chmx(bc[i],bc[i+1]);
chmx(ca[i],ca[i+1]);
chmx(cb[i],cb[i+1]);
}
ui ap=1,bp=1,cp=1;
for(ui i=n;i;--i){
while(ap<=amx[i]) av[ap++]=n-i;
while(bp<=bmx[i]) bv[bp++]=n-i;
while(cp<=cmx[i]) cv[cp++]=n-i;
}
while(ap<=m) av[ap++]=n;
while(bp<=m) bv[bp++]=n;
while(cp<=m) cv[cp++]=n;
ui res=0;
for(ui i=1;i<=n;++i) w[i]=w[i-1]+n-bc[i];
for(ui i=n+1,t=1;i;--i){
while(t<=n&&bc[t]>=i) ++t;
ps[i]=t-1;
}
bp=cp=1;
for(ui a=1;a<=n;++a){
while(bp<=n&&bv[bp]<av[a]) ++bp;
while(cp<=n&&cv[cp]<av[a]) ++cp;
ui bl=max(bp,ab[a]+1);
ui cl=max(cp,ac[a]+1);
if(ps[cl]<bl) res+=(n-bl+1)*(n-cl+1)*av[a];
else res+=((n-ps[cl])*(n-cl+1)+w[ps[cl]]-w[bl-1])*av[a];
}
for(ui i=1;i<=n;++i) w[i]=w[i-1]+n-ac[i];
for(ui i=n+1,t=1;i;--i){
while(t<=n&&ac[t]>=i) ++t;
ps[i]=t-1;
}
ap=cp=1;
for(ui b=1;b<=n;++b){
while(ap<=n&&av[ap]<=bv[b]) ++ap;
while(cp<=n&&cv[cp]<bv[b]) ++cp;
ui al=max(ap,ba[b]+1);
ui cl=max(cp,bc[b]+1);
if(ps[cl]<al) res+=(n-al+1)*(n-cl+1)*bv[b];
else res+=((n-ps[cl])*(n-cl+1)+w[ps[cl]]-w[al-1])*bv[b];
}
for(ui i=1;i<=n;++i) w[i]=w[i-1]+n-ab[i];
for(ui i=n+1,t=1;i;--i){
while(t<=n&&ab[t]>=i) ++t;
ps[i]=t-1;
}
ap=bp=1;
for(ui c=1;c<=n;++c){
while(ap<=n&&av[ap]<=cv[c]) ++ap;
while(bp<=n&&bv[bp]<=cv[c]) ++bp;
ui al=max(ap,ca[c]+1);
ui bl=max(bp,cb[c]+1);
if(ps[bl]<al) res+=(n-al+1)*(n-bl+1)*cv[c];
else res+=((n-ps[bl])*(n-bl+1)+w[ps[bl]]-w[al-1])*cv[c];
}
printf("%u\n",res);
return 0;
}