学好数理化，走遍天下都不怕

DTOJ3704 威士忌（whiskey）

发表于 更新于 分类于

题目

题目描述

Alan喝了假威士忌，想问你一个问题：
nvliu66推荐大家读三本书《百年孤独》、《城市发展史》、《美国大城市的生与死》（？？？）
三本书的总页数分别为$p,q,r$
现有$n$个nvliu66的粉丝，作为nvliu66的粉丝，想必每本书都至少读过一页，其中第$i$个粉丝读过$a_i$页《百年孤独》、$b_i$页《城市发展史》、$c_i$页《美国大城市的生与死》$(1 \leqslant a_i \leqslant p,1 \leqslant b_i \leqslant q,1 \leqslant c_i \leqslant 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 \leqslant a_0 \leqslant p,1 \leqslant b_0 \leqslant q,1 \leqslant c_0 \leqslant r)$
如果Alan比$n$个粉丝都要博闻强识，那么他就会感到很奴比（？？？）
Alan想知道自己有多少种不同的读书方案使自己会很奴比，两个读书方案不同当且仅当存在一本书读取的页数不同

输入格式

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

输出格式

一行，表示答案

样例

样例输入

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

样例输出

1
10

数据范围与提示

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

题解

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

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

附上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#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));
}