| xjr考考你数据结构（根号3） |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
请你编写一个数据结构，完成以下功能： 1）求出第L个到第R个数中的最大、最小值以及连续和。 2）将第addL到addR个数改成v。 |
|
输入
|
|
第一行：n，表示数的个数
第二行：空格分开每个数Ai 第三行：Q，表示操作数目 后Q行：先输入一个字母， 若字母为“Q”则后面跟上两个数，分别为L与R 若字母为“C”则后面跟上三个数，分别为addL，addR与v |
|
输出
|
|
若干行，按顺序针对每个查询（Q）操作分别输出最大、最小值以及连续和。每行遵守以下格式（行末无空格）：
MaxNum: 整数, MinNum: 整数, Sum: 整数 |
|
输入示例
|
|
5
1 2 3 4 5 3 Q 1 4 C 3 3 5 Q 1 5 |
|
输出示例
|
|
MaxNum: 4, MinNum: 1, Sum: 10
MaxNum: 5, MinNum: 1, Sum: 17 |
|
其他说明
|
|
0 < n, q < 100001
0 < Ai < 2001 0 < L, R < n + 1 |
题解：线段树大水题
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define CH for(int d=0;d<=1;d++) if(ch[d])
using namespace std;
const int maxn=+,maxnode=+,inf=-1u>>;
struct node{
node*ch[];int mi,mx,sm,add,set,siz;node(){mi=inf;mx=-inf;sm=;set=inf;}
void sett(int tag){mi=mx=set=tag;sm=tag*siz;return;}
void down(){
if(set!=inf){CH{ch[d]->sett(set);}set=inf;}
return;
}
void update(){
mi=inf;mx=-inf;sm=;
CH{mi=min(mi,ch[d]->mi);mx=max(mx,ch[d]->mx);sm+=ch[d]->sm;}
return;
}
}seg[maxnode],*nodecnt=seg,*root;
int A[maxn],ql,qr,cv,tp;
void build(node*&x,int L,int R){
x=nodecnt++;
if(L==R) x->mi=x->mx=x->sm=A[L];
else{
int M=L+R>>;
build(x->ch[],L,M);
build(x->ch[],M+,R);
x->update();
} x->siz=R-L+;return;
}
void update(node*&x,int L,int R){
if(ql<=L&&R<=qr) x->sett(cv);
else{
int M=L+R>>;
x->down();
if(ql<=M) update(x->ch[],L,M);
if(qr>M) update(x->ch[],M+,R);
x->update();
}
return;
}
int _mi,_mx,_sm;
void query(node*x,int L,int R){
if(ql<=L&&R<=qr){
_mi=min(_mi,x->mi);
_mx=max(_mx,x->mx);
_sm+=x->sm;
}
else{
int M=L+R>>;
x->down();
if(ql<=M) query(x->ch[],L,M);
if(qr>M) query(x->ch[],M+,R);
} return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
inline char readc(){
char x=getchar();
while(!isalpha(x)) x=getchar();
return x;
}
int n,Q;
void init(){
n=read();
for(int i=;i<=n;i++) A[i]=read();
build(root,,n);
return;
}
void work(){
Q=read();char ch;
while(Q--){
ch=readc();ql=read();qr=read();
if(ql>qr) swap(ql,qr);
if(ch=='C'){
cv=read();
update(root,,n);
}
else{
_mi=inf;_mx=-inf;_sm=;
query(root,,n);
printf("MaxNum: %d, MinNum: %d, Sum: %d\n",_mx,_mi,_sm);
}
}
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}