题目描述
DCrusher有一个数列，初始值均为0，他进行N次操作，每次将数列[a,b)这个区间中所有比k小的数改为k，他想知道N次操作后数列中所有元素的和。他还要玩其他游戏，所以这个问题留给你解决。
题解
这题因为a,b过大所以不能直接维护线段树和可持久化线段树。
之后我们仔细研究此题发现这题不用在线做！可以离线！
因为是把比k小的数改为k，又是问最后的答案，所以很容易想到所有k输入后将其排序，从大到小枚举。
每次只需把[a,b)区间内没有改过的数改为k即可，因为被改过的数被改的值一定比当前的k大。
现在我们考虑如何维护线段树。
在每个节点记录两个值，一个代表现在这个区间有多少被改过的值，一个是懒惰标记。
更改就像正常更改找区间，如果找到了一个区间，就把更新答案，$ans+=(区间长度 - 区间有多少改过数) \times 当前k$。
ans += (r - l + 1 - tr[p].val) * k;
之后将有多少数改过设成区间长，打上懒惰标记。
if (x <= l && r <= y) {
ans += (r - l + 1 - tr[p].val) * k;
tr[p].val = r - l + 1;
tr[p].tag = 1;
return;
}
pushdown操作也很类似。
void push_down(int p, int l, int r) {
if (tr[p].tag) {
tr[p].tag = 0;
int mid = (l + r) >> 1;
if (!tr[p].lson) tr[p].lson = ++tot;
tr[tr[p].lson].tag = 1;
tr[tr[p].lson].val = mid - l + 1;
if (!tr[p].rson) tr[p].rson = ++tot;
tr[tr[p].rson].tag = 1;
tr[tr[p].rson].val = r - mid;
}
}
之后我们就愉快地A了这道题。
不孩子你太天真了。
我们发现a，b还是太大，所以要动态开点。
好了这回不逗你了。。。
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 using namespace std;
5 struct Segment{
6 int lson, rson;//左孩子，右孩子
7 int val;//有多少被改过的数
8 int tag;//懒惰标记
9 }tr[1000010];
10 int rt, tot;
11 int n;
12 int ans;
13 struct node{
14 int a, b;
15 int k;
16 }ASUKA[40010];
17 void push_down(int p, int l, int r) {
18 if (tr[p].tag) {
19 tr[p].tag = 0;
20 int mid = (l + r) >> 1;
21 if (!tr[p].lson) tr[p].lson = ++tot;
22 tr[tr[p].lson].tag = 1;
23 tr[tr[p].lson].val = mid - l + 1;
24 if (!tr[p].rson) tr[p].rson = ++tot;
25 tr[tr[p].rson].tag = 1;
26 tr[tr[p].rson].val = r - mid;
27 }
28 }
29 void work(int &p, int l, int r, int x, int y, int k) {
30 if (!p) {
31 p = ++tot;
32 }
33 if (x <= l && r <= y) {
34 ans += (r - l + 1 - tr[p].val) * k;
35 tr[p].val = r - l + 1;
36 tr[p].tag = 1;
37 return;
38 }
39 push_down(p, l, r);
40 int mid = (l + r) >> 1;
41 if (x <= mid) work(tr[p].lson, l, mid, x, y, k);
42 if (y > mid) work(tr[p].rson, mid + 1, r, x, y, k);
43 tr[p].val = tr[tr[p].lson].val + tr[tr[p].rson].val;
44 }
45 bool cmp(node x, node y) {
46 return x.k > y.k;
47 }
48 int main() {
49 cin >> n;
50 for (int i = 1; i <= n; i++) {
51 cin >> ASUKA[i].a >> ASUKA[i].b >> ASUKA[i].k;
52 }
53 sort(ASUKA + 1, ASUKA + n + 1, cmp);
54 for (int i = 1; i <= n; i++) {
55 work(rt, 1, 1000000000, ASUKA[i].a, ASUKA[i].b - 1, ASUKA[i].k);
56 }
57 cout << ans;
58 return 0;
59 }
...
...
...
抄代码的肯定没A！
因为上面的代码没开longlong（(⊙o⊙)…）。
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 using namespace std;
5 typedef long long ll;
6 struct Segment{
7 int lson, rson;//左孩子，右孩子
8 ll val;//有多少被改过的数
9 int tag;//懒惰标记
10 }tr[1000010];
11 int rt, tot;
12 int n;
13 ll ans;
14 struct node{
15 int a, b;
16 ll k;
17 }ASUKA[40010];
18 void push_down(int p, int l, int r) {
19 if (tr[p].tag) {
20 tr[p].tag = 0;
21 int mid = (l + r) >> 1;
22 if (!tr[p].lson) tr[p].lson = ++tot;
23 tr[tr[p].lson].tag = 1;
24 tr[tr[p].lson].val = mid - l + 1;
25 if (!tr[p].rson) tr[p].rson = ++tot;
26 tr[tr[p].rson].tag = 1;
27 tr[tr[p].rson].val = r - mid;
28 }
29 }
30 void work(int &p, int l, int r, int x, int y, ll k) {
31 if (!p) {
32 p = ++tot;
33 }
34 if (x <= l && r <= y) {
35 ans += (r - l + 1 - tr[p].val) * k;
36 tr[p].val = r - l + 1;
37 tr[p].tag = 1;
38 return;
39 }
40 push_down(p, l, r);
41 int mid = (l + r) >> 1;
42 if (x <= mid) work(tr[p].lson, l, mid, x, y, k);
43 if (y > mid) work(tr[p].rson, mid + 1, r, x, y, k);
44 tr[p].val = tr[tr[p].lson].val + tr[tr[p].rson].val;
45 }
46 bool cmp(node x, node y) {
47 return x.k > y.k;
48 }
49 int main() {
50 cin >> n;
51 for (int i = 1; i <= n; i++) {
52 cin >> ASUKA[i].a >> ASUKA[i].b >> ASUKA[i].k;
53 }
54 sort(ASUKA + 1, ASUKA + n + 1, cmp);
55 for (int i = 1; i <= n; i++) {
56 work(rt, 1, 1000000000, ASUKA[i].a, ASUKA[i].b - 1, ASUKA[i].k);
57 }
58 cout << ans;
59 return 0;
60 }
View Code