总时间限制: 

10000ms

 

单个测试点时间限制: 

1000ms

 

内存限制: 

262144kB

描述

给一个长为N的数列，有M次操作，每次操作是以下两种之一：

（1）将某连续一段同时改成一个数

（2）求数列中某连续一段的和

输入

第一行两个正整数N和M。
第二行N的整数表示这个数列。
接下来M行，每行开头是一个字符，若该字符为‘M‘，则表示一个修改操作，接下来三个整数x、y和z，表示在[x,y]这段区间的数改为z；若该字符为‘Q‘，则表示一个询问操作，接下来两个整数x和y，表示求[x,y]这段区间的和。

输出

对每一个询问操作单独输出一行，表示答案。

样例输入

5 31 2 3 4 5Q 1 5M 2 3 2Q 3 5

样例输出

1511

提示

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         else103         {104             ans=0;105             ask(1,x,y);106             printf("%d\n",ans);107         }108     }109     return 0;110 }111 12: Challenge 5最近的提交

 

12:Challenge 5（线段树区间直接修改）