[洛谷春令营 D1T3] 过年【权值线段树】

• 2018-02-09
• 0
• 0

题目描述

有 n (1≤n≤10⁵) 个小朋友，过年了，要发放 m (1≤m≤10⁵) 次礼物。

每次发放，会给出三个参数 l,r,k (1≤l≤r≤n , 1≤k≤10⁵) ，表示给区间 [l, r] 内的小朋友都发一个礼物 k 。

所有礼物发放完成后，对于每一个小朋友，回答他接受的礼物中，出现次数最多的礼物是什么。如果有多个，输出编号最小的那个；如果不存在，输出 -1。

输入输出格式

输入格式：

第一行两个整数 n, m ，意义如上所述。

接下来 m 行，每行三个数 l,r,k ，意义如上所述。

输出格式：

一共 n 行，每行一个数，表示答案。

输入输出样例

6 3
1 5 1
2 3 2
3 4 2

1
1
2
1
1
-1

Solution:

神奇的扫描线+权值线段树。

利用差分的思想用 vector 记录每个小朋友收到的不同于前一个小朋友的礼物。

从左到右扫描一遍，将增量累加到权值线段树上，并维护区间最大值及其序号。

Code 中的负数是为了简化差分中的删除操作。

PS: 我还学会了指针版线段树。

Code: O(mlogK), 其中k为值域上界(=1e5) [16402KB, 60MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN = 100005;
const int MAXK = 100000;

int n, m, l, r, k;
vector<int> d[MAXN];

struct Node{
    int id, val;
    Node *lc, *rc;

    Node(): lc(NULL), rc(NULL) {}

    inline void update(){
        if(lc->val >= rc->val) val = lc->val, id = lc->id;
        else val = rc->val, id = rc->id;
    }
} pool[MAXN << 2];

inline Node* newNode(){
    static int topp = 0;
    return &pool[topp++];
}

inline Node* build(int l, int r){
    Node *cur = newNode();
    if(l == r) cur->id = l, cur->val = 0;
    else{
        int smid = l + r >> 1;
        cur->lc = build(l, smid);
        cur->rc = build(smid + 1, r);
        cur->update();
    }
    return cur;
}

inline void add(Node *cur, int l, int r, int pos, int v){
    if(l == r) {cur->val += v; return;}
    int smid = l + r >> 1;
    if(pos <= smid) add(cur->lc, l, smid, pos, v);
    else add(cur->rc, smid + 1, r, pos, v);
    cur->update();
}

int main(){
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= m; i++){
        scanf("%d%d%d", &l, &r, &k);
        d[l].push_back(k);
        d[r + 1].push_back(-k);
    }
    Node *root = build(1, MAXK);
    for(register int i = 1; i <= n; i++){
        for(register int j = d[i].size() - 1; j >= 0; j--){
            int pos = d[i][j];
            if(pos > 0) add(root, 1, MAXK, pos, 1);
            else add(root, 1, MAXK, -pos, -1);
        }
        if(root->val) printf("%d\n", root->id);
        else puts("-1");
    }
    return 0;
}