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

  • 2018-02-09
  • 0
  • 0

题目描述

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

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

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

输入输出格式

输入格式:

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

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

输出格式:

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

输入输出样例

输入样例#1:

6 3
1 5 1
2 3 2
3 4 2

输出样例#1:

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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai