【BZOJ-4636】蒟蒻的数列 动态开点线段树 ||(离散化) + 标记永久化

4636: 蒟蒻的数列

Time Limit: 30 Sec  Memory Limit: 256 MB
Submit: 247  Solved: 113
[Submit][Status][Discuss]

Description

蒟蒻DCrusher不仅喜欢玩扑克,还喜欢研究数列
题目描述
DCrusher有一个数列,初始值均为0,他进行N次操作,每次将数列[a,b)这个区间中所有比k小的数改为k,他想知
道N次操作后数列中所有元素的和。他还要玩其他游戏,所以这个问题留给你解决。
 

Input

第一行一个整数N,然后有N行,每行三个正整数a、b、k。
N<=40000 , a、b、k<=10^9

Output

一个数,数列中所有元素的和

Sample Input

4
2 5 1
9 10 4
6 8 2
4 6 3

Sample Output

16

HINT

Source

Solution

这题似乎是IOI-Wall的弱化版

可行的做法有两种:

Part1: 动态开点线段树

动态的添加区间,标记永久化

最后遍历一遍线段树,统计一下答案

Part2:离散化普通线段树

把需要操作的区间离散化,对每个节点维护左右端点.离散化后对应长度.以及K

在打标记的时候,注意比较,实际上和标记永久化维护半平面交有点类似的思想

然后区间修改区间求和就可以了

Part1.时间较优,但空间较大 Part2.时间尚可,但空间较优

Code

最开始大家想法是Part2,但这里提供更好写的Part1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int N,a,b,K;
long long ans;
#define MAXN 50000
struct SegmentTreeNode
{
    int data[MAXN<<8],son[MAXN<<8][2],root,sz;
    void Insert(int &rt,int l,int r,int L,int R,int x)
        {
            if (L>R) return;
            if (!rt) rt=++sz;
            if (l==L && R==r) {data[rt]=max(data[rt],x); return;}
            int mid=(l+r)>>1;
            if (R<=mid) Insert(son[rt][0],l,mid,L,R,x);
            else if (L>mid) Insert(son[rt][1],mid+1,r,L,R,x);
            else Insert(son[rt][0],l,mid,L,mid,x),Insert(son[rt][1],mid+1,r,mid+1,R,x);
        }
    void Query(int rt,int l,int r,int x)
        {
            if (!rt) return;
            data[rt]=max(data[rt],x);
            if (!son[rt][0] && !son[rt][1]) {ans+=(long long)((r-l+1)*data[rt]); return;}
            int mid=(l+r)>>1;
            Query(son[rt][0],l,mid,data[rt]),Query(son[rt][1],mid+1,r,data[rt]);
            if (!son[rt][0]) ans+=(long long)((mid-l+1)*data[rt]);
            if (!son[rt][1]) ans+=(long long)((r-mid)*data[rt]);
        }
}SegTree;
#define INF (int)1e9
void Freopen() {freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);}
void Fclose() {fclose(stdin);fclose(stdout);}
int main()
{
    //Freopen();
    N=read();
    while (N--)
        a=read(),b=read(),K=read(),
        SegTree.Insert(SegTree.root,1,INF,a,b-1,K);
    SegTree.Query(SegTree.root,1,INF,0);
    printf("%lld
",ans);
    return 0;
}

蛋爷上传的题目,最早来源是faebdc学长放到洛谷上的

澄清一个事实: 题面里的DCrusher是神犇!是神犇!是神犇!不是蒟蒻

原文地址:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5668130.html