DTOJ3704 威士忌（whiskey）

题目

题目描述

Alan喝了假威士忌，想问你一个问题：
nvliu66推荐大家读三本书《百年孤独》、《城市发展史》、《美国大城市的生与死》（？？？）
三本书的总页数分别为$p,q,r$
现有$n$个nvliu66的粉丝，作为nvliu66的粉丝，想必每本书都至少读过一页，其中第$i$个粉丝读过$a_i$页《百年孤独》、$b_i$页《城市发展史》、$c_i$页《美国大城市的生与死》$(1⩽a_i⩽p,1⩽b_i⩽q,1⩽c_i⩽r)$
如果粉丝$x$有不少于两本书阅读过的页数都严格多余粉丝$y$，即当 $a_x>a_y,b_x>b_y,c_x>c_y$ 三个条件中有至少两个成立时，那么称$x$比$y$更“博闻强识”（？？？）
Alan作为nvliu66的粉丝，也决定去读$a_0$ 页《百年孤独》、$b_0$页《城市发展史》、$c_0$页《美国大城市的生与死》 $(1⩽a_0⩽p,1⩽b_0⩽q,1⩽c_0⩽r)$
如果Alan比$n$个粉丝都要博闻强识，那么他就会感到很奴比（？？？）
Alan想知道自己有多少种不同的读书方案使自己会很奴比，两个读书方案不同当且仅当存在一本书读取的页数不同

输入格式

第一行，四个整数$n,p,q,r$
接下来$n$行，每行三个整数$a_i,b_i,c_i$

输出格式

一行，表示答案

样例

样例输入

3 4 4 5
2 2 5
1 3 4
4 1 1

样例输出

10

数据范围与提示

对于$30\%$的数据，$n,p,q,r⩽100$
对于$60\%$的数据，$n,p,q,r⩽50000$
对于$100\%$的数据，$n,p,q,r⩽500000$

题解

首先，我们先将这些粉丝按$a_i$的大小来排序，然后我们枚举$a_0$的大小，有两种情况：

1. 如果$a_i>a_0$，那我们就要要求$b>b_i$并且$c>c_i$，为了方便，我们可以先预处理求出$max{b}_i$和$max{c}_i$（后缀最大值）
2. 如果$a_i<a_0$，那我们就要要求$b>b_i$或$c>c_i$，所以我们把所有的$(b_i,c_i)$数对转化为直角坐标系上的点，那么$(b_0,c_0)$就不能在任何一个以$(b_i,c_i)$组成的矩形中，又因为这些矩形的并集的$y$是递减的，所以我们就可以用一棵线段树来维护这些矩形的并集的面积

附上代码：

#include<algorithm>
#include<cstdio>
using namespace std;
struct ppap
{
	int a,b,c;
}s[500010];
struct Segment_Tree
{
	int min,add;
	long long sum;
}t[2000010];
int n,p,q,r,maxb[500010],maxc[500010];
long long ans;
int cmp(const ppap &a,const ppap &b)
{
	return a.a<b.a;
}
void spread(int p,int l,int r)
{
	int mid=(l+r)/2;
	t[p*2].add=t[p*2+1].add=t[p*2].min=t[p*2+1].min=t[p].add,t[p*2].sum=(mid-l+1)*t[p].add,t[p*2+1].sum=(r-mid)*t[p].add,t[p].add=0;
}
int find(int p,int l,int r,int x)
{
	if(l==r) return (t[p].min<x?l:l+1);
	if(t[p].add) spread(p,l,r);
	int mid=(l+r)>>1;
	if(t[p*2].min<x) return find(p*2,l,mid,x);
	else return find(p*2+1,mid+1,r,x);
}
void change(int p,int l,int r,int L,int R,int d)
{
	if(L<=l&&r<=R){t[p].min=t[p].add=d,t[p].sum=(r-l+1)*d;return;}
	if(t[p].add) spread(p,l,r);
	int mid=(l+r)/2;
	if(L<=mid) change(p*2,l,mid,L,R,d);
	if(R>mid) change(p*2+1,mid+1,r,L,R,d);
	t[p].sum=t[p*2].sum+t[p*2+1].sum,t[p].min=min(t[p*2].min,t[p*2+1].min);
}
long long Ask(int p,int l,int r,int L,int R)
{
	if(L<=l&&r<=R) return t[p].sum;
	if(t[p].add) spread(p,l,r);
	int mid=(l+r)/2;
	long long ans=0;
	if(L<=mid) ans+=Ask(p*2,l,mid,L,R);
	if(R>mid) ans+=Ask(p*2+1,mid+1,r,L,R);
	return ans;
}
long long ask(int b,int c)
{
	int x=find(1,1,r,b);
	if(x<=c) return 1ll*(c-x+1)*b-Ask(1,1,r,x,c);
	return 0;
}
int main()
{
	freopen("whiskey.in","r",stdin);
	freopen("whiskey.out","w",stdout);
	scanf("%d%d%d%d",&n,&p,&q,&r);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
	sort(s+1,s+n+1,cmp);
	for(int i=n;i;i--) maxb[i]=max(maxb[i+1],s[i].b),maxc[i]=max(maxc[i+1],s[i].c);
	for(int i=1;i<=n;i++){
		long long Ans=ask(q,r)-ask(maxb[i],r)-ask(q,maxc[i])+ask(maxb[i],maxc[i]);
		ans+=Ans*(s[i].a-s[i-1].a);
		int x=find(1,1,r,s[i].b);
		if(x<=s[i].c) change(1,1,r,x,s[i].c,s[i].b);
	}
	printf("%lld",ans+1ll*(p-s[n].a)*ask(q,r));
}