首先说下我写的线段树吧。
我是按照线段树【完全版】那个人的写法来写的，因为网上大多数题解都是按照他的写法来写。
确实比较飘逸，所以就借用了。
节点大小是maxn是4倍，准确来说是大于maxn的2^x次方的最小值的两倍。
lson 和 rson 用宏定义写了。因为是固定的量。
线段树不必保存自身的区间，因为一边传递过去的时候，在函数里就有区间表示，无谓开多些无用的变量。
pushUp函数，更新当前节点cur的值，其实就是，线段树一般都是处理完左右孩子，然后再递归更新父亲的嘛，这个pushUp函数就是用来更新父亲的。感觉不用这个函数更加清楚明了。
pushDown函数，在lazy--upDate的时候有用，作用是把延迟标记更新到左右节点。
多次使用sum不用清0，add要。build的时候就会初始化sum数据。但其他用法就可能要
1 #define lson L, mid, cur << 1
2 #define rson mid + 1, R, cur << 1 | 1
3 void pushUp(int cur) {
4 sum[cur] = sum[cur << 1] + sum[cur << 1 | 1];
5 }
6 void pushDown(int cur, int total) {
7 if (add[cur]) {
8 add[cur << 1] += add[cur]; //传递去左右孩子
9 add[cur << 1 | 1] += add[cur]; // val >> 1 相当于 val / 2
10 sum[cur << 1] += add[cur] * (total - (total >> 1)); //左孩子有多少个节点
11 sum[cur << 1 | 1] += add[cur] * (total >> 1); //一共控制11个，则右孩子有5个
12 add[cur] = 0;
13 }
14 }
15 void build(int L, int R, int cur) {
16 if (L == R) {
17 sum[cur] = a[L];
18 return;
19 }
20 int mid = (L + R) >> 1;
21 build(lson);
22 build(rson);
23 pushUp(cur);
24 }
25 void upDate(int begin, int end, int val, int L, int R, int cur) {
26 if (L >= begin && R <= end) {
27 add[cur] += val;
28 sum[cur] += val * (R - L + 1); //这里加了一次，后面pushDown就只能用add[cur]的
29 return;
30 }
31 pushDown(cur, R - L + 1); //这个是必须的，因为下面的pushUp是直接等于的
32 //所以要先把加的，传递去右孩子，然后父亲又调用pushUp，才能保证正确性。
33 int mid = (L + R) >> 1; //一直分解的是大区间，开始时是[1, n]这个区间。
34 if (begin <= mid) upDate(begin, end, val, lson); //只要区间涉及，就必须更新
35 if (end > mid) upDate(begin, end, val, rson);
36 pushUp(cur);
37 }
38 int query(int begin, int end, int L, int R, int cur) {
39 if (L >= begin && R <= end) {
40 return sum[cur];
41 }
42 pushDown(cur, R - L + 1);
43 int ans = 0, mid = (L + R) >> 1;
44 if (begin <= mid) ans += query(begin, end, lson); //只要区间涉及，就必须查询
45 if (end > mid) ans += query(begin, end, rson);
46 return ans;
47
成段更新模板
关于成段更新时的upDate函数，中途的pushDown是不能省的，可以看看第三题然后结合我给的数据（数据是poj的大牛发出来的，不是我想的。）关键就在于pushUp函数是直接等于的，你不pushDown，然后pushUp，就会把以前的增加值给抹杀了
HDU 1166 敌兵布阵
单点更新，区间求和
http://acm.hdu.edu.cn/showproblem.php?pid=1166
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 50000 + 20;
int sum[maxn << 2];
int a[maxn];
void pushUp(int cur) { //更新当前这个节点的信息
sum[cur] = sum[cur << 1] + sum[cur << 1 | 1];
}
void build(int L, int R, int cur) {
if (L == R) {
sum[cur] = a[L];
return;
}
int mid = (L + R) >> 1;
build(lson);
build(rson);
pushUp(cur);
}
void upDate(int pos, int val, int L, int R, int cur) {
if (L == pos && R == pos) {
sum[cur] += val;
return;
}
int mid = (L + R) >> 1;
if (pos <= mid) upDate(pos, val, lson);
else upDate(pos, val, rson);
pushUp(cur);
}
int query(int begin, int end, int L, int R, int cur) { //[L, R]大区间, [begin, end]查询区间
if (L >= begin && R <= end) { //这个大区间是待查区间的子集
return sum[cur];
}
int mid = (L + R) >> 1;
int ans = 0;
if (begin <= mid) ans += query(begin, end, lson);
if (end > mid) ans += query(begin, end, rson);
return ans;
}
int f;
void work() {
printf("Case %d:\n", ++f);
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
build(1, n, 1);
char cmd[111];
while (scanf("%s", cmd) != EOF && cmd[0] != 'E') {
int a, b;
scanf("%d%d", &a, &b);
if (cmd[0] == 'Q') {
printf("%d\n", query(a, b, 1, n, 1));
} else if (cmd[0] == 'A') {
upDate(a, b, 1, n, 1);
} else {
upDate(a, -b, 1, n, 1);
}
}
return;
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d", &t);
while (t--) {
work();
}
return 0;
}
View Code
HDU 1754 I Hate It
单点更新，区间最值
http://acm.hdu.edu.cn/showproblem.php?pid=1754
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 200000 + 20;
int mx[maxn << 2];
int a[maxn];
void pushUp(int cur) {
mx[cur] = max(mx[cur << 1], mx[cur << 1 | 1]);
}
void build(int L, int R, int cur) {
if (L == R) {
mx[cur] = a[L]; //就是自己
return;
}
int mid = (L + R) >> 1;
build(lson);
build(rson);
pushUp(cur);
}
void upDate(int pos, int val, int L, int R, int cur) {
if (L == pos && R == pos) { //精确到这一个点
mx[cur] = val;
return;
}
int mid = (L + R) >> 1;
if (pos <= mid) upDate(pos, val, lson);
else upDate(pos, val, rson);
pushUp(cur);
}
int query(int begin, int end, int L, int R, int cur) {
if (L >= begin && R <= end) {
return mx[cur];
}
int mid = (L + R) >> 1;
int ans = 0;
if (begin <= mid) ans = query(begin, end, lson); //区间有涉及，级要查询
if (end > mid) ans = max(ans, query(begin, end, rson));
return ans;
}
int n, m;
void work() {
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
build(1, n, 1);
for (int i = 1; i <= m; ++i) {
char str[11];
int b, c;
scanf("%s%d%d", str, &b, &c);
if (str[0] == 'Q') {
printf("%d\n", query(b, c, 1, n, 1));
} else upDate(b, c, 1, n, 1);
}
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
while (scanf("%d%d", &n, &m) != EOF) {
work();
}
return 0;
}
View Code
POJ 3468 A Simple Problem with Integers
http://poj.org/problem?id=3468
成段更新，区间查询总和，这题记得用LL，
给个数据
10 22
1 2 3 4 5 6 7 8 9 10
Q 4 4
C 1 10 3
C 6 10 3
C 6 9 3
C 8 9 -100
C 7 9 3
C 7 10 3
C 1 10 3
Q 6 10
Q 6 9
Q 8 9
Q 7 9
Q 7 10
Q 1 10
Q 2 4
C 3 6 3
Q 9 9
Q 1 1
Q 5 5
Q 6 6
Q 7 7
Q 6 8
ans
4
-82
-104
-147
-122
-100
-37
27
-73
7
14
21
25
-28
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 100000 + 20;
LL sum[maxn << 2];
LL add[maxn << 2];
int a[maxn];
void pushUp(int cur) {
sum[cur] = sum[cur << 1] + sum[cur << 1 | 1];
}
void pushDown(int cur, int total) {
if (add[cur]) {
add[cur << 1] += add[cur];
add[cur << 1 | 1] += add[cur]; // val >> 1 相当于 val / 2
sum[cur << 1] += add[cur] * (total - (total >> 1)); //左孩子有多少个节点
sum[cur << 1 | 1] += add[cur] * (total >> 1); //一共控制11个，则右孩子有5个
add[cur] = 0;
}
}
void build(int L, int R, int cur) {
if (L == R) {
sum[cur] = a[L];
return;
}
int mid = (L + R) >> 1;
build(lson);
build(rson);
pushUp(cur);
}
void upDate(int begin, int end, LL val, int L, int R, int cur) {
if (L >= begin && R <= end) {
add[cur] += val;//这里加了一次，后面pushDown就只能用add[cur]的
sum[cur] += val * (R - L + 1); //控制的节点数目
return;
}
pushDown(cur, R - L + 1);
int mid = (L + R) >> 1;
if (begin <= mid) upDate(begin, end, val, lson);
if (end > mid) upDate(begin, end, val, rson);
pushUp(cur);
}
LL query(int begin, int end, int L, int R, int cur) {
if (L >= begin && R <= end) {
return sum[cur];
}
pushDown(cur, R - L + 1);
LL ans = 0, mid = (L + R) >> 1;
if (begin <= mid) ans += query(begin, end, lson);
if (end > mid) ans += query(begin, end, rson);
return ans;
}
void work() {
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
build(1, n, 1);
char str[11];
for (int i = 1; i <= q; ++i) {
scanf("%s", str);
int L, R, val;
if (str[0] == 'Q') {
scanf("%d%d", &L, &R);
printf("%I64d\n", query(L, R, 1, n, 1));
} else {
scanf("%d%d%d", &L, &R, &val);
upDate(L, R, val, 1, n, 1);
}
}
return;
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
work();
return 0;
}
View Code
HDU 1698 Just a Hook
http://acm.hdu.edu.cn/showproblem.php?pid=1698
线段树成段覆盖成一个值，然后求总和。
思路是：用线段树覆盖整一段的值，然后每次更新，也是延迟标记加速。不同的是：每次更新的时候，线段树节点覆盖的总和不是加上去而是直接等于，因为后面一段都变成了这个数字嘛。。前面的值就相当于没用了。。所以sum[1]就是答案
然后记得memset add
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 100000 + 20;
int add[maxn << 2];
int sum[maxn << 2];
void pushDown(int cur, int total) {
if (add[cur]) {
add[cur << 1] = add[cur];
add[cur << 1 | 1] = add[cur];
sum[cur << 1] = add[cur] * (total - (total >> 1));
sum[cur << 1 | 1] = add[cur] * (total >> 1);
add[cur] = 0;
}
}
void pushUp(int cur) {
sum[cur] = sum[cur << 1] + sum[cur << 1 | 1];
}
void upDate(int begin, int end, int val, int L, int R, int cur) {
if (L >= begin && R <= end) {
add[cur] = val;
sum[cur] = val * (R - L + 1);
return;
}
pushDown(cur, R - L + 1);
int mid = (L + R) >> 1;
if (begin <= mid) upDate(begin, end, val, lson);
if (end > mid) upDate(begin, end, val, rson);
pushUp(cur);
}
//int query(int begin, int end, int L, int R, int cur) {
// if (L >= begin && R <= end) {
// return sum[cur];
// }
// pushDown(cur, R - L + 1);
// int mid = (L + R) >> 1;
// int ans = 0;
//
//}
void build(int L, int R, int cur) {
if (L == R) {
sum[cur] = 1;
return;
}
int mid = (L + R) >> 1;
build(lson);
build(rson);
pushUp(cur);
}
int f;
void work() {
int n;
scanf("%d", &n);
build(1, n, 1);
// cout << sum[2] << endl;
int m;
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
int L, R, val;
scanf("%d%d%d", &L, &R, &val);
upDate(L, R, val, 1, n, 1);
// cout << L << " " << R << " " << val << endl;
// cout << sum[3] << endl;
}
printf("Case %d: The total value of the hook is %d.\n", ++f, sum[1]);
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
cin >> t;
while (t--) {
work();
memset(add, 0, sizeof add);
}
return 0;
}
View Code
可以用a[cur]表示这个 节点所保存的相同值的总和。就是a[cur]保存的是它所维护的区间，数字都是val这一个的总和。
然后query一下即可。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 100000 + 20;
int a[maxn << 2];
void pushDown(int cur, int total) {
if (a[cur]) {
a[cur << 1] = (total - (total >> 1)) * (a[cur] / total);
a[cur << 1 | 1] = (total >> 1) * (a[cur] / total);
a[cur] = 0;
}
}
void upDate(int begin, int end, int val, int L, int R, int cur) {
if (L >= begin && R <= end) {
a[cur] = (R - L + 1) * val;
return;
}
pushDown(cur, R - L + 1);
int mid = (L + R) >> 1;
if (begin <= mid) upDate(begin, end, val, lson);
if (end > mid) upDate(begin, end, val, rson);
}
int query(int L, int R, int cur) {
if (a[cur]) {
return a[cur];
}
if (L == R) {
while (1);
return 0;
}
int mid = (L + R) >> 1;
int ans = query(lson) + query(rson);
return ans;
}
int f;
void work() {
int n, q;
cin >> n >> q;
a[1] = n;
for (int i = 1; i <= q; ++i) {
int L, R, val;
scanf("%d%d%d", &L, &R, &val);
upDate(L, R, val, 1, n, 1);
}
printf("Case %d: The total value of the hook is %d.\n", ++f, query(1, n, 1));
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d", &t);
while (t--) {
work();
}
return 0;
}
View Code
POJ 2528 Mayor's posters
http://poj.org/problem?id=2528
离散化。
一开始就知道要离散化的了，但觉得离散化后保证不了答案的正确性呀？（其实是还没懂的什么叫离散化）
可以这样去想。如果[L1, R1]和[L2, R2]已知，那么，同时放大或者缩小若干倍，是不影响其相交性的。
比如[1, 6]和[3, 7]离散后[1, 3]和[2, 4]，一样是这样的相交。只不过露出来的部分确实少了点，但是不影响我们的答案。
所以可以离散化后线段树搞一搞。也是区间成段替换的题目。
离散的时候 有bug
[1, 10]
[1, 4]
[6, 10] 的话。直接离散是错误的。这个ans应该是3.
但是直接离散后，[1, 4] [1, 2] [3,4]使得ans = 2；
是因为忽略了5这样的错误。解决方法就是如果数字隔开了，补上一个数字，这样离散后就不会挨着了。
线段树思路：用seg[cur]表示cur这个节点控制的区间的值。就是seg[1] = val表示[1, n]这段区间的值都是val
然后直接pushDown即可，pushUp就不用了。（传递下去后可以把当前的清空了）
每次询问，hash一下这个值有没出现过就行。每次判断玩后，直接return了，不要找它儿子了。因为可能后来延迟标记的没延迟标记下去。不然就pushdown一下
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 10 * 10000 + 20;
int all[maxn];
int L[maxn];
int R[maxn];
set<int>number;
int seg[maxn << 2];
void pushDown(int cur) {
if (seg[cur]) {
seg[cur << 1] = seg[cur << 1 | 1] = seg[cur];
seg[cur] = 0;
}
}
void upDate(int begin, int end, int val, int L, int R, int cur) {
if (L >= begin && R <= end) {
seg[cur] = val;
return;
}
pushDown(cur);
int mid = (L + R) >> 1;
if (begin <= mid) upDate(begin, end, val, lson);
if (end > mid) upDate(begin, end, val, rson);
}
bool hash[maxn];
int ans;
void query(int L, int R, int cur) {
if (seg[cur]) {
if (!hash[seg[cur]]) {
hash[seg[cur]] = 1;
ans++;
}
// return;
}
pushDown(cur); //不return就pushDown
if (L == R) return;
int mid = (L + R) >> 1;
query(lson);
query(rson);
}
void work() {
int n;
scanf("%d", &n);
number.clear();
memset(seg, 0, sizeof seg);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &L[i], &R[i]);
number.insert(L[i]);
number.insert(R[i]);
}
int lenall = 0;
for (set<int> :: iterator it = number.begin(); it != number.end(); ++it) {
all[++lenall] = *it; //去重
}
int t = lenall;
for (int i = 2; i <= t; ++i) {
if (all[i] != all[i - 1] + 1) {
all[++lenall] = all[i - 1] + 1;
}
}
sort(all + 1, all + 1 + lenall);
for (int i = 1; i <= n; ++i) {
int begin = lower_bound(all + 1, all + 1 + lenall, L[i]) - all;
int end = lower_bound(all + 1, all + 1 + lenall, R[i]) - all;
upDate(begin, end, i, 1, lenall, 1);
}
ans = 0;
memset(hash, 0, sizeof hash);
query(1, lenall, 1);
cout << ans << endl;
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return 0;
}
View Code
HDU 4027
Can you answer these queries?
http://acm.hdu.edu.cn/showproblem.php?pid=4027
有一个很明显的道理就是如果那个开放数是1了，其实就没必要开放了。
同样是用sum[cur]表示这个节点控制的总和。然后用个book[cur]表示这个节点控制的区间的值是否全部是1.
由于开放不超7次就会变成1了。所以可以暴力单点更新。然后把book[cur]传递上去就行。
book[cur]为1（不用更新了）的前提是左右儿子都不用更新。还有叶子节点是不会pushUp的（return了），以前理解错误。
注意一个坑爹点，就是L可能大于R
sum不用清0，因为每次都重新输入值了，而且不用考虑叶子节点后面的节点，用不上的。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 100000 + 20;
LL sum[maxn << 2];
bool book[maxn << 2];//查看是否还有更新的必要
int n;
void pushUp(int cur) {
sum[cur] = sum[cur << 1] + sum[cur << 1 | 1];
book[cur] = book[cur << 1] && book[cur << 1 | 1]; //左右孩子都不用更新了，就不更新了
}
void build(int L, int R, int cur) {
if (L == R) {
scanf("%I64d", &sum[cur]);
return;
}
int mid = (L + R) >> 1;
build(lson);
build(rson);
pushUp(cur);
}
void upDate(int begin, int end, int L, int R, int cur) {
if (L == R) { //暴力单点更新
sum[cur] = (LL)sqrt(sum[cur] * 1.0);
if (sum[cur] == 1) { //已经等于1就不用更新了
book[cur] = 1;
}
return;
}
int mid = (L + R) >> 1;
if (begin <= mid && !book[cur << 1]) upDate(begin, end, lson);
if (end > mid && !book[cur << 1 | 1]) upDate(begin, end, rson);
pushUp(cur);
}
LL query(int begin, int end, int L, int R, int cur) {
if (L >= begin && R <= end) {
return sum[cur];
}
int mid = (L + R) >> 1;
LL ans = 0;
if (begin <= mid) ans += query(begin, end, lson);
if (end > mid) ans += query(begin, end, rson);
return ans;
}
int f;
void work() {
printf("Case #%d:\n", ++f);
build(1, n, 1);
int m;
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
int flag, L, R;
scanf("%d%d%d", &flag, &L, &R);
if (L > R) swap(L, R); //注意这个特别坑
if (flag == 0) {
upDate(L, R, 1, n, 1);
} else {
printf("%I64d\n", query(L, R, 1, n, 1));
}
}
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
while (scanf("%d", &n) != EOF) {
work();
memset(book, 0, sizeof book);
printf("\n");
}
return 0;
}
View Code
线段树的区间合并
HDU 1540 Tunnel Warfare
http://acm.hdu.edu.cn/showproblem.php?pid=1540
点单更新，区间查询
对于一个数组[1, n]有三种操作，
1、可以删除一个元素，这样连续区间就会减小。
2、恢复上一次删除的那个元素。
3、给定一个位置pos，求出其最大的连续区间。
思路：查询的时候，就是这个点pos的左边连续最大 + 右边连续最大。（有一点分治的思想）
然后用2颗线段树维护。分别是LtoRsum[cur]表示，对于第cur个节点，其左端点，向右能延伸的最长距离。
就是假如这个节点维护的是区间[L, R]，那么LtoRsum[cur]就表示从L开始，向右边最多能延伸的区间。
同理，RtoLsum[cur]就是这个区间的右端点，向左延伸的区间。
那么ans = [1, pos]中向左延伸的区间 + [pos, n]中向右延续的区间。
对于每次的pushUp。其思路就是，假如是LtoRsum[cur]，先要满足其左孩子的值，如果左孩子丰满，才能加上右孩子的值。因为这样这个区间才是连续的。
具体看看代码模拟一下吧~~
恢复 and 删除那个。可以用0表示删除了，1表示没删除。单点更新即可、
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define root 1, n, 1
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 50000 + 20;
int LtoRsum[maxn << 2];
int RtoLsum[maxn << 2];
bool book[maxn];
void build(int L, int R, int cur) {
LtoRsum[cur] = RtoLsum[cur] = R - L + 1;
if (L == R) return;
int mid = (L + R) >> 1;
build(lson);
build(rson);
}
void pushUp(int cur, int total) {
LtoRsum[cur] = LtoRsum[cur << 1];
RtoLsum[cur] = RtoLsum[cur << 1 | 1];
if (LtoRsum[cur] == (total - (total >> 1))) { //如果左孩子都丰满了，就可以接着合并右孩子的值
LtoRsum[cur] += LtoRsum[cur << 1 | 1];
}
if (RtoLsum[cur] == (total >> 1)) {
RtoLsum[cur] += RtoLsum[cur << 1];
}
}
void upDate(int pos, int val, int L, int R, int cur) { //单点更新
if (L == R) {
LtoRsum[cur] = RtoLsum[cur] = val;
return;
}
int mid = (L + R) >> 1;
if (pos <= mid) upDate(pos, val, lson);
else upDate(pos, val, rson);
pushUp(cur, R - L + 1);
}
int queryLtoRsum(int begin, int end, int L, int R, int cur) {
if (L >= begin && R <= end) return LtoRsum[cur];
int mid = (L + R) >> 1, lans = -inf, rans = -inf;
if (begin <= mid) lans = queryLtoRsum(begin, end, lson);
if (end > mid) rans = queryLtoRsum(begin, end, rson);
if (end <= mid) return lans; //只有左孩子
if (begin > mid) return rans;
if (lans == mid - begin + 1) return lans + rans;
//就是[begin, end]这个区间，的左孩子能够去到中间和右孩子汇合。
return lans;
}
int queryRtoLsum(int begin, int end, int L, int R, int cur) {
if (L >= begin && R <= end) return RtoLsum[cur];
int mid = (L + R) >> 1, lans = -inf, rans = -inf;
if (begin <= mid) lans = queryRtoLsum(begin, end, lson);
if (end > mid) rans = queryRtoLsum(begin, end, rson);
if (begin > mid) return rans;
if (end <= mid) return lans; //只有左孩子
if (rans == end - mid) return rans + lans; //本来右孩子就少了一个
return rans;
}
int n, m;
int stack[maxn];
int top;
void work() {
top = 0;
build(root);
// cout << RtoLsum[14] << endl;
// int a = 4;
// int ans = queryLtoRsum(a, n, 1, n, 1) + queryRtoLsum(1, a, 1, n, 1);
// printf("%d***\n", queryLtoRsum(a, n, 1, n, 1) );
// printf("%d***\n", queryRtoLsum(1, a, 1, n, 1) );
for (int i = 1; i <= m; ++i) {
char str[22];
int a;
scanf("%s", str);
if (str[0] == 'D') {
scanf("%d", &a);
stack[++top] = a;
upDate(a, 0, root);
} else if (str[0] == 'R') {
upDate(stack[top], 1, root);
--top;
} else {
scanf("%d", &a);
int ans = queryLtoRsum(a, n, root) + queryRtoLsum(1, a, root);
printf("%d\n", ans == 0 ? 0 : ans - 1);
}
}
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
while (scanf("%d%d", &n, &m) != EOF) work();
return 0;
}
View Code
上一题的升级版 POJ 3667 Hotel
http://poj.org/problem?id=3667
有两种操作，
1、查找第一个具有连续val个空位的点，就是找出第一个[L, L + val - 1]是空位的。然后占据，不存在输出0
2、占据[L, R]这段位置。
思路：对于2这样的操作，可以用lazy-update来做，和以前的区间覆盖一段数值是一样的。
关键是如何找出第一个位置，具有连续val个空位的。
用以前的那种暴力查找每个位置的值，显然就超时了。
考虑用一个sum[cur]表示这个节点所维护的区间的“最长连续空位置数目”
那么先判断总区间是否 > val，没有则直接是0了。
那么
1、如果左孩子有 > val个数目，则优先去找左孩子
2、如果是中间有 > val个数目，就是两个区间合并起来，连续数目 > val的，那么起点可以找出来了，就是mid - RtoLsum[cur << 1] + 1
3、去找右孩子
左孩子右端点向左，连续的最大数目。可以画图理解。
那么现在关键是怎么解出这个sum[cur]了，来源是三部分，第一是max(sum[cur << 1], sum[cur << 1 | 1])这个好理解，就是左右孩子能维护多少，就能更新到父亲那里去。然后关键就是有一部分是中间区间合并的，这段和就是RtoLsum[cur << 1] + LtoRsum[cur << 1 | 1]，左孩子的右端点向左连续的个数 ＋ 右孩子左端点向右连续的个数。这里不需要减去１，因为他们各自维护的区间是独立的，不会相交，不存在有一个数字相加了２次的情况。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define root 1, n, 1
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 50000 + 20;
int n, m;
int LtoRsum[maxn << 2];
int RtoLsum[maxn << 2];
int add[maxn << 2];
int sum[maxn << 2];
void build(int L, int R, int cur) {
sum[cur] = LtoRsum[cur] = RtoLsum[cur] = R - L + 1;
if (L == R) return;
int mid = (L + R) >> 1;
build(lson);
build(rson);
}
void pushDown(int cur, int total) {
if (add[cur] != -1) {
add[cur << 1] = add[cur << 1 | 1] = add[cur];
if (add[cur]) {
sum[cur << 1] = LtoRsum[cur << 1] = RtoLsum[cur << 1] = (total - (total >> 1));
sum[cur << 1 | 1] = LtoRsum[cur << 1 | 1] = RtoLsum[cur << 1 | 1] = (total >> 1);
} else {
sum[cur << 1] = LtoRsum[cur << 1] = LtoRsum[cur << 1 | 1] = 0;
sum[cur << 1 | 1] = RtoLsum[cur << 1] = RtoLsum[cur << 1 | 1] = 0;
}
add[cur] = -1;
}
}
void pushUp(int cur, int total) {
LtoRsum[cur] = LtoRsum[cur << 1];
RtoLsum[cur] = RtoLsum[cur << 1 | 1];
if (LtoRsum[cur] == (total - (total >> 1))) LtoRsum[cur] += LtoRsum[cur << 1 | 1];
if (RtoLsum[cur] == (total >> 1)) RtoLsum[cur] += RtoLsum[cur << 1];
sum[cur] = max(max(sum[cur << 1], sum[cur << 1 | 1]), LtoRsum[cur << 1 | 1] + RtoLsum[cur << 1]);//区间相互独立，没交集，不用减去1
}
void upDate(int begin, int end, int val, int L, int R, int cur) {
if (L >= begin && R <= end) {
if (val) {
sum[cur] = LtoRsum[cur] = RtoLsum[cur] = R - L + 1;
} else sum[cur] = LtoRsum[cur] = RtoLsum[cur] = 0;
add[cur] = val;
return;
}
int mid = (L + R) >> 1;
pushDown(cur, R - L + 1);
if (begin <= mid) upDate(begin, end, val, lson);
if (end > mid) upDate(begin, end, val, rson);
pushUp(cur, R - L + 1);
}
//int queryLtoRsum(int begin, int end, int L, int R, int cur) {
// if (L >= begin && R <= end) return LtoRsum[cur];
// pushDown(cur, R - L + 1);
// int mid = (R + L) >> 1, lans = -inf, rans = -inf;
// if (begin <= mid) lans = queryLtoRsum(begin, end, lson);
// if (end > mid) rans = queryLtoRsum(begin, end, rson);
//
// if (end <= mid) return lans;
// if (begin > mid) return rans;
// if (lans == mid - begin + 1) return lans + rans;
// return lans;
//// printf("fff\n");
//// while (1);
//}
//int queryRtoLsum(int begin, int end, int L, int R, int cur) {
// if (L >= begin && R <= end) return RtoLsum[cur];
// pushDown(cur, R - L + 1);
// int mid = (L + R) >> 1, lans = -inf, rans = -inf;
// if (begin <= mid) lans = queryRtoLsum(begin, end, lson);
// if (end > mid) rans = queryRtoLsum(begin, end, rson);
//
// if (begin > mid) return rans;
// if (end <= mid) return lans;
// if (rans == end - mid) return rans + lans;
// return rans;
//}
//int calc(int a) {
// return queryLtoRsum(a, n, root) + queryRtoLsum(1, a, root);
//}
int query(int val, int L, int R, int cur) {
// if (L == R) return L;
pushDown(cur, R - L + 1);
int mid = (L + R) >> 1;
if (sum[cur << 1] >= val) return query(val, lson); //优先左孩子
else if (LtoRsum[cur << 1 | 1] + RtoLsum[cur << 1] >= val) return mid - RtoLsum[cur << 1] + 1;
else return query(val, rson);
}
void work() {
memset(add, -1, sizeof add);
cin >> n >> m;
build(root);
// int a = 7;
// upDate(a, a, 0, root);
// int ans = queryLtoRsum(a, n, root) + queryRtoLsum(1, a, root);
// cout << ans - 1 << endl;
for (int i = 1; i <= m; ++i) {
int flag, a, b;
scanf("%d", &flag);
if (flag == 1) {
scanf("%d", &a);
if (sum[1] < a) {
printf("0\n");
} else {
int pos = query(a, root);
printf("%d\n", pos);
upDate(pos, pos + a - 1, 0, root);
}
} else {
scanf("%d%d", &a, &b);
upDate(a, min(a + b - 1, n), 1, root);
}
}
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
work();
return 0;
}
View Code
HDU 3974 Assign the task
http://acm.hdu.edu.cn/showproblem.php?pid=3974
给定一颗树，要求对这颗树进行染色，（类似思路）
操作
1、把节点x和其所有下属节点都染成y
2、查询x是什么颜色。
首先，对于一颗树，是不好处理的，要映射到一维数组，所以考虑dfs序，Lcur[i]和Rcur[i]，表示这个节点在dfs的时候什么时候被访问到和什么时候退出访问。那么它映射到一维数组就是一个区间[Lcur[i], Rcur[i]]，然后就是简单的线段树区间替换了
用sum[cur]表示这个节点所维护的区间的值，是否相同，不相同，就是-2，相同就是那个val，因为一开始什么任务都没有，所以就全部设置成-1,更新即可
bug点：记得所有区间都要用Lcur[]和Rcur[]表达，相当于映射到哪里去了。当时就是query的时候没用Lcur[a] 。一直wa
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define root 1, n, 1
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 50000 + 20;
int add[maxn << 2];
int sum[maxn << 2];
int Lcur[maxn];
int Rcur[maxn];
int first[maxn];
bool in[maxn];
struct node {
int u, v, toNext;
}e[maxn << 2];
int num, index;
void addEdge(int u, int v) {
++num;
e[num].u = u;
e[num].v = v;
e[num].toNext = first[u];
first[u] = num;
}
void dfs(int cur) {
Lcur[cur] = ++index;
for (int i = first[cur]; i; i = e[i].toNext) {
dfs(e[i].v);
}
Rcur[cur] = index;
}
void build(int L, int R, int cur) {
sum[cur] = -1;
if (L == R) return;
int mid = (L + R) >> 1;
build(lson);
build(rson);
}
void pushDown(int cur) {
if (add[cur] != -1) {
add[cur << 1] = add[cur << 1 | 1] = add[cur];
sum[cur] = sum[cur << 1] = sum[cur << 1 | 1] = add[cur];
add[cur] = -1;
}
}
void pushUp(int cur) {
if (sum[cur << 1] == sum[cur << 1 | 1]) sum[cur] = sum[cur << 1];
else sum[cur] = -2;
}
void upDate(int begin, int end, int val, int L, int R, int cur) {
if (L >= begin && R <= end) {
sum[cur] = val;
add[cur] = val;
return;
}
pushDown(cur);
int mid = (L + R) >> 1;
if (begin <= mid) upDate(begin, end, val, lson);
if (end > mid) upDate(begin, end, val, rson);
pushUp(cur);
}
int query(int pos, int L, int R, int cur) {
if (sum[cur] != -2) return sum[cur];
pushDown(cur);
int mid = (L + R) >> 1;
if (pos <= mid) return query(pos, lson);
else return query(pos, rson);
}
int f;
void work() {
num = index = 0;
memset(first, 0, sizeof first);
memset(in, 0, sizeof in);
memset(add, -1, sizeof add);
printf("Case #%d:\n", ++f);
int n;
scanf("%d", &n);
for (int i = 1; i <= n - 1; ++i) {
int u, v;
scanf("%d%d", &v, &u);
addEdge(u, v);
in[v] = 1;
}
for (int i = 1; i <= n; ++i) {
if (in[i] == 0) {
dfs(i);
break;
}
}
// for (int i = 1; i <= n; ++i) {
// printf("%d %d\n", L[i], R[i]);
// }
build(root);
int m;
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
char op[11];
int a, b;
scanf("%s", op);
if (op[0] == 'C') {
scanf("%d", &a);
printf("%d\n", query(Lcur[a], root));
} else {
scanf("%d%d", &a, &b);
upDate(Lcur[a], Rcur[a], b, root);
}
}
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return 0;
}
View Code
HDU 4578
Transformation
超级恶心的线段树
http://acm.hdu.edu.cn/showproblem.php?pid=4578
要维护操作区间增加，覆盖，乘上一个数字。然后查询区间1次方和，2次方和，3次方和。
首先可以考虑一下把1次方和，2次方和，3次方和分三个线段树来维护。
pushUp是最简单的，也就是左右儿子加起来。
但是每次增加一个数字时，2次方和会增加多少呢？
设本来是[a1, a2, a3......an]，sum2 = a1^2 + a2^2 + ... + an^2。那么加上一个数字后，就会变成sum2 = (a1 + val)^2 + (a2 + val)^2 + .....+(an + val)^2。所以这样可以拆开来。变成本来的sum2 + 2 * val * (a1 + a2 + .... + an) + total * val * val。（total是区间大小）。所以这样就可以lazy--update了
三次方和同理。覆盖和乘上一个数字更加简单。
但是有问题，考虑下本来区间就已经需要加上一个数字的了（因为lazy--update的缘故，还没传递下去）。那么现在再在这个区间上乘上一个数字，那么你后来向下传递下去的add就应该是本来的val * add倍了。
（这就提示我们，在pushDown的时候，顺序是先pushdown相同，再乘法，再加法）
1、因为有相同的话，可以把乘法和加法都变成0了。
2、先传递乘法，免得传递加法后，再传递乘法再次把加法的add变成val * add倍
一定要注意细节，add操作那里，取模的时候一定要小心，看看有没地方没有及时取模，还有query的时候，左孩子+右孩子后，也是要去摸
可能要把val * val * val % MOD用个变量来保存一下，我不知道为什么不用变量保存会wa
还有long long int 确实比int快，可以把我的myTypec改成LL试一试
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#define root 1, n, 1
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
typedef int myTypec;
int n, m;
const int maxn = 200000 + 20;
const int MOD = 10007;
myTypec sum1[maxn << 2], sum2[maxn << 2], sum3[maxn << 2];
myTypec add[maxn << 2], mult[maxn << 2], same[maxn << 2];
void build(int L, int R, int cur) {
sum1[cur] = sum2[cur] = sum3[cur] = 0;
add[cur] = mult[cur] = same[cur] = 0;
if (L == R) return;
int mid = (L + R) >> 1;
build(lson);
build(rson);
}
void pushUp(int cur) {
sum1[cur] = (sum1[cur << 1] + sum1[cur << 1 | 1]) % MOD;
sum2[cur] = (sum2[cur << 1] + sum2[cur << 1 | 1]) % MOD;
sum3[cur] = (sum3[cur << 1] + sum3[cur << 1 | 1]) % MOD;
}
myTypec sum11;
myTypec sum22;
myTypec sum33;
void Toadd(int cur, int val, int total) {
sum11 = sum1[cur];
sum22 = sum2[cur];
sum1[cur] += (total * val) % MOD;
sum1[cur] %= MOD;
myTypec temp = val * val % MOD;
sum2[cur] += ((2 * val * sum11) % MOD + (total * temp) % MOD) %MOD;
sum2[cur] %= MOD;
myTypec liu = temp;
temp = temp * val % MOD;
sum3[cur] += ((3 * sum22 * val) % MOD + (3 * liu * sum11) % MOD + (total * temp) % MOD) % MOD;
sum3[cur] %= MOD;
add[cur] += val;
add[cur] %= MOD;
}
void ToMult(int cur, int val, int total) {
sum11 = sum1[cur];
sum22 = sum2[cur];
sum1[cur] *= val;
sum1[cur] %= MOD;
myTypec temp = val * val % MOD;
sum2[cur] *= temp;
sum2[cur] %= MOD;
temp = temp * val % MOD;
sum3[cur] *= temp;
sum3[cur] %= MOD;
if (mult[cur]) {
mult[cur] *= val;
mult[cur] %= MOD;
} else mult[cur] = val;
add[cur] = add[cur] * val % MOD;
}
void ToSame(int cur, int val, int total) {
same[cur] = val;
add[cur] = mult[cur] = 0;
sum1[cur] = total * val % MOD;
myTypec temp = val * val % MOD;
sum2[cur] = total * temp % MOD;
temp = temp * val % MOD;
sum3[cur] = total * temp % MOD;
}
void pushDown(int cur, int total) {
if (same[cur]) {
ToSame(cur << 1, same[cur], total - (total >> 1));
ToSame(cur << 1 | 1, same[cur], total >> 1);
same[cur] = 0;
}
if (mult[cur]) {
ToMult(cur << 1, mult[cur], total - (total >> 1));
ToMult(cur << 1 | 1, mult[cur], total >> 1);
mult[cur] = 0;
}
if (add[cur]) {
Toadd(cur << 1, add[cur], total - (total >> 1));
Toadd(cur << 1 | 1, add[cur], total >> 1);
add[cur] = 0;
}
}
void upDate(int begin, int end, int val, int L, int R, int cur, int flag) {
if (L >= begin && R <= end) {
if (flag == 1) { //加上一个数
Toadd(cur, val, R - L + 1);
} else if (flag == 2) { //乘上一个数
ToMult(cur, val, R - L + 1);
} else if (flag == 3) {
ToSame(cur, val, R - L + 1);
}
// while(1);
return;
}
pushDown(cur, R - L + 1);
int mid = (L + R) >> 1;
if (begin <= mid) upDate(begin, end, val, lson, flag);
if (end > mid) upDate(begin, end, val, rson, flag);
pushUp(cur);
}
myTypec query(int begin, int end, int L, int R, int cur, int p) {
if (L >= begin && R <= end) {
if (p == 1) return sum1[cur];
if (p == 2) return sum2[cur];
if (p == 3) return sum3[cur];
while(1);
}
pushDown(cur, R - L + 1);
int mid = (L + R) >> 1;
myTypec ans = 0;
if (begin <= mid) {
ans += query(begin, end, lson, p);
ans %= MOD;
}
if (end > mid) {
ans += query(begin, end, rson, p);
ans %= MOD;
}
return ans % MOD;
}
void work() {
build(root);
for (int i = 1; i <= m; ++i) {
int flag, L, R, val;
cin >> flag >> L >> R >> val;
if (L > R) swap(L, R);
if (flag != 4) {
upDate(L, R, val, root, flag);
} else {
cout << query(L, R, root, val) << endl;
}
}
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
IOS;
while (cin >> n >> m) {
if (n == 0 && m == 0) break;
work();
}
return 0;
}
View Code
HDU 4614 二分 + 线段树
Vases and Flowers
http://acm.hdu.edu.cn/showproblem.php?pid=4614
两种操作，
1、区间替换，输出成功替换的个数
2、输出从a开始，大小为b的空白区间（不一定要连续），输出起始位置和终止位置，然后把这段区间标记为已占据。
注意，如果从a开始没有空白区间，输出那段话，如果有，就覆盖min(区间大小， b)，多余的b是扔掉的。
明显可以用线段树维护区间空白个数的值，1表示空白，0表示占据，因为这方便我lazy--update
然后每次询问有没b个空白区间，就是从[a, n - 1]中找有多少个空白区间，然后因为它要最靠近a的，b个
可以在[a, n - 1]中进行二分，先确定R，使得[a, R]的空白区间是b个的。然后因为a可能已经是被占据了的，所以继续二分，确定L
PS:那个"[pre]"是没用的，不用管
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define root 0, n - 1, 1
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 50001 + 20;
int n, m;
int sum[maxn << 2], add[maxn << 2];
void build(int L, int R, int cur) {
sum[cur] = R - L + 1;
add[cur] = -1;
if (L == R) return;
int mid = (L + R) >> 1;
build(lson);
build(rson);
}
void pushDown(int cur, int total) {
if (add[cur] != -1) {
add[cur << 1] = add[cur << 1 | 1] = add[cur];
sum[cur << 1] = (total - (total >> 1)) * add[cur];
sum[cur << 1 | 1] = (total >> 1) * add[cur];
add[cur] = -1;
}
}
void pushUp(int cur) {
sum[cur] = sum[cur << 1] + sum[cur << 1 | 1];
}
void upDate(int begin, int end, int val, int L, int R, int cur) {
if (L >= begin && R <= end) {
sum[cur] = (R - L + 1) * val;
add[cur] = val;
return;
}
pushDown(cur, R - L + 1);
int mid = (L + R) >> 1;
if (begin <= mid) upDate(begin, end, val, lson);
if (end > mid) upDate(begin, end, val, rson);
pushUp(cur);
}
int query(int begin, int end, int L, int R, int cur) {
if (L >= begin && R <= end) return sum[cur];
pushDown(cur, R - L + 1);
int mid = (L + R) >> 1;
int ans = 0;
if (begin <= mid) ans += query(begin, end, lson);
if (end > mid) ans += query(begin, end, rson);
return ans;
}
void bin_find(int a, int b, int toFindVal) { //a是起点[a, n - 1]
int L = a, R = inf;
int begin = a, end = n - 1;
while (begin <= end) {
int mid = (begin + end) >> 1;
if (query(L, mid, root) >= toFindVal) {
R = mid;
end = mid - 1;
} else begin = mid + 1;
}
begin = a;
end = R;
while (begin <= end) {
int mid = (begin + end) >> 1;
if (query(mid, R, root) >= toFindVal) {
L = mid;
begin = mid + 1;
} else end = mid - 1;
}
printf("%d %d\n", L, R);
upDate(L, R, 0, root);
}
void work() {
scanf("%d%d", &n, &m);
build(root);
for (int i = 1; i <= m; ++i) {
int flag, a, b;
scanf("%d%d%d", &flag, &a, &b);
if (flag == 1) {
int ans = query(a, n - 1, root);
if (ans == 0) {
printf("Can not put any one.\n");
} else {
bin_find(a, b, min(ans, b)); //同时update了
}
} else {
if (a > b) swap(a, b);
int ans = b - a + 1 - query(a, b, root);
printf("%d\n", ans);
upDate(a, b, 1, root);
}
}
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d", &t);
while (t--) {
work();
printf("\n");
}
return 0;
}
View Code
hdu 4553
约会安排
http://acm.hdu.edu.cn/showproblem.php?pid=4553
和 POJ 3667 Hotel 一样的。
维护两个线段树，NS的先从sumOne（就是屌丝的）去找。然后占据，占据的时候同时更新女神的。就这样。看看Hotel那题的思路，就知道了。
刚开始的时候pushDownTwo少了一句话。wa到我傻逼一样。。委屈啊。
然后从Hotel那题试出来是pushDownTwo错误了，也是一件快乐的事情~
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 #define IOS ios::sync_with_stdio(false)
7 using namespace std;
8 #define inf (0x3f3f3f3f)
9 typedef long long int LL;
10
11 #include <iostream>
12 #include <sstream>
13 #include <vector>
14 #include <set>
15 #include <map>
16 #include <queue>
17 #include <string>
18 #define root 1, n, 1
19 #define lson L, mid, cur << 1
20 #define rson mid + 1, R, cur << 1 | 1
21 const int maxn = 2 * 100000 + 20;
22 struct node {
23 int LtoRsum, RtoLsum;
24 int add;
25 int sum;
26 } sumOne[maxn << 2], sumTwo[maxn << 2];
27 void build(int L, int R, int cur) {
28 sumOne[cur].LtoRsum = sumOne[cur].RtoLsum = sumOne[cur].sum = R - L + 1;
29 sumTwo[cur].LtoRsum = sumTwo[cur].RtoLsum = sumTwo[cur].sum = R - L + 1;
30 sumOne[cur].add = sumTwo[cur].add = -1;
31 if (L == R) return;
32 int mid = (L + R) >> 1;
33 build(lson);
34 build(rson);
35 }
36 void pushDownOne(int cur, int total) {
37 if (sumOne[cur].add != -1) {
38 sumOne[cur << 1].add = sumOne[cur << 1 | 1].add = sumOne[cur].add;
39 if (sumOne[cur].add) {
40 sumOne[cur << 1].LtoRsum = sumOne[cur << 1].RtoLsum = sumOne[cur << 1].sum = 0;
41 sumOne[cur << 1 | 1].LtoRsum = sumOne[cur << 1 | 1].RtoLsum = sumOne[cur << 1 | 1].sum = 0;
42 } else {
43 sumOne[cur << 1].LtoRsum = sumOne[cur << 1].RtoLsum = sumOne[cur << 1].sum = total - (total >> 1);
44 sumOne[cur << 1 | 1].LtoRsum = sumOne[cur << 1 | 1].RtoLsum = sumOne[cur << 1 | 1].sum = (total >> 1);
45 }
46 sumOne[cur].add = -1;
47 }
48 }
49 void pushUpOne(int cur, int total) {
50 sumOne[cur].LtoRsum = sumOne[cur << 1].LtoRsum;
51 sumOne[cur].RtoLsum = sumOne[cur << 1 | 1].RtoLsum;
52 if (sumOne[cur].LtoRsum == (total - (total >> 1))) sumOne[cur].LtoRsum += sumOne[cur << 1 | 1].LtoRsum;
53 if (sumOne[cur].RtoLsum == (total >> 1)) sumOne[cur].RtoLsum += sumOne[cur << 1].RtoLsum;
54 sumOne[cur].sum = max(sumOne[cur << 1].sum, sumOne[cur << 1 | 1].sum);
55 sumOne[cur].sum = max(sumOne[cur].sum, sumOne[cur << 1].RtoLsum + sumOne[cur << 1 | 1].LtoRsum);
56 }
57 void upDateOne(int begin, int end, int val, int L, int R, int cur) {
58 if (L >= begin && R <= end) {
59 if (val) {
60 sumOne[cur].sum = sumOne[cur].LtoRsum = sumOne[cur].RtoLsum = 0;
61 } else sumOne[cur].sum = sumOne[cur].LtoRsum = sumOne[cur].RtoLsum = R - L + 1;
62 sumOne[cur].add = val;
63 return;
64 }
65 pushDownOne(cur, R - L + 1);
66 int mid = (R + L) >> 1;
67 if (begin <= mid) upDateOne(begin, end, val, lson);
68 if (end > mid) upDateOne(begin, end, val, rson);
69 pushUpOne(cur, R - L + 1);
70 }
71 int queryOne(int val, int L, int R, int cur) {
72 if (L == R) return L;
73 pushDownOne(cur, R - L + 1);
74 // printf("%d %d %d***\n", L, R, sumOne[cur << 1].sum);
75 int mid = (L + R) >> 1;
76 if (sumOne[cur << 1].sum >= val) return queryOne(val, lson);
77 else if (sumOne[cur << 1].RtoLsum + sumOne[cur << 1 | 1].LtoRsum >= val) {
78 // if (mid - sumOne[cur << 1].RtoLsum < 0) {
79 //// printf("%d %d\n", mid, sumOne[cur << 1].RtoLsum);
80 //// printf("%d %d\n", L, R);
81 // printf("ff");
82 // while(1);
83 // }
84 return mid - sumOne[cur << 1].RtoLsum + 1;
85 }
86 else return queryOne(val, rson);
87 }
88
89
90 void pushDownTwo(int cur, int total) {
91 if (sumTwo[cur].add != -1) {
92 sumTwo[cur << 1].add = sumTwo[cur << 1 | 1].add = sumTwo[cur].add;
93 if (sumTwo[cur].add) {
94 sumTwo[cur << 1].LtoRsum = sumTwo[cur << 1].RtoLsum = sumTwo[cur << 1].sum = 0;
95 sumTwo[cur << 1 | 1].LtoRsum = sumTwo[cur << 1 | 1].RtoLsum = sumTwo[cur << 1 | 1].sum = 0;
96 } else {
97 sumTwo[cur << 1].LtoRsum = sumTwo[cur << 1].RtoLsum = sumTwo[cur << 1].sum = total - (total >> 1);
98 sumTwo[cur << 1 | 1].LtoRsum = sumTwo[cur << 1 | 1].RtoLsum = sumTwo[cur << 1 | 1].sum = (total >> 1);
99 }
100 sumTwo[cur].add = -1;
101 }
102 }
103 void pushUpTwo(int cur, int total) {
104 sumTwo[cur].LtoRsum = sumTwo[cur << 1].LtoRsum;
105 sumTwo[cur].RtoLsum = sumTwo[cur << 1 | 1].RtoLsum;
106 if (sumTwo[cur].LtoRsum == (total - (total >> 1))) sumTwo[cur].LtoRsum += sumTwo[cur << 1 | 1].LtoRsum;
107 if (sumTwo[cur].RtoLsum == (total >> 1)) sumTwo[cur].RtoLsum += sumTwo[cur << 1].RtoLsum;
108 sumTwo[cur].sum = max(sumTwo[cur << 1].sum, sumTwo[cur << 1 | 1].sum);
109 sumTwo[cur].sum = max(sumTwo[cur].sum, sumTwo[cur << 1].RtoLsum + sumTwo[cur << 1 | 1].LtoRsum);
110 }
111 void upDateTwo(int begin, int end, int val, int L, int R, int cur) {
112 if (L >= begin && R <= end) {
113 if (val) {
114 sumTwo[cur].sum = sumTwo[cur].LtoRsum = sumTwo[cur].RtoLsum = 0;
115 } else sumTwo[cur].sum = sumTwo[cur].LtoRsum = sumTwo[cur].RtoLsum = R - L + 1;
116 sumTwo[cur].add = val;
117 return;
118 }
119 pushDownTwo(cur, R - L + 1);
120 int mid = (L + R) >> 1;
121 if (begin <= mid) upDateTwo(begin, end, val, lson);
122 if (end > mid) upDateTwo(begin, end, val, rson);
123 pushUpTwo(cur, R - L + 1);
124 }
125 int queryTwo(int val, int L, int R, int cur) {
126 if (L == R) return L;
127 pushDownTwo(cur, R - L + 1);
128 int mid = (L + R) >> 1;
129 if (sumTwo[cur << 1].sum >= val) return queryTwo(val, lson);
130 else if (sumTwo[cur << 1].RtoLsum + sumTwo[cur << 1 | 1].LtoRsum >= val) return mid - sumTwo[cur << 1].RtoLsum + 1;
131 else return queryTwo(val, rson);
132 }
133 int f;
134 void work() {
135 printf("Case %d:\n", ++f);
136 int n, m;
137 scanf("%d%d", &n, &m);
138 // printf("%d %d\n", n, m);
139 build(root);
140 // upDateOne(1, 3, 1, root);
141 // upDateOne(4, 5, 1, root);
142 // upDateOne(1, 5, 0, root);
143 // printf("%d\n", sumOne[1].sum);
144 // printf("%d****\n", queryOne(5, root));
145 for (int i = 1; i <= m; ++i) {
146 char op[22];
147 scanf("%s", op);
148 if (op[0] == 'S') {
149 int L, R;
150 scanf("%d%d", &L, &R);
151 // if (L > R) swap(L, R);
152 // printf("%d %d***\n", L, R);
153 upDateOne(L, R, 0, root);
154 upDateTwo(L, R, 0, root);
155 printf("I am the hope of chinese chengxuyuan!!\n");
156 } else if (op[0] == 'D') { //屌丝
157 int val;
158 scanf("%d", &val);
159 if (sumOne[1].sum < val) {
160 printf("fly with yourself\n");
161 } else {
162 int pos = queryOne(val, root);
163 printf("%d,let's fly\n", pos);
164 // printf("%d: %d %d\n", pos, val, sumOne[1].sum);
165 upDateOne(pos, pos + val - 1, 1, root);
166 }
167 } else {
168 int val;
169 scanf("%d", &val);
170 if (sumOne[1].sum < val && sumTwo[1].sum < val) {
171 printf("wait for me\n");
172 } else {
173 if (sumOne[1].sum >= val) {
174 int pos = queryOne(val, root);
175 printf("%d,don't put my gezi\n", pos);
176 upDateOne(pos, pos + val - 1, 2, root);
177 upDateTwo(pos, pos + val - 1, 2, root);
178 } else {
179 int pos = queryTwo(val, root);
180 printf("%d,don't put my gezi\n", pos);
181 upDateOne(pos, pos + val - 1, 2, root);
182 upDateTwo(pos, pos + val - 1, 2, root);
183 }
184 }
185 }
186 }
187 return;
188 }
189 int main() {
190 #ifdef local
191 freopen("data.txt","r",stdin);
192 #endif
193 int t;
194 scanf("%d", &t);
195 while (t--) {
196 work();
197 }
198 return 0;
199
View Code
标签：begin,题目,cur,val,int,线段,mid,include From： https://blog.51cto.com/u_15833059/5779778