首先说下我写的线段树吧。
我是按照线段树【完全版】那个人的写法来写的，因为网上大多数题解都是按照他的写法来写。
确实比较飘逸，所以就借用了。
节点大小是maxn是4倍，准确来说是大于maxn的2^x次方的最小值的两倍。
lson 和 rson 用宏定义写了。因为是固定的量。
线段树不必保存自身的区间，因为一边传递过去的时候，在函数里就有区间表示，无谓开多些无用的变量。
pushUp函数，更新当前节点cur的值，其实就是，线段树一般都是处理完左右孩子，然后再递归更新父亲的嘛，这个pushUp函数就是用来更新父亲的。感觉不用这个函数更加清楚明了。
pushDown函数，在lazy--upDate的时候有用，作用是把延迟标记更新到左右节点。
多次使用sum不用清0，add要。build的时候就会初始化sum数据。但其他用法就可能要
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
void pushUp(int cur) {
sum[cur] = sum[cur << ] + sum[cur << | ];
}
void pushDown(int cur, int total) {
if (add[cur]) {
add[cur << ] += add[cur]; //传递去左右孩子
add[cur << | ] += add[cur]; // val >> 1 相当于 val / 2
sum[cur << ] += add[cur] * (total - (total >> )); //左孩子有多少个节点
sum[cur << | ] += add[cur] * (total >> ); //一共控制11个，则右孩子有5个
add[cur] = ;
}
}
void build(int L, int R, int cur) {
if (L == R) {
sum[cur] = a[L];
return;
}
int mid = (L + R) >> ;
build(lson);
build(rson);
pushUp(cur);
}
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 + ); //这里加了一次，后面pushDown就只能用add[cur]的
return;
}
pushDown(cur, R - L + ); //这个是必须的，因为下面的pushUp是直接等于的
//所以要先把加的，传递去右孩子，然后父亲又调用pushUp，才能保证正确性。
int mid = (L + R) >> ; //一直分解的是大区间，开始时是[1, n]这个区间。
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 + );
int ans = , mid = (L + R) >> ;
if (begin <= mid) ans += query(begin, end, lson); //只要区间涉及，就必须查询
if (end > mid) ans += query(begin, end, rson);
return ans;
}
成段更新模板
关于成段更新时的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 = + ;
int sum[maxn << ];
int a[maxn];
void pushUp(int cur) { //更新当前这个节点的信息
sum[cur] = sum[cur << ] + sum[cur << | ];
}
void build(int L, int R, int cur) {
if (L == R) {
sum[cur] = a[L];
return;
}
int mid = (L + R) >> ;
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) >> ;
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) >> ;
int ans = ;
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 = ; i <= n; ++i) {
scanf("%d", &a[i]);
}
build(, n, );
char cmd[];
while (scanf("%s", cmd) != EOF && cmd[] != 'E') {
int a, b;
scanf("%d%d", &a, &b);
if (cmd[] == 'Q') {
printf("%d\n", query(a, b, , n, ));
} else if (cmd[] == 'A') {
upDate(a, b, , n, );
} else {
upDate(a, -b, , n, );
}
}
return;
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d", &t);
while (t--) {
work();
}
return ;
}
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 = + ;
int mx[maxn << ];
int a[maxn];
void pushUp(int cur) {
mx[cur] = max(mx[cur << ], mx[cur << | ]);
}
void build(int L, int R, int cur) {
if (L == R) {
mx[cur] = a[L]; //就是自己
return;
}
int mid = (L + R) >> ;
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) >> ;
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) >> ;
int ans = ;
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 = ; i <= n; ++i) {
scanf("%d", &a[i]);
}
build(, n, );
for (int i = ; i <= m; ++i) {
char str[];
int b, c;
scanf("%s%d%d", str, &b, &c);
if (str[] == 'Q') {
printf("%d\n", query(b, c, , n, ));
} else upDate(b, c, , n, );
}
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
while (scanf("%d%d", &n, &m) != EOF) {
work();
}
return ;
}
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 = + ;
LL sum[maxn << ];
LL add[maxn << ];
int a[maxn];
void pushUp(int cur) {
sum[cur] = sum[cur << ] + sum[cur << | ];
}
void pushDown(int cur, int total) {
if (add[cur]) {
add[cur << ] += add[cur];
add[cur << | ] += add[cur]; // val >> 1 相当于 val / 2
sum[cur << ] += add[cur] * (total - (total >> )); //左孩子有多少个节点
sum[cur << | ] += add[cur] * (total >> ); //一共控制11个，则右孩子有5个
add[cur] = ;
}
}
void build(int L, int R, int cur) {
if (L == R) {
sum[cur] = a[L];
return;
}
int mid = (L + R) >> ;
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 + ); //控制的节点数目
return;
}
pushDown(cur, R - L + );
int mid = (L + R) >> ;
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 + );
LL ans = , mid = (L + R) >> ;
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 = ; i <= n; ++i) {
scanf("%d", &a[i]);
}
build(, n, );
char str[];
for (int i = ; i <= q; ++i) {
scanf("%s", str);
int L, R, val;
if (str[] == 'Q') {
scanf("%d%d", &L, &R);
printf("%I64d\n", query(L, R, , n, ));
} else {
scanf("%d%d%d", &L, &R, &val);
upDate(L, R, val, , n, );
}
}
return;
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
work();
return ;
}
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 = + ;
int add[maxn << ];
int sum[maxn << ];
void pushDown(int cur, int total) {
if (add[cur]) {
add[cur << ] = add[cur];
add[cur << | ] = add[cur];
sum[cur << ] = add[cur] * (total - (total >> ));
sum[cur << | ] = add[cur] * (total >> );
add[cur] = ;
}
}
void pushUp(int cur) {
sum[cur] = sum[cur << ] + sum[cur << | ];
}
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 + );
return;
}
pushDown(cur, R - L + );
int mid = (L + R) >> ;
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] = ;
return;
}
int mid = (L + R) >> ;
build(lson);
build(rson);
pushUp(cur);
}
int f;
void work() {
int n;
scanf("%d", &n);
build(, n, );
// cout << sum[2] << endl;
int m;
scanf("%d", &m);
for (int i = ; i <= m; ++i) {
int L, R, val;
scanf("%d%d%d", &L, &R, &val);
upDate(L, R, val, , n, );
// cout << L << " " << R << " " << val << endl; // cout << sum[3] << endl;
}
printf("Case %d: The total value of the hook is %d.\n", ++f, sum[]);
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
cin >> t;
while (t--) {
work();
memset(add, , sizeof add);
}
return ;
}
可以用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 = + ;
int a[maxn << ];
void pushDown(int cur, int total) {
if (a[cur]) {
a[cur << ] = (total - (total >> )) * (a[cur] / total);
a[cur << | ] = (total >> ) * (a[cur] / total);
a[cur] = ;
}
}
void upDate(int begin, int end, int val, int L, int R, int cur) {
if (L >= begin && R <= end) {
a[cur] = (R - L + ) * val;
return;
}
pushDown(cur, R - L + );
int mid = (L + R) >> ;
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 ();
return ;
}
int mid = (L + R) >> ;
int ans = query(lson) + query(rson);
return ans;
}
int f;
void work() {
int n, q;
cin >> n >> q;
a[] = n;
for (int i = ; i <= q; ++i) {
int L, R, val;
scanf("%d%d%d", &L, &R, &val);
upDate(L, R, val, , n, );
}
printf("Case %d: The total value of the hook is %d.\n", ++f, query(, n, ));
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d", &t);
while (t--) {
work();
}
return ;
}
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 = * + ;
int all[maxn];
int L[maxn];
int R[maxn];
set<int>number;
int seg[maxn << ];
void pushDown(int cur) {
if (seg[cur]) {
seg[cur << ] = seg[cur << | ] = seg[cur];
seg[cur] = ;
}
}
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) >> ;
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]] = ;
ans++;
}
// return;
}
pushDown(cur); //不return就pushDown
if (L == R) return;
int mid = (L + R) >> ;
query(lson);
query(rson);
}
void work() {
int n;
scanf("%d", &n);
number.clear();
memset(seg, , sizeof seg);
for (int i = ; i <= n; ++i) {
scanf("%d%d", &L[i], &R[i]);
number.insert(L[i]);
number.insert(R[i]);
}
int lenall = ;
for (set<int> :: iterator it = number.begin(); it != number.end(); ++it) {
all[++lenall] = *it; //去重
}
int t = lenall;
for (int i = ; i <= t; ++i) {
if (all[i] != all[i - ] + ) {
all[++lenall] = all[i - ] + ;
}
}
sort(all + , all + + lenall);
for (int i = ; i <= n; ++i) {
int begin = lower_bound(all + , all + + lenall, L[i]) - all;
int end = lower_bound(all + , all + + lenall, R[i]) - all;
upDate(begin, end, i, , lenall, );
}
ans = ;
memset(hash, , sizeof hash);
query(, lenall, );
cout << ans << endl;
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
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 = + ;
LL sum[maxn << ];
bool book[maxn << ];//查看是否还有更新的必要
int n;
void pushUp(int cur) {
sum[cur] = sum[cur << ] + sum[cur << | ];
book[cur] = book[cur << ] && book[cur << | ]; //左右孩子都不用更新了，就不更新了
}
void build(int L, int R, int cur) {
if (L == R) {
scanf("%I64d", &sum[cur]);
return;
}
int mid = (L + R) >> ;
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就不用更新了
book[cur] = ;
}
return;
}
int mid = (L + R) >> ;
if (begin <= mid && !book[cur << ]) upDate(begin, end, lson);
if (end > mid && !book[cur << | ]) 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) >> ;
LL ans = ;
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(, n, );
int m;
scanf("%d", &m);
for (int i = ; i <= m; ++i) {
int flag, L, R;
scanf("%d%d%d", &flag, &L, &R);
if (L > R) swap(L, R); //注意这个特别坑
if (flag == ) {
upDate(L, R, , n, );
} else {
printf("%I64d\n", query(L, R, , n, ));
}
}
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
while (scanf("%d", &n) != EOF) {
work();
memset(book, , sizeof book);
printf("\n");
}
return ;
}
线段树的区间合并
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 = + ;
int LtoRsum[maxn << ];
int RtoLsum[maxn << ];
bool book[maxn];
void build(int L, int R, int cur) {
LtoRsum[cur] = RtoLsum[cur] = R - L + ;
if (L == R) return;
int mid = (L + R) >> ;
build(lson);
build(rson);
}
void pushUp(int cur, int total) {
LtoRsum[cur] = LtoRsum[cur << ];
RtoLsum[cur] = RtoLsum[cur << | ];
if (LtoRsum[cur] == (total - (total >> ))) { //如果左孩子都丰满了，就可以接着合并右孩子的值
LtoRsum[cur] += LtoRsum[cur << | ];
}
if (RtoLsum[cur] == (total >> )) {
RtoLsum[cur] += RtoLsum[cur << ];
}
}
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) >> ;
if (pos <= mid) upDate(pos, val, lson);
else upDate(pos, val, rson);
pushUp(cur, R - L + );
}
int queryLtoRsum(int begin, int end, int L, int R, int cur) {
if (L >= begin && R <= end) return LtoRsum[cur];
int mid = (L + R) >> , 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 + ) 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) >> , 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 = ;
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 = ; i <= m; ++i) {
char str[];
int a;
scanf("%s", str);
if (str[] == 'D') {
scanf("%d", &a);
stack[++top] = a;
upDate(a, , root);
} else if (str[] == 'R') {
upDate(stack[top], , root);
--top;
} else {
scanf("%d", &a);
int ans = queryLtoRsum(a, n, root) + queryRtoLsum(, a, root);
printf("%d\n", ans == ? : ans - );
}
}
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
while (scanf("%d%d", &n, &m) != EOF) work();
return ;
}
上一题的升级版 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 = + ;
int n, m;
int LtoRsum[maxn << ];
int RtoLsum[maxn << ];
int add[maxn << ];
int sum[maxn << ];
void build(int L, int R, int cur) {
sum[cur] = LtoRsum[cur] = RtoLsum[cur] = R - L + ;
if (L == R) return;
int mid = (L + R) >> ;
build(lson);
build(rson);
}
void pushDown(int cur, int total) {
if (add[cur] != -) {
add[cur << ] = add[cur << | ] = add[cur];
if (add[cur]) {
sum[cur << ] = LtoRsum[cur << ] = RtoLsum[cur << ] = (total - (total >> ));
sum[cur << | ] = LtoRsum[cur << | ] = RtoLsum[cur << | ] = (total >> );
} else {
sum[cur << ] = LtoRsum[cur << ] = LtoRsum[cur << | ] = ;
sum[cur << | ] = RtoLsum[cur << ] = RtoLsum[cur << | ] = ;
}
add[cur] = -;
}
}
void pushUp(int cur, int total) {
LtoRsum[cur] = LtoRsum[cur << ];
RtoLsum[cur] = RtoLsum[cur << | ];
if (LtoRsum[cur] == (total - (total >> ))) LtoRsum[cur] += LtoRsum[cur << | ];
if (RtoLsum[cur] == (total >> )) RtoLsum[cur] += RtoLsum[cur << ];
sum[cur] = max(max(sum[cur << ], sum[cur << | ]), LtoRsum[cur << | ] + RtoLsum[cur << ]);//区间相互独立，没交集，不用减去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 + ;
} else sum[cur] = LtoRsum[cur] = RtoLsum[cur] = ;
add[cur] = val;
return;
}
int mid = (L + R) >> ;
pushDown(cur, R - L + );
if (begin <= mid) upDate(begin, end, val, lson);
if (end > mid) upDate(begin, end, val, rson);
pushUp(cur, R - L + );
}
//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 + );
int mid = (L + R) >> ;
if (sum[cur << ] >= val) return query(val, lson); //优先左孩子
else if (LtoRsum[cur << | ] + RtoLsum[cur << ] >= val) return mid - RtoLsum[cur << ] + ;
else return query(val, rson);
}
void work() {
memset(add, -, 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 = ; i <= m; ++i) {
int flag, a, b;
scanf("%d", &flag);
if (flag == ) {
scanf("%d", &a);
if (sum[] < a) {
printf("0\n");
} else {
int pos = query(a, root);
printf("%d\n", pos);
upDate(pos, pos + a - , , root);
}
} else {
scanf("%d%d", &a, &b);
upDate(a, min(a + b - , n), , root);
}
}
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
work();
return ;
}
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 = + ;
int add[maxn << ];
int sum[maxn << ];
int Lcur[maxn];
int Rcur[maxn];
int first[maxn];
bool in[maxn];
struct node {
int u, v, toNext;
}e[maxn << ];
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] = -;
if (L == R) return;
int mid = (L + R) >> ;
build(lson);
build(rson);
}
void pushDown(int cur) {
if (add[cur] != -) {
add[cur << ] = add[cur << | ] = add[cur];
sum[cur] = sum[cur << ] = sum[cur << | ] = add[cur];
add[cur] = -;
}
}
void pushUp(int cur) {
if (sum[cur << ] == sum[cur << | ]) sum[cur] = sum[cur << ];
else sum[cur] = -;
}
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) >> ;
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] != -) return sum[cur];
pushDown(cur);
int mid = (L + R) >> ;
if (pos <= mid) return query(pos, lson);
else return query(pos, rson);
}
int f;
void work() {
num = index = ;
memset(first, , sizeof first);
memset(in, , sizeof in);
memset(add, -, sizeof add);
printf("Case #%d:\n", ++f);
int n;
scanf("%d", &n);
for (int i = ; i <= n - ; ++i) {
int u, v;
scanf("%d%d", &v, &u);
addEdge(u, v);
in[v] = ;
}
for (int i = ; i <= n; ++i) {
if (in[i] == ) {
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 = ; i <= m; ++i) {
char op[];
int a, b;
scanf("%s", op);
if (op[] == '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 ;
}
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 = + ;
const int MOD = ;
myTypec sum1[maxn << ], sum2[maxn << ], sum3[maxn << ];
myTypec add[maxn << ], mult[maxn << ], same[maxn << ];
void build(int L, int R, int cur) {
sum1[cur] = sum2[cur] = sum3[cur] = ;
add[cur] = mult[cur] = same[cur] = ;
if (L == R) return;
int mid = (L + R) >> ;
build(lson);
build(rson);
}
void pushUp(int cur) {
sum1[cur] = (sum1[cur << ] + sum1[cur << | ]) % MOD;
sum2[cur] = (sum2[cur << ] + sum2[cur << | ]) % MOD;
sum3[cur] = (sum3[cur << ] + sum3[cur << | ]) % 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] += (( * val * sum11) % MOD + (total * temp) % MOD) %MOD;
sum2[cur] %= MOD; myTypec liu = temp;
temp = temp * val % MOD;
sum3[cur] += (( * sum22 * val) % MOD + ( * 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] = ;
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 << , same[cur], total - (total >> ));
ToSame(cur << | , same[cur], total >> );
same[cur] = ;
}
if (mult[cur]) {
ToMult(cur << , mult[cur], total - (total >> ));
ToMult(cur << | , mult[cur], total >> );
mult[cur] = ;
}
if (add[cur]) {
Toadd(cur << , add[cur], total - (total >> ));
Toadd(cur << | , add[cur], total >> );
add[cur] = ;
}
}
void upDate(int begin, int end, int val, int L, int R, int cur, int flag) {
if (L >= begin && R <= end) {
if (flag == ) { //加上一个数
Toadd(cur, val, R - L + );
} else if (flag == ) { //乘上一个数
ToMult(cur, val, R - L + );
} else if (flag == ) {
ToSame(cur, val, R - L + );
}
// while(1);
return;
}
pushDown(cur, R - L + );
int mid = (L + R) >> ;
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 == ) return sum1[cur];
if (p == ) return sum2[cur];
if (p == ) return sum3[cur];
while();
}
pushDown(cur, R - L + );
int mid = (L + R) >> ;
myTypec ans = ;
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 = ; i <= m; ++i) {
int flag, L, R, val;
cin >> flag >> L >> R >> val;
if (L > R) swap(L, R);
if (flag != ) {
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 == && m == ) break;
work();
}
return ;
}
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 = + ;
int n, m;
int sum[maxn << ], add[maxn << ];
void build(int L, int R, int cur) {
sum[cur] = R - L + ;
add[cur] = -;
if (L == R) return;
int mid = (L + R) >> ;
build(lson);
build(rson);
}
void pushDown(int cur, int total) {
if (add[cur] != -) {
add[cur << ] = add[cur << | ] = add[cur];
sum[cur << ] = (total - (total >> )) * add[cur];
sum[cur << | ] = (total >> ) * add[cur];
add[cur] = -;
}
}
void pushUp(int cur) {
sum[cur] = sum[cur << ] + sum[cur << | ];
}
void upDate(int begin, int end, int val, int L, int R, int cur) {
if (L >= begin && R <= end) {
sum[cur] = (R - L + ) * val;
add[cur] = val;
return;
}
pushDown(cur, R - L + );
int mid = (L + R) >> ;
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 + );
int mid = (L + R) >> ;
int ans = ;
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 - ;
while (begin <= end) {
int mid = (begin + end) >> ;
if (query(L, mid, root) >= toFindVal) {
R = mid;
end = mid - ;
} else begin = mid + ;
}
begin = a;
end = R;
while (begin <= end) {
int mid = (begin + end) >> ;
if (query(mid, R, root) >= toFindVal) {
L = mid;
begin = mid + ;
} else end = mid - ;
}
printf("%d %d\n", L, R);
upDate(L, R, , root);
}
void work() {
scanf("%d%d", &n, &m);
build(root);
for (int i = ; i <= m; ++i) {
int flag, a, b;
scanf("%d%d%d", &flag, &a, &b);
if (flag == ) {
int ans = query(a, n - , root);
if (ans == ) {
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 + - query(a, b, root);
printf("%d\n", ans);
upDate(a, b, , root);
}
}
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d", &t);
while (t--) {
work();
printf("\n");
}
return ;
}
hdu 4553
约会安排
http://acm.hdu.edu.cn/showproblem.php?pid=4553
和 POJ 3667 Hotel 一样的。
维护两个线段树，NS的先从sumOne（就是屌丝的）去找。然后占据，占据的时候同时更新女神的。就这样。看看Hotel那题的思路，就知道了。
刚开始的时候pushDownTwo少了一句话。wa到我傻逼一样。。委屈啊。
然后从Hotel那题试出来是pushDownTwo错误了，也是一件快乐的事情~
#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 1, n, 1
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = * + ;
struct node {
int LtoRsum, RtoLsum;
int add;
int sum;
} sumOne[maxn << ], sumTwo[maxn << ];
void build(int L, int R, int cur) {
sumOne[cur].LtoRsum = sumOne[cur].RtoLsum = sumOne[cur].sum = R - L + ;
sumTwo[cur].LtoRsum = sumTwo[cur].RtoLsum = sumTwo[cur].sum = R - L + ;
sumOne[cur].add = sumTwo[cur].add = -;
if (L == R) return;
int mid = (L + R) >> ;
build(lson);
build(rson);
}
void pushDownOne(int cur, int total) {
if (sumOne[cur].add != -) {
sumOne[cur << ].add = sumOne[cur << | ].add = sumOne[cur].add;
if (sumOne[cur].add) {
sumOne[cur << ].LtoRsum = sumOne[cur << ].RtoLsum = sumOne[cur << ].sum = ;
sumOne[cur << | ].LtoRsum = sumOne[cur << | ].RtoLsum = sumOne[cur << | ].sum = ;
} else {
sumOne[cur << ].LtoRsum = sumOne[cur << ].RtoLsum = sumOne[cur << ].sum = total - (total >> );
sumOne[cur << | ].LtoRsum = sumOne[cur << | ].RtoLsum = sumOne[cur << | ].sum = (total >> );
}
sumOne[cur].add = -;
}
}
void pushUpOne(int cur, int total) {
sumOne[cur].LtoRsum = sumOne[cur << ].LtoRsum;
sumOne[cur].RtoLsum = sumOne[cur << | ].RtoLsum;
if (sumOne[cur].LtoRsum == (total - (total >> ))) sumOne[cur].LtoRsum += sumOne[cur << | ].LtoRsum;
if (sumOne[cur].RtoLsum == (total >> )) sumOne[cur].RtoLsum += sumOne[cur << ].RtoLsum;
sumOne[cur].sum = max(sumOne[cur << ].sum, sumOne[cur << | ].sum);
sumOne[cur].sum = max(sumOne[cur].sum, sumOne[cur << ].RtoLsum + sumOne[cur << | ].LtoRsum);
}
void upDateOne(int begin, int end, int val, int L, int R, int cur) {
if (L >= begin && R <= end) {
if (val) {
sumOne[cur].sum = sumOne[cur].LtoRsum = sumOne[cur].RtoLsum = ;
} else sumOne[cur].sum = sumOne[cur].LtoRsum = sumOne[cur].RtoLsum = R - L + ;
sumOne[cur].add = val;
return;
}
pushDownOne(cur, R - L + );
int mid = (R + L) >> ;
if (begin <= mid) upDateOne(begin, end, val, lson);
if (end > mid) upDateOne(begin, end, val, rson);
pushUpOne(cur, R - L + );
}
int queryOne(int val, int L, int R, int cur) {
if (L == R) return L;
pushDownOne(cur, R - L + );
// printf("%d %d %d***\n", L, R, sumOne[cur << 1].sum);
int mid = (L + R) >> ;
if (sumOne[cur << ].sum >= val) return queryOne(val, lson);
else if (sumOne[cur << ].RtoLsum + sumOne[cur << | ].LtoRsum >= val) {
// if (mid - sumOne[cur << 1].RtoLsum < 0) {
//// printf("%d %d\n", mid, sumOne[cur << 1].RtoLsum);
//// printf("%d %d\n", L, R);
// printf("ff");
// while(1);
// }
return mid - sumOne[cur << ].RtoLsum + ;
}
else return queryOne(val, rson);
} void pushDownTwo(int cur, int total) {
if (sumTwo[cur].add != -) {
sumTwo[cur << ].add = sumTwo[cur << | ].add = sumTwo[cur].add;
if (sumTwo[cur].add) {
sumTwo[cur << ].LtoRsum = sumTwo[cur << ].RtoLsum = sumTwo[cur << ].sum = ;
sumTwo[cur << | ].LtoRsum = sumTwo[cur << | ].RtoLsum = sumTwo[cur << | ].sum = ;
} else {
sumTwo[cur << ].LtoRsum = sumTwo[cur << ].RtoLsum = sumTwo[cur << ].sum = total - (total >> );
sumTwo[cur << | ].LtoRsum = sumTwo[cur << | ].RtoLsum = sumTwo[cur << | ].sum = (total >> );
}
sumTwo[cur].add = -;
}
}
void pushUpTwo(int cur, int total) {
sumTwo[cur].LtoRsum = sumTwo[cur << ].LtoRsum;
sumTwo[cur].RtoLsum = sumTwo[cur << | ].RtoLsum;
if (sumTwo[cur].LtoRsum == (total - (total >> ))) sumTwo[cur].LtoRsum += sumTwo[cur << | ].LtoRsum;
if (sumTwo[cur].RtoLsum == (total >> )) sumTwo[cur].RtoLsum += sumTwo[cur << ].RtoLsum;
sumTwo[cur].sum = max(sumTwo[cur << ].sum, sumTwo[cur << | ].sum);
sumTwo[cur].sum = max(sumTwo[cur].sum, sumTwo[cur << ].RtoLsum + sumTwo[cur << | ].LtoRsum);
}
void upDateTwo(int begin, int end, int val, int L, int R, int cur) {
if (L >= begin && R <= end) {
if (val) {
sumTwo[cur].sum = sumTwo[cur].LtoRsum = sumTwo[cur].RtoLsum = ;
} else sumTwo[cur].sum = sumTwo[cur].LtoRsum = sumTwo[cur].RtoLsum = R - L + ;
sumTwo[cur].add = val;
return;
}
pushDownTwo(cur, R - L + );
int mid = (L + R) >> ;
if (begin <= mid) upDateTwo(begin, end, val, lson);
if (end > mid) upDateTwo(begin, end, val, rson);
pushUpTwo(cur, R - L + );
}
int queryTwo(int val, int L, int R, int cur) {
if (L == R) return L;
pushDownTwo(cur, R - L + );
int mid = (L + R) >> ;
if (sumTwo[cur << ].sum >= val) return queryTwo(val, lson);
else if (sumTwo[cur << ].RtoLsum + sumTwo[cur << | ].LtoRsum >= val) return mid - sumTwo[cur << ].RtoLsum + ;
else return queryTwo(val, rson);
}
int f;
void work() {
printf("Case %d:\n", ++f);
int n, m;
scanf("%d%d", &n, &m);
// printf("%d %d\n", n, m);
build(root);
// upDateOne(1, 3, 1, root);
// upDateOne(4, 5, 1, root);
// upDateOne(1, 5, 0, root);
// printf("%d\n", sumOne[1].sum);
// printf("%d****\n", queryOne(5, root));
for (int i = ; i <= m; ++i) {
char op[];
scanf("%s", op);
if (op[] == 'S') {
int L, R;
scanf("%d%d", &L, &R);
// if (L > R) swap(L, R);
// printf("%d %d***\n", L, R);
upDateOne(L, R, , root);
upDateTwo(L, R, , root);
printf("I am the hope of chinese chengxuyuan!!\n");
} else if (op[] == 'D') { //屌丝
int val;
scanf("%d", &val);
if (sumOne[].sum < val) {
printf("fly with yourself\n");
} else {
int pos = queryOne(val, root);
printf("%d,let's fly\n", pos);
// printf("%d: %d %d\n", pos, val, sumOne[1].sum);
upDateOne(pos, pos + val - , , root);
}
} else {
int val;
scanf("%d", &val);
if (sumOne[].sum < val && sumTwo[].sum < val) {
printf("wait for me\n");
} else {
if (sumOne[].sum >= val) {
int pos = queryOne(val, root);
printf("%d,don't put my gezi\n", pos);
upDateOne(pos, pos + val - , , root);
upDateTwo(pos, pos + val - , , root);
} else {
int pos = queryTwo(val, root);
printf("%d,don't put my gezi\n", pos);
upDateOne(pos, pos + val - , , root);
upDateTwo(pos, pos + val - , , root);
}
}
}
}
return;
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
int t;
scanf("%d", &t);
while (t--) {
work();
}
return ;
}