一、题目
1、原题链接
3805. 环形数组
2、题目描述
给定一个长度为 n 的环形数组 a0,a1,…,an−1。
现在要对该数组进行 m 次操作。
操作分为以下两种：
增值操作 l r d，将区间 [l,r] 上的每个元素都增加 d。
求最小值操作 l r，输出区间 [l,r] 内的所有元素的最小值。
注意，数组是环形的，所以当 n=5 时，区间 [3,1] 内的所有元素依次为 a3,a4,a0,a1。
输入格式
第一行包含整数 n，表示数组长度。
第二行包含 n 个整数，表示 a0,a1,…,an−1。
第三行包含整数 m，表示操作数。
接下来 m 行，每行描述一个操作，对于第 i 行，如果包含两个整数 l,r，则表示第 i 个操作为求最小值操作；如果包含三个整数
l,r,d，则表示第 i 个操作为增值操作。
输出格式
每个求最小值操作输出一行结果。
数据范围
前三个测试点满足 1≤n,m≤10。
所有测试点满足 1≤n≤2×105，0≤m≤2×105，−106≤ai≤106，0≤l,r≤n−1，−106≤d≤106。
输入样例：
4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1
输出样例：
1
0
0
二、解题报告
1、思路分析
思路来源：y总讲解视频
y总yyds
（1）针对环形的处理：如果输入的区间的右端点小于左端点，则将区间分为两段：[0,左端点]和[右端点,n]；如果输入区间的右端点大于等于左端点正常处理即可。
（2）处理输入问题：读取第二个输入的数的后面的字符，如果输入为\n则说明输入两个数，执行求最小值操作；否则，则执行增值操作。（注意cin不读取空格，需要使用scanf进行读取）。
（3）利用线段树模版进行求解。（详见y总讲解视频）
2、时间复杂度
时间复杂度为O(nlogn)
3、代码详解
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL; //注意数据范围，要开long long
const int N=200010;
int n,m;
int w[N]; //w[]代表初始每个点的值
//线段树结点
struct Node{
int l,r; //l,r分别代表当前节点区间左端点和右端点
LL dt,mn; //dt代表当前区间要加多少值，mn代表当前区间最小值
}tr[N*4]; //线段树数组要开四倍
void pushup(int u){
tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);
}
void pushdown(int u){
auto &root=tr[u],&l=tr[u<<1],&r=tr[u<<1|1];
l.dt+=root.dt,l.mn+=root.dt;
r.dt+=root.dt,r.mn+=root.dt;
root.dt=0;
}
//构建线段树
void build(int u,int l,int r){
if(l==r) tr[u]={l,r,0,w[r]};
else{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void update(int u,int l,int r,int d){
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].dt+=d,tr[u].mn+=d;
}
else{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) update(u<<1,l,r,d);
if(r>mid) update(u<<1|1,l,r,d);
pushup(u);
}
}
LL query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mn;
else{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
LL res=1e18;
if(l<=mid) res=min(res,query(u<<1,l,r));
if(r>mid) res=min(res,query(u<<1|1,l,r));
return res;
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>w[i];
build(1,0,n-1);
cin>>m;
while(m--){
int l,r;
char c;
scanf("%d %d%c",&l,&r,&c); //cin不接收空格
if(c=='\n'){
if(l<=r) cout<<query(1,l,r)<<endl;
else cout<<min(query(1,0,r),query(1,l,n-1))<<endl;
}
else{
int d;
cin>>d;
if(l<=r) update(1,l,r,d);
else update(1,0,r,d),update(1,l,n-1,d);
}
}
return 0;
}
三、知识风暴
线段树
