首页 > 代码库 > codevs 1299 线段树 区间更新查询
codevs 1299 线段树 区间更新查询
1299 切水果
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 Description
简单的说,一共N个水果排成一排,切M次,每次切[L,R]区间的所有水果(可能有的水果被重复切),每切完一次输出剩下水果数量
数据已重新装配，不会出现OLE错误
时限和数据范围适当修改，避免数据包过大而浪费空间资源
输入描述 Input Description
第1行共包括2个正整数，分别为N,M。
接下来m行每行两个正整数L,R
输出描述 Output Description
一共输出M行,每行输出切完之后剩下水果数量
样例输入 Sample Input
10 3
3 5
2 8
1 5
样例输出 Sample Output
7
3
2
数据范围及提示 Data Size & Hint
30%的数据满足N，M<=5,000
60%的数据满足N，M<=100,000
100% 的数据满足1<=L<=R<=N<=500,000，1<=M<=500,000
题意：n个水果排成一排 m次查询 每次删除[L,R]区间内的水果 并输出剩下的水果的数量
题解：线段树处理 题目数据有问题 存在L<0 R>N的数据
1 /****************************** 2 code by drizzle 3 blog: www.cnblogs.com/hsd-/ 4 ^ ^ ^ ^ 5 O O 6 ******************************/ 7 #include<bits/stdc++.h> 8 #include<iostream> 9 #include<cstring> 10 #include<cstdio> 11 #include<map> 12 #include<algorithm> 13 #include<queue> 14 #define ll __int64 15 using namespace std; 16 struct node 17 { 18 int l,r; 19 int w; 20 int add; 21 }tree[2000005]; 22 void buildtree(int root,int left,int right) 23 { 24 tree[root].l=left; 25 tree[root].r=right; 26 tree[root].add=0; 27 if(left==right) 28 { 29 tree[root].w=1; 30 return ; 31 } 32 int mid=(left+right)>>1; 33 buildtree(root<<1,left,mid); 34 buildtree(root<<1|1,mid+1,right); 35 tree[root].w=tree[root<<1].w+tree[root<<1|1].w; 36 } 37 void pushdown(int root) 38 { 39 if(tree[root].add==0) return; 40 tree[root<<1].add=1; 41 tree[root<<1|1].add=1; 42 tree[root].add=0; 43 tree[root<<1].w=0; 44 tree[root<<1|1].w=0; 45 } 46 void updata(int root,int left,int right,int c) 47 { 48 if(tree[root].l==left&&tree[root].r==right) 49 { 50 tree[root].add=c; 51 tree[root].w=0; 52 return ; 53 } 54 pushdown(root); 55 int mid=(tree[root].l+tree[root].r)>>1; 56 if(right<=mid) 57 { 58 updata(root<<1,left,right,c); 59 } 60 else 61 { 62 if(left>mid) 63 updata(root<<1|1,left,right,c); 64 else 65 { 66 updata(root<<1,left,mid,c); 67 updata(root<<1|1,mid+1,right,c); 68 } 69 } 70 tree[root].w=tree[root<<1].w+tree[root<<1|1].w; 71 } 72 int query(int root ,int left,int right) 73 { 74 if(tree[root].l==left&&tree[root].r==right) 75 { 76 return tree[root].w; 77 } 78 pushdown(root); 79 int mid=(tree[root].l+tree[root].r)>>1; 80 if(mid<=right) 81 return query(root<<1,left,right); 82 else 83 { 84 if(left>mid) 85 return query(root<<1|1,left,right); 86 else 87 return query(root<<1,left,mid)+query(root<<1|1,mid+1,right); 88 } 89 } 90 int n,m; 91 int le,ri; 92 int main() 93 { 94 while(scanf("%d %d",&n,&m)!=EOF) 95 { 96 buildtree(1,1,n); 97 for(int i=1;i<=m;i++) 98 { 99 scanf("%d %d",&le,&ri);100 updata(1,max(1,le),min(n,ri),1);101 printf("%d\n",query(1,1,n));102 }103 }104 return 0;105 }
codevs 1299 线段树 区间更新查询
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。