BZOJ 4636: 직경 33951 의 수열 이 빠 르 고 int 64 선분 수

Description: 33951: 33979: DCrusher 는 포커 를 좋아 할 뿐만 아니 라 수열 문제 에 대한 묘사 도 좋아 합 니 다. DCrusher 는 수열 이 있 습 니 다. 초기 값 은 0 입 니 다. 그 는 N 번 조작 을 합 니 다. 매번 수열 [a, b) 이 구간 의 모든 k 보다 작은 수 를 k 로 바 꿉 니 다. 그 는 N 번 조작 후 수열 에 있 는 요소 의 합 을 알 고 싶 습 니 다. 그 는 다른 게임 을 해 야 하기 때문에 이 문 제 는 당신 에 게 해결 해 주 었 습 니 다.
Input 첫 줄 의 정수 N, 그리고 N 줄 이 있 습 니 다. 줄 마다 세 개의 정수 a, b, k. N < = 40000, a, b, k < = 10 ^ 9 출력 하나의 수, 수열 에 있 는 모든 요소 의 합.
Sample Input 4
2 5 1
9 10 4
6 8 2
4 6 3 Sample Output 16
해법 1: 동적 개방 점 선분 트 리 는 선분 트 리 에 직접 표 시 를 하고 마지막 으로 dfs 는 전체 선분 트 리 를 한 번 에 표시 하면 됩 니 다. 구간 길이 가 비교적 크기 때문에 동적 개방 점 이 필요 합 니 다. 구축 되 지 않 은 노드 도 기여 하 므 로 이 를 넣 어야 합 니 다.

//151288 kb  788ms O(nsqrt(n))
#include 
using namespace std;
const int maxn = 50000;
const int inf = 1e9;
long long ans;
int n, a, b, k;
namespace int64segmenttree{
    int sum[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){
            sum[rt] = max(sum[rt], x);
            return ;
        }
        int mid = (l + r) / 2;
        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 ;
        sum[rt] = max(sum[rt], x);
        if(!son[rt][0] && !son[rt][1]){
            ans += 1LL * (r - l + 1) * sum[rt];
            return ;
        }
        int mid = (l + r) / 2;
        query(son[rt][0], l, mid, sum[rt]);
        query(son[rt][1], mid + 1, r, sum[rt]);
        if(!son[rt][0]) ans += 1LL * (mid - l + 1) * sum[rt];
        if(!son[rt][1]) ans += 1LL * (r - mid) * sum[rt];
    }
}
using namespace int64segmenttree;

int main(){
    int n, a, b, k;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d%d", &a, &b, &k);
        insert(root, 1, inf, a, b - 1, k);
    }
    query(root, 1, inf, 0);
    printf("%lld
", ans);
    return 0;
}

해법 2: 이산 화 + 블록 15072 kb 2356 ms

#include 
using namespace std;
const int maxn = 2e5+7;
int n, m, num, belong[maxn], block, l[maxn], r[maxn], low[maxn];
vector <int> V;//   
map <int, int> H1; //   
map <int, int> H2; //  
int A[maxn], B[maxn], K[maxn], a[maxn];

void build(){
    block = sqrt(n);
    num = n / block; if(n%block) num++;
    for(int i = 1; i <= num; i++) l[i] = (i - 1) * block + 1, r[i] = i * block;
    r[num] = n;
    for(int i = 1; i <= n; i++) belong[i] = (i - 1) / block + 1;
}

void update(int L, int R, int k){
    if(L > R) return;
    if(belong[L] == belong[R]){
        for(int i = l[belong[L]]; i <= r[belong[L]]; i++) a[i] = max(a[i], low[belong[L]]); low[belong[L]] = 0;
        for(int i = L; i <= R; i++) a[i] = max(a[i], k);
        return;
    }
    for(int i = l[belong[L]]; i <= r[belong[L]]; i++) a[i] = max(a[i], low[belong[L]]); low[belong[L]] = 0;
    for(int i = l[belong[R]]; i <= r[belong[R]]; i++) a[i] = max(a[i], low[belong[R]]); low[belong[R]] = 0;
    for(int i = L; i <= r[belong[L]]; i++) a[i] = max(a[i], k);
    for(int i = l[belong[R]]; i <= R; i++) a[i] = max(a[i], k);
    for(int i = belong[L] + 1; i < belong[R]; i++) low[i] = max(low[i], k);
}

int main(){
    scanf("%d", &m);
    for(int i = 1; i <= m; i++){//     ，            3      
        scanf("%d%d%d", &A[i], &B[i], &K[i]);
        V.push_back(A[i]), V.push_back(B[i]), V.push_back(B[i] - 1);
    }
    n = 3*m;
    build();
    sort(V.begin(), V.end()), V.erase(unique(V.begin(), V.end()), V.end());
    for(int i = 0; i < (int) V.size(); i++){
        H1[V[i]] = i + 1, H2[i + 1] = V[i];
    }
    long long ans = 0;
    for(int i = 1; i <= m; i++) update(H1[A[i]], H1[B[i] - 1], K[i]);
    for(int i = 0; i < (int) (V.size()); i++) a[i + 1] = max(a[i + 1], low[belong[i + 1]]);
    for(int i = 0; i < (int) (V.size() - 1); i++) ans += (H2[i + 2] - H2[i + 1]) * a[i + 1];
    printf("%lld
", ans);
    return 0;
}