poj3667【线段树水题】

题意:n个空房间。两种操作:1.选择最小的连续D个房间入住,并输出这连续D个房间的最小标号。2.将某个区间内的房间全部退房。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #define ll long long
 5 #define lson l, m, rt<<1
 6 #define rson m+1, r, rt<<1|1
 7 #define st first
 8 #define nd second
 9 #define mp make_pair
10 #define pii pair<int, int>
11 #define gg puts("gg");
12 using namespace std;
13 void gmax(int& a, int b){
14     if(a < b) a = b;
15 }
16 const int N = 5e4+10;
17 struct Node{
18     int lsum, rsum, sum;
19     int tag;
20 };
21 Node T[N<<2];
22 void pushup(int l, int r, int rt){
23     T[rt].lsum = T[rt<<1].lsum, T[rt].rsum = T[rt<<1|1].rsum;
24     int m = l+r >> 1;
25     if(T[rt<<1].lsum == m-l+1) T[rt].lsum += T[rt<<1|1].lsum;
26     if(T[rt<<1|1].rsum == r-m) T[rt].rsum += T[rt<<1].rsum;
27     T[rt].sum = max(T[rt<<1].sum, T[rt<<1|1].sum);
28     gmax(T[rt].sum, T[rt<<1].rsum+T[rt<<1|1].lsum);
29 }
30 void pushdown(int l, int r, int rt){
31     if(T[rt].tag != -1){
32         T[rt<<1].tag = T[rt<<1|1].tag = T[rt].tag;
33         int m = l+r >> 1;
34         T[rt<<1].lsum = T[rt<<1].rsum = T[rt<<1].sum = T[rt].tag? m-l+1 : 0;
35         T[rt<<1|1].lsum = T[rt<<1|1].rsum = T[rt<<1|1].sum = T[rt].tag? r-m : 0;
36         T[rt].tag = -1;
37     }
38 }
39 void build(int l, int r, int rt){
40     T[rt].lsum = T[rt].rsum = T[rt].sum = r-l+1;
41     T[rt].tag = -1;
42     if(l == r)
43         return ;
44     int m = l+r >> 1;
45     build(lson);
46     build(rson);
47 }
48 int query(int c, int l, int r, int rt){
49     //printf("query %d: l %d, r %d, lson %d, rson %d, sum %d\n", rt, l, r, T[rt].lsum, T[rt].rsum, T[rt].sum);
50     if(l == r)
51         return l;
52     pushdown(l, r, rt);
53     int m = l+r >> 1;
54     if(T[rt<<1].sum >= c) return query(c, lson);
55     if(T[rt<<1].rsum+T[rt<<1|1].lsum >= c) return m-T[rt<<1].rsum+1;
56     return query(c, rson);
57 }
58 void update(int L, int R, int c, int l, int r, int rt){
59     if(L <= l&&r <= R){
60         T[rt].tag = c;
61         T[rt].lsum = T[rt].rsum = T[rt].sum = c? r-l+1:0;
62         return ;
63     }
64     pushdown(l, r, rt);
65     int m = l+r >> 1;
66     if(L <= m) update(L, R, c, lson);
67     if(R > m) update(L, R, c, rson);
68     pushup(l, r, rt);
69     //printf("updaet %d: l %d, r %d, lson %d, rson %d, sum %d\n", rt, l, r, T[rt].lsum, T[rt].rsum, T[rt].sum);
70 }
71
72 int main(){
73     int n, m, x, y, op;
74     scanf("%d%d", &n, &m);
75     build(1, n, 1);
76     while(m--){
77         scanf("%d", &op);
78         if(op == 1){
79             scanf("%d", &x);
80             if(T[1].sum < x) puts("0");
81             else {
82                 int ret = query(x, 1, n, 1);
83                 printf("%d\n", ret);
84                 update(ret, ret+x-1, 0, 1, n, 1);
85             }
86         }
87         else {
88             scanf("%d%d", &x, &y);
89             update(x, x+y-1, 1, 1, n, 1);
90         }
91     }
92     return 0;
93 }

后记:这也是线段树一经典题。不难。

主要是通过这种写法可以O(logn)的时间内完成离散化查询。不过平时一般都是二分+树状数组O(lognlogn)完成离散化查询。

时间: 10-27

poj3667【线段树水题】的相关文章

[ACM] Color the ball [线段树水题][数组开大]

Description N个气球排成一排,从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的"小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色.但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了,你能帮他算出每个气球被涂过几次颜色吗? Input 每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行,每行包括2个整数a b(1 <= a <= b <= N).  当N

P2023 [AHOI2009] 维护序列(线段树水题)

题目描述 老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成. 有长为N的数列,不妨设为a1,a2,…,aN .有如下三种操作形式: (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模P的值. 输入输出格式 输入格式: 第一行两个整数N和P(1≤P≤1000000000).第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N).第三行有一个整

codeforces 339C Xenia and Bit Operations(线段树水题)

转载请注明出处: http://www.cnblogs.com/fraud/          ——by fraud Xenia and Bit Operations Xenia the beginner programmer has a sequence a, consisting of 2n non-negative integers: a1, a2, ..., a2n. Xenia is currently studying bit operations. To better unders

hdu - 1394 Minimum Inversion Number(线段树水题)

http://acm.hdu.edu.cn/showproblem.php?pid=1394 很基础的线段树. 先查询在更新,如果后面的数比前面的数小肯定会查询到前面已经更新过的值,这时候返回的sum就是当前数的逆序数. 这样查询完之后得到初始数列的逆序数,要求得所有序列的最小逆序数,还需要循环一次. 设初始序列abcde中逆序数为k,小于a的个数是t-1那么大于a的个数就是n-t,当把a左移一位,原来比a大的都变成了a的逆序对,即逆序数增加了n-t,但是原来比a小的数都变成了顺序, 因此逆序数

hdu 1754 线段树 水题 单点更新 区间查询

I Hate It Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 59558    Accepted Submission(s): 23201 Problem Description 很多学校流行一种比较的习惯.老师们很喜欢询问,从某某到某某当中,分数最高的是多少.这让很多学生很反感. 不管你喜不喜欢,现在需要你做的是,就是按照老师的要

线段树水题

1.洛谷p1351 https://www.luogu.org/problem/show?pid=1531 //单点修改区间询问 #include<iostream> #include<cstdio> #include<cstring> #define maxn 200001 using namespace std; int n,m,x,y,z,ans1,ans2; char c; struct node { int l,r,sum,max; }tree[maxn<

线段树水题 #1077 : RMQ问题再临-线段树

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std; #define maxn 1000000 + 10 #define Lson L, mid, root<<1 #define Rson mid+1, R, root<<1|1 #define

POJ 3264 Balanced Lineup(最大最小差值 线段树水题)

Language: Default Balanced Lineup Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 37122   Accepted: 17383 Case Time Limit: 2000MS Description For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order.

HDU 4893 线段树裸题

Wow! Such Sequence! Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2512    Accepted Submission(s): 751 Problem Description Recently, Doge got a funny birthday present from his new friend, Pro