CF815D

shight · 2022-04-06 19:04:10 · 题解

模拟赛遇到的题目。

看各位大佬的做法都不是很懂，于是自己一通乱搞搞出来了。

题意

翻译清楚的不能再清楚了

做法

为了方便叙述，我们将每个给出的三元组表示成 (a_i,b_i,c_i)，所选的三元组表示成(x,y,z)。

首先我们考虑如果 c_i 相等（设为 c）怎么做：

直接做看起来很麻烦，于是我们考虑正难则反，由算可行解数量改为算不可行解数量，并维护对于每一个 y 可选的 x ，显然对于每一个y，x的选择满足单调性。

然后我们分类讨论一下 z 和 c_i 的大小关系

当 z \le c 时，对于每一个三元组,当 y \in [1,b_i] 时， x>p；当 y \in (b_i,q] 时，x>a_i。

当 z>c 时，对于每一个三元组，只需满足当 y \in [1,b_i]时，x>a_i 即可。

拿个线段树维护一下就可以了。

然后我们将这种做法拓展一下，我们先把原序列按 c_i 从大到小排序，可以轻易发现此时当 z \in (c_i,c_{i+1}] 时，每一个 z 贡献都是一样的

对于每一个区间(c_i,c_{i+1}]，我们考虑上面的做法来算贡献，显然对于前 i 个三元组，满足 z>c 的条件，对于后面的三元组，满足 z \le c 的条件。

且显然 z \le c 的条件是比 z > c 完全严格的，所以每次修改的时候把 z > c的条件给当前枚举到的三元组加上去就好了。

然后关于这个线段树，我们需要维护区间最大值，区间求和，这个可以自行百度解决（相信做到这道题的大佬都会）。

#include <bits/stdc++.h>
#define int long long
#define INF 2147483647
#define N 1000005
#define mkp make_pair
#define pii pair<int,int>
#define pb push_back
using namespace std;
int n,A,B,C,ans=0;
struct Y{int a,b,c;}a[N];
int cmp(Y x,Y y){return x.c>y.c;}
struct Ji_seg{
    struct Tr{
        int mn,tag,t,se,sum;
    }tr[N<<2];
    int ls(int nw){return nw*2;}
    int rs(int nw){return nw*2+1;}
    void change(int nw,int l,int r,int k){//对nw节点的区间进行区间取max 
        if(k<=tr[nw].mn)return;
        if(k<tr[nw].se){
            tr[nw].sum+=(k-tr[nw].mn)*tr[nw].t;
            tr[nw].mn=k;tr[nw].t=max(tr[nw].t,1ll);tr[nw].tag=max(tr[nw].tag,k);
            return;
        }
        int mid=(l+r)/2;
        change(ls(nw),l,mid,k);change(rs(nw),mid+1,r,k);push_up(nw);
    }
    void push_down(int nw,int l,int r){
        if(tr[nw].tag){
            int mid=(l+r)/2;
            change(ls(nw),l,mid,tr[nw].tag);
            change(rs(nw),mid+1,r,tr[nw].tag);
            tr[nw].tag=0;
        }
    }
    void push_up(int nw){
        tr[nw].sum=tr[ls(nw)].sum+tr[rs(nw)].sum;
        if(tr[ls(nw)].mn==tr[rs(nw)].mn){
            tr[nw].mn=tr[ls(nw)].mn;
            tr[nw].t=tr[ls(nw)].t+tr[rs(nw)].t;
            tr[nw].se=min(tr[ls(nw)].se,tr[rs(nw)].se);
            return;
        }
        if(tr[ls(nw)].mn<tr[rs(nw)].mn){tr[nw].mn=tr[ls(nw)].mn;tr[nw].t=tr[ls(nw)].t;tr[nw].se=min(tr[ls(nw)].se,tr[rs(nw)].mn);}
            else {tr[nw].mn=tr[rs(nw)].mn;tr[nw].t=tr[rs(nw)].t;tr[nw].se=min(tr[rs(nw)].se,tr[ls(nw)].mn);}
    }
    void build(int nw,int l,int r){
        if(l==r){
            tr[nw].sum=0;tr[nw].mn=0;tr[nw].se=INF;tr[nw].t=1;tr[nw].tag=0;
            return;
        }
        int mid=(l+r)/2;
        build(ls(nw),l,mid);
        build(rs(nw),mid+1,r);
        push_up(nw);
    }
    void update(int nw,int l,int r,int x,int y,int k){
        if(x>y)return;
        if(x<=l&&r<=y){
            change(nw,l,r,k);
            return;
        }
        int mid=(l+r)/2;push_down(nw,l,r);
        if(x<=mid)update(ls(nw),l,mid,x,y,k);
        if(y>mid)update(rs(nw),mid+1,r,x,y,k);
        push_up(nw);
    }
}T;
signed main() {
    scanf("%lld %lld %lld %lld",&n,&A,&B,&C);
    for(int i=1;i<=n;i++)scanf("%lld %lld %lld",&a[i].a,&a[i].b,&a[i].c);
    sort(a+1,a+n+1,cmp);a[0]=Y{0,0,C};a[n+1]=Y{0,0,0};
    T.build(1,1,B);
    for(int i=1;i<=n;i++)T.update(1,1,B,1,a[i].b,a[i].a);
    for(int i=0;i<=n;i++){
        T.update(1,1,B,1,a[i].b,A);T.update(1,1,B,a[i].b+1,B,a[i].a);
        ans+=(a[i].c-a[i+1].c)*(A*B-T.tr[1].sum);
    }
    printf("%lld\n",ans);
    return 0;
}