12:Challenge 5(线段树区间直接修改)
2018-06-18 04:00:41来源:未知 阅读 ()
- 总时间限制:
- 10000ms
- 单个测试点时间限制:
- 1000ms
- 内存限制:
- 262144kB
- 描述
-
给一个长为N的数列,有M次操作,每次操作是以下两种之一:
(1)将某连续一段同时改成一个数
(2)求数列中某连续一段的和
- 输入
- 第一行两个正整数N和M。
第二行N的整数表示这个数列。
接下来M行,每行开头是一个字符,若该字符为'M',则表示一个修改操作,接下来三个整数x、y和z,表示在[x,y]这段区间的数改为z;若该字符为'Q',则表示一个询问操作,接下来两个整数x和y,表示求[x,y]这段区间的和。 - 输出
- 对每一个询问操作单独输出一行,表示答案。
- 样例输入
-
5 3 1 2 3 4 5 Q 1 5 M 2 3 2 Q 3 5
- 样例输出
-
15 11
- 提示
- 1<=N<=10^5,1<=M<=10^5,输入保证合法,且所有整数及答案可用带符号32位整型存储。
- 对于线段树的直接修改,
- 我们首先考虑要维护一个修改标记,
- 注意这个标记是可以每次被覆盖的!
- 然后值直接区间修改就好
-
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define ls k<<1 5 #define rs k<<1|1 6 using namespace std; 7 const int MAXN=100001; 8 const int maxn=0x7ffff; 9 void read(int &n) 10 { 11 char c='+';int x=0;bool flag=0; 12 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 13 while(c>='0'&&c<='9') 14 x=(x<<1)+(x<<3)+c-48,c=getchar(); 15 flag==1?n=-x:n=x; 16 } 17 int n,m; 18 int ans=0; 19 struct node 20 { 21 int l,r,w,f; 22 node() 23 { 24 l=r=w=0; 25 f=-maxn; 26 } 27 }tree[MAXN<<2]; 28 void update(int k) 29 { 30 tree[k].w=tree[ls].w+tree[rs].w; 31 } 32 void build(int ll,int rr,int k) 33 { 34 tree[k].l=ll;tree[k].r=rr; 35 if(ll==rr) 36 { 37 read(tree[k].w); 38 return ; 39 } 40 int mid=(ll+rr)>>1; 41 build(ll,mid,ls); 42 build(mid+1,rr,rs); 43 update(k); 44 } 45 void push(int k) 46 { 47 tree[ls].w=(tree[ls].r-tree[ls].l+1)*tree[k].f; 48 tree[rs].w=(tree[rs].r-tree[rs].l+1)*tree[k].f; 49 tree[ls].f=tree[k].f; 50 tree[rs].f=tree[k].f; 51 tree[k].f=-maxn; 52 53 } 54 void change(int k,int wl,int wr,int v) 55 { 56 if(wr<tree[k].l||wl>tree[k].r) 57 return ; 58 if(wl<=tree[k].l&&tree[k].r<=wr) 59 { 60 tree[k].w=(tree[k].r-tree[k].l+1)*v; 61 tree[k].f=v; 62 return ; 63 } 64 int mid=(tree[k].l+tree[k].r)>>1; 65 if(tree[k].f!=-maxn) 66 push(k); 67 change(ls,wl,wr,v); 68 change(rs,wl,wr,v); 69 update(k); 70 } 71 void ask(int k,int wl,int wr) 72 { 73 if(wr<tree[k].l||wl>tree[k].r) 74 return ; 75 if(wl<=tree[k].l&&tree[k].r<=wr) 76 { 77 ans+=tree[k].w; 78 return ; 79 } 80 int mid=(tree[k].l+tree[k].r)>>1; 81 if(tree[k].f!=-maxn) 82 push(k); 83 ask(ls,wl,wr); 84 ask(rs,wl,wr); 85 update(k); 86 } 87 int main() 88 { 89 read(n);read(m); 90 build(1,n,1); 91 for(int i=1;i<=m;i++) 92 { 93 char c;int x,y; 94 cin>>c; 95 read(x);read(y); 96 if(c=='M') 97 { 98 int v; 99 read(v); 100 change(1,x,y,v); 101 } 102 else 103 { 104 ans=0; 105 ask(1,x,y); 106 printf("%d\n",ans); 107 } 108 } 109 return 0; 110 } 111 12: Challenge 5最近的提交
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【数据结构】树套树——线段树套平衡树 2020-04-18
- 线段树学习资料 2020-03-19
- 排兵布阵 2020-02-21
- 【题解】P1440 求m区间内的最小值 2019-12-23
- 线段树 2019-11-28
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash