CF815D Karen and Cards（题解）
Leap_Frog
·
·
题解
P.S.
来一个垃圾的带 \log 做法。
但是很好想，像我这种傻逼都想得到（
Description.
有 n 个三元组，问有多少好的三元组，满足比所有给定的三元组都要大。
一个三元组 (a,b,c) 是好的，当且仅当：
一个三元组 (a,b,c) 比三元组 (d,e,f) 大，当且仅当：
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 了。
考虑我们每次是把前缀赋成 $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;
}
```