12:Challenge 5（线段树区间直接修改）
12:Challenge 5（线段树区间直接修改）
attack
发布于 2018-04-12 12:01:35
发布于 2018-04-12 12:01:35
总时间限制: 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最近的提交本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-07-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读