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

• 2018-02-09
• 0
• 0

```6 3
1 5 1
2 3 2
3 4 2
```

```1
1
2
1
1
-1
```

## Solution:

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

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai