[洛谷春令营 D1T3] 过年【权值线段树】
题目描述
有 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; }
发表评论