CF815D Karen and Cards（题解）
Leap_Frog
2021-07-29 10:01:00
### P.S.
来一个垃圾的带 $\log$ 做法。
但是很好想，像我这种傻逼都想得到（
### Description.
有 $n$ 个三元组，问有多少好的三元组，满足比所有给定的三元组都要大。
一个三元组 $(a,b,c)$ 是好的，当且仅当：
- $a\le p,b\le q,c\le r$
一个三元组 $(a,b,c)$ 比三元组 $(d,e,f)$ 大，当且仅当：
- $[a>d]+[b>e]+[c>f]\ge2$
### Solution.
看到这个值域的范围是 $500000$，很小。
首先我们考虑 $O(V^2\times n)$ 的做法，首先枚举前两维，然后 $O(n)$ 找出它是否已经比所有三元组大了。
如果 $\exists i\in[1,n],[a>a_i]+[b>b_i]<1$，则无解。
如果 $\exists i\in[1,n],[a>a_i]+[b>b_i]>1$，则第三位任意。
否则第三位就必须满足 $>c_i$。
然后就可以知道第三位所有可能的取值了。
考虑优化掉一个 $n$。
每次枚举，未免太浪费了，考虑 $a$ 从小到大的过程中，$[a>a_i]+[b>b_i]$ 不减。
所以我们从大到小枚举 $a$，这样限制只会变多，每次直接找出当前改变后增多的限制，然后加到 $c$ 里面去即可。
复杂度 $O(V^2+V\times n)$。
考虑用数据结构维护它。
我们可以使用一棵线段树来维护 $b$，线段树上每个点 $i$ 代表 $b=i$ 时 $c$ 的最小值。
然后我们从大到小枚举 $a$，刚开始线段树上所有 $\le b_i$ 的点都有限制 $c_i$，$>b_i$ 的点则没有。
每次 $a=a_i$，线段树上 $\le b_i$ 的所有位置都无解了，所有 $>b_i$ 的点都有限制 $c_i$ 了。
$c_i$ 的限制是对线段树取 $\max$，就为了这个套一个吉司机线段树不合适。
考虑我们每次是把前缀赋成 $q+1$，后缀赋成 $c_i+1$，所以这个序列一定是单调的。
所以我们直接线段树上二分然后区间覆盖即可。
### Coding.
```cpp
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
if(f) x=-x;
}/*}}}*/
const int N=500005;int n,p,q,r,a[N],b[N],c[N],vl[N];
struct segm{ll sm;int mx,fg,ln;}T[N<<2];vector<int>vc[N];
inline void pushup(int x) {T[x].sm=T[x<<1].sm+T[x<<1|1].sm,T[x].mx=max(T[x<<1].mx,T[x<<1|1].mx);}
inline void allc(int x,int c) {T[x].sm=1ll*T[x].ln*c,T[x].mx=T[x].fg=c;}
inline void pushdw(int x) {if(T[x].fg) allc(x<<1,T[x].fg),allc(x<<1|1,T[x].fg),T[x].fg=0;}
inline void build(int x,int l,int r)
{
T[x].fg=0,T[x].ln=r-l+1;if(l==r) return T[x].sm=T[x].mx=vl[l],void();
build(x<<1,l,(l+r)>>1),build(x<<1|1,((l+r)>>1)+1,r),pushup(x);
}
inline void modif(int x,int l,int r,int dl,int dr,int dc)
{
if(l>dr||dl>r) return;else if(dl<=l&&r<=dr) return allc(x,dc);else pushdw(x);
modif(x<<1,l,(l+r)>>1,dl,dr,dc),modif(x<<1|1,((l+r)>>1)+1,r,dl,dr,dc),pushup(x);
}
inline void chang(int x,int l,int r,int dc)
{
if(l==r) return T[x].sm=T[x].mx=max(T[x].mx,dc),void();else pushdw(x);
if(T[x<<1|1].mx>dc) chang(x<<1|1,((l+r)>>1)+1,r,dc),pushup(x);
else allc(x<<1|1,dc),chang(x<<1,l,(l+r)>>1,dc),pushup(x);
}
inline void debug(int x,int l,int r)
{
if(l==r) return printf("%d%c",T[x].mx,l==q?'\n':' '),void();
pushdw(x),debug(x<<1,l,(l+r)>>1),debug(x<<1|1,((l+r)>>1)+1,r);
}
int main()
{
read(n),read(p),read(q),read(r),vl[q+1]=1;
for(int i=1;i<=n;i++) read(a[i]),read(b[i]),read(c[i]),vc[a[i]].push_back(i);
for(int i=1;i<=n;i++) vl[b[i]]=max(c[i]+1,vl[b[i]]);//a=p+1
ll rs=0;for(int i=q;i>=1;i--) vl[i]=max(vl[i],vl[i+1]);
//for(int i=1;i<=q;i++) printf("%d%c",vl[i],i==q?'\n':' ');
build(1,1,q);for(int i=p;i>=1;i--,rs+=1ll*(r+1)*q-T[1].sm)
for(auto j:vc[i]) chang(1,1,q,c[j]+1),modif(1,1,q,1,b[j],r+1);
return printf("%lld\n",rs),0;
}
```