ZOJ 3324 Machine(线段树区间合并)

这道题网上很多代码是错误的,由于后台数据水,他们可以AC。

比如这组数据

10 3

p 0 9

r 0 5

r 6 9

输出应该是 0 1 1

所以有的人直接记录该区间是否被覆盖过的方法是错误的

正确方法应该是记录这段区间的最小高度(就是最接近初始位置的高度),和最小高度对应的最长左区间和右区间

开一个sum记录这段区间最小高度的块数,min_v 记录该区间最小高度

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
*/
时间: 04-28

ZOJ 3324 Machine(线段树区间合并)的相关文章

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

HDU 3308 LCIS (线段树区间合并)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3308 题目很好懂,就是单点更新,然后求区间的最长上升子序列. 线段树区间合并问题,注意合并的条件是a[mid + 1] > a[mid],写的细心点就好了. 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const int MAXN = 1

HDU 5316 Magician(线段树区间合并入门)

本文纯属原创,转载请注明出处谢谢.http://blog.csdn.net/zip_fan. 题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5316 Time Limit: 18000/9000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Problem Description Fantasy magicians usually gain their ability

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

HDU 3308 LCIS(最长连续上升子序列)(线段树区间合并)

题意:给你n个整数,有两种操作,U A B把第A个数变成B,Q A B查询区间[A,B]的最长连续上升序列. 思路:还是查询和更新操作,而且也是询问区间中满足条件的连续最长区间 ,所以是线段树区间合并类型的题,通法是开三棵线段树,一个记录此区间内的LCIS的最长长度,一个记录从左边第一个数开始的LCIS长度,另一个记录从右边最后一个数结尾的LCIS长度.然后试图找到父亲与儿子关系维护的递推关系式就好 本题中的递推关系是: 1. 左儿子最右边的值 < 右儿子最左边的值 lmx = (左儿子的lmx

POJ 3667 Hotel (初遇线段树区间合并)

题意: 有一个线段,从1到n,下面m个操作,操作分两个类型,以1开头的是查询操作,以2开头的是更新操作 1 w 表示在总区间内查询一个长度为w的可用区间并且要最靠左,能找到的话返回这个区间的左端点并占用了这个区间,找不到返回0 2 a len , 表示从单位a开始,清除一段长度为len的区间(将其变为可用,不被占用),不需要输出. 思路: 这是第一次遇到线段树区间合并的题目,写下感悟,还是对线段的更新和查询工作,但是查询的对象的性质已经不像单点那样,查询的是某个线段的最大可用区间是多少,还要一并