# ZOJ 3324 Machine(线段树区间合并）

10 3

p 0 9

r 0 5

r 6 9

cover作为懒惰标记下推该区间的子区间需要被压几次

 KinderRiven C Accepted 6776 170 C++ (g++ 4.7.2) 3285
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson (pos<<1)
#define rson (pos<<1|1)
const int maxn = 20005;
const int maxd = 55555;
struct Input{
char op[5];
int x,y;
}input[maxn];
int Hash[maxd],cnt,ret;
void Hash_init(){
sort(Hash,Hash + cnt);
cnt = unique(Hash,Hash + cnt) - Hash;
int t = cnt;
for(int i = 1; i < t; i++)
if(Hash[i - 1] + 1 != Hash[i]) Hash[cnt++] = Hash[i - 1] + 1;
sort(Hash,Hash + cnt);
}
int HASH(int t){
return lower_bound(Hash,Hash + cnt,t) - Hash;
}
struct Node{
int l,r;
int lx,rx,min_v,sum,cover;
int mid(){
return (l + r) >> 1;
}
int len(){
return r - l + 1;
}
}node[maxd << 2];
void build(int l,int r,int pos){
node[pos].l = l;
node[pos].r = r;
node[pos].lx = node[pos].rx = node[pos].len();
node[pos].min_v = 0;
node[pos].sum = 1;
node[pos].cover = 0;
if(l == r) return;
int mid = node[pos].mid();
build(l,mid,lson);
build(mid + 1,r,rson);
}
void pushdown(int pos){
if(node[pos].cover){
node[lson].cover += node[pos].cover;
node[rson].cover += node[pos].cover;
node[lson].min_v += node[pos].cover;
node[rson].min_v += node[pos].cover;
node[pos].cover = 0;
}
}
void pushup(int pos){
node[pos].min_v = min(node[lson].min_v,node[rson].min_v);
if(node[lson].min_v == node[rson].min_v){
node[pos].lx = node[lson].lx;
node[pos].rx = node[rson].rx;
if(node[pos].lx == node[lson].len()) node[pos].lx += node[rson].lx;
if(node[pos].rx == node[rson].len()) node[pos].rx += node[lson].rx;
node[pos].sum = node[lson].sum + node[rson].sum;
if(node[lson].rx && node[rson].lx)
node[pos].sum --;
}
else if(node[lson].min_v < node[rson].min_v){
node[pos].lx = node[lson].lx;
node[pos].rx = 0;
node[pos].sum = node[lson].sum;
}
else{
node[pos].rx = node[rson].rx;
node[pos].lx = 0;
node[pos].sum = node[rson].sum;
}
}
void update(int l,int r,int pos,int d){
if(l <= node[pos].l && node[pos].r <= r){
node[pos].cover += d;
node[pos].min_v += d;
return;
}
pushdown(pos);
int mid = node[pos].mid();
if(l <= mid)
update(l,r,lson,d);
if(r  > mid)
update(l,r,rson,d);
pushup(pos);
}
int main(){
int T,Case = 1;
scanf("%d",&T);
while(T--){
int n,m;
cnt = 0;
ret = 0;
scanf("%d%d",&n,&m);
Hash[cnt++] = 0;
Hash[cnt++] = n - 1;
for(int i = 0; i < m; i++){
scanf("%s%d%d",input[i].op,&input[i].x,&input[i].y);
Hash[cnt++] = input[i].x;
Hash[cnt++] = input[i].y;
}
Hash_init();
build(0,cnt - 1,1);
printf("Case #%d:\n",Case++);
for(int i = 0; i < m; i++){
int l = HASH(input[i].x),r = HASH(input[i].y),c,t = 0,ans;
if(input[i].op[0] == 'p') c = 1;
else  c = -1;
update(l,r,1,c);
if(node[1].min_v == 0) t = 1;
ans = t * node[1].sum;
printf("%d\n",ans);
}
}
return 0;
}
/*
1
10 3
p 0 9
r 0 5
r 6 9
*/

## HDU 3911 Black And White（线段树区间合并）

Problem Description There are a bunch of stones on the beach; Stone color is white or black. Little Sheep has a magic brush, she can change the color of a continuous stone, black to white, white to black. Little Sheep like black very much, so she wan

## poj3667 线段树 区间合并

1 //Accepted 3728 KB 1079 ms 2 //线段树 区间合并 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <queue> 7 #include <cmath> 8 #include <algorithm> 9 using namespace std; 10 /** 11 * This is a document

## hdu3911 线段树 区间合并

1 //Accepted 3911 750MS 9872K 2 //线段树 区间合并 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <queue> 7 #include <cmath> 8 #include <algorithm> 9 using namespace std; 10 /** 11 * This is a documen

## 线段树 区间合并

poj3667 Hotel 区间合并入门题,照着代码打的, 题意:1 a:询问是不是有连续长度为a的空房间,有的话住进最左边       2 a b:将[a,a+b-1]的房间清空思路:记录区间中最长的空房间,开三个数组,msum[rt]表示节点rt内连续的1的个数的最大值,lsum[rt]表示从节点rt左端点开始连续1的个数,rsum[rt]表示从节点rt右端点开始连续1的个数..线段树操作:update:区间替换 query:询问满足条件的最左端点 1 #include<iostream>

## 【BZOJ3638】Cf172 k-Maximum Subsequence Sum 线段树区间合并（模拟费用流）

[BZOJ3638]Cf172 k-Maximum Subsequence Sum Description 给一列数,要求支持操作: 1.修改某个数的值 2.读入l,r,k,询问在[l,r]内选不相交的不超过k个子段,最大的和是多少.1 ≤ n ≤ 105,1 ≤ m ≤ 105,1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ 20 Sample Input 9 9 -8 9 -1 -1 -1 9 -8 9 3 1 1 9 1 1 1 9 2 1 4 6 3 Sample Output 17 25