BZOJ 4636 蒟蒻的数列 - 排序+线段树/set

154 阅读 0 评论 102 点赞

我是靠谱客的博主繁荣钢笔，这篇文章主要介绍BZOJ 4636 蒟蒻的数列 - 排序+线段树/set，现在分享给大家，希望可以做个参考。

排序真是门博大精深的学问。。。

先说线段树，大概就是按照大小排个序，小的排在前，然后直接覆盖上一层，线段树set之后维护一下就好了。只不过范围太大，得动态开节点。

还得注意：线段树动态开节点的pushdown的写法：子树有可能未建立，不能直接传递下标，于是先建树，调用set函数建树+传递下标一回了事。

复制代码

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn=40005;
const int maxm=1e9;

struct operation
{
    int x,y,val;
    bool operator < (const operation tmp) const
    {
        return val<tmp.val;
    } 
}q[maxn];
struct tree
{
    long long val;
    int set,lson,rson;
}t[3000000];

int n,cnt,root;
void update(int &ro,int L,int R,int val,int l,int r);

void pushdown(int ro,int l,int r)
{
    int mid=l+r>>1;
    if(t[ro].set)
    {

/*
        if(t[ro].lson)
        {
            t[t[ro].lson].set=t[ro].set;
            t[t[ro].lson].val=(mid-l+1)*t[ro].set;
        }
        if(t[ro].rson)
        {
            t[t[ro].rson].set=t[ro].set;
            t[t[ro].rson].val=(r-mid)*t[ro].set;
        }*/
        //有可能子树还未建立，需要先建立再打tag 
        update(t[ro].lson,l,mid,t[ro].set,l,mid);
        update(t[ro].rson,mid+1,r,t[ro].set,mid+1,r);
        t[ro].set=0;
    }
}
void maintain(int ro)
{
    t[ro].val=0;
    if(t[ro].lson)t[ro].val+=t[t[ro].lson].val;
    if(t[ro].rson)t[ro].val+=t[t[ro].rson].val;
}
void update(int &ro,int L,int R,int val,int l,int r)
{
    if(!ro)ro=++cnt;
    if(l==L&&r==R)
    {
        t[ro].set=val;
        t[ro].val=1LL*val*(r-l+1);
        return;
    }
    pushdown(ro,l,r);
    int mid=l+r>>1;
    if(R<=mid)update(t[ro].lson,L,R,val,l,mid);
    else if(L>=mid+1)update(t[ro].rson,L,R,val,mid+1,r);
    else update(t[ro].lson,L,mid,val,l,mid),update(t[ro].rson,mid+1,R,val,mid+1,r);
    maintain(ro);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].val);
    sort(q+1,q+n+1);
    for(int i=1;i<=n;i++)
        if(q[i].x<q[i].y)update(root,q[i].x,q[i].y-1,q[i].val,1,1e9);
    printf("%lld",t[root].val);
    return 0;
}

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
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn=40005;
const int maxm=1e9;

struct operation
{
    int x,y,val;
    bool operator < (const operation tmp) const
    {
        return val<tmp.val;
    } 
}q[maxn];
struct tree
{
    long long val;
    int set,lson,rson;
}t[3000000];

int n,cnt,root;
void update(int &ro,int L,int R,int val,int l,int r);

void pushdown(int ro,int l,int r)
{
    int mid=l+r>>1;
    if(t[ro].set)
    {

        /*
        if(t[ro].lson)
        {
            t[t[ro].lson].set=t[ro].set;
            t[t[ro].lson].val=(mid-l+1)*t[ro].set;
        }
        if(t[ro].rson)
        {
            t[t[ro].rson].set=t[ro].set;
            t[t[ro].rson].val=(r-mid)*t[ro].set;
        }*/
        //有可能子树还未建立，需要先建立再打tag 
        update(t[ro].lson,l,mid,t[ro].set,l,mid);
        update(t[ro].rson,mid+1,r,t[ro].set,mid+1,r);
        t[ro].set=0;
    }
}
void maintain(int ro)
{
    t[ro].val=0;
    if(t[ro].lson)t[ro].val+=t[t[ro].lson].val;
    if(t[ro].rson)t[ro].val+=t[t[ro].rson].val;
}
void update(int &ro,int L,int R,int val,int l,int r)
{
    if(!ro)ro=++cnt;
    if(l==L&&r==R)
    {
        t[ro].set=val;
        t[ro].val=1LL*val*(r-l+1);
        return;
    }
    pushdown(ro,l,r);
    int mid=l+r>>1;
    if(R<=mid)update(t[ro].lson,L,R,val,l,mid);
    else if(L>=mid+1)update(t[ro].rson,L,R,val,mid+1,r);
    else update(t[ro].lson,L,mid,val,l,mid),update(t[ro].rson,mid+1,R,val,mid+1,r);
    maintain(ro);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].val);
    sort(q+1,q+n+1);
    for(int i=1;i<=n;i++)
        if(q[i].x<q[i].y)update(root,q[i].x,q[i].y-1,q[i].val,1,1e9);
    printf("%lld",t[root].val);
    return 0;
}

set的话就是那些更新将区域化成了小段，然后每一小段肯定取的是被覆盖的最大值，然后就用循环+set模拟小段，set中存当前最大值。set的值在那个值的l节点时存入，r+1（闭区间）节点清除，每次对于每个小段取set中最大元素即可。

然后set有一个神奇的函数：rbegin()，直接返回最后一个元素的指针（反向迭代函数），比end()之后it–方便多了。

再就是set是集合，相同元素只出现一次，而multiset可以存多个相同的元素。

复制代码

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<algorithm>

using namespace std;

int n,cnt;
long long ans;

multiset<int>s;
multiset<int>::iterator it;

struct node
{
    int pos,val,op;
    bool operator < (const node tmp) const
    {
        return pos<tmp.pos;
    }
}q[40005<<1];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a==b)continue;
        q[++cnt]=(node){a,c,0};
        q[++cnt]=(node){b,c,1};
    }
    sort(q+1,q+cnt+1);
    for(int i=1;i<=cnt;i++)
    {
        if(q[i].pos!=q[i-1].pos&&!s.empty())
            ans+=(q[i].pos-q[i-1].pos)* *s.rbegin();
        if(q[i].op)it=s.lower_bound(q[i].val),s.erase(it);
        else s.insert(q[i].val);
    }
    cout<<ans;
}