CF52C Circular RMQ
题意翻译
【题目大意】
给定一个环形数列 a0,a1,…,an−1a_0,a_1,\dots,a_{n-1}a0,a1,…,an−1。
现在有 222 种操作：
- inc(lf,rg,v)\operatorname{inc}(lf,rg,v)inc(lf,rg,v)：将区间 [lf,rg][lf,rg][lf,rg] 中的每个数增加 vvv。
- rmq(lf,rg)\operatorname{rmq}(lf,rg)rmq(lf,rg)：求出区间 [lf,rg][lf,rg][lf,rg] 中的最小值。
因为数列是环形的，所以当 n=5n=5n=5，lf=3lf=3lf=3，rg=1rg=1rg=1 时，表示的区间下标为 3,4,0,13,4,0,13,4,0,1。
Translated by 小恐。
【输入】
第一行有一个整数 nnn。
第二行为数列的初始状态 a0,a1,…,an−1a_0,a_1,\dots,a_{n-1}a0,a1,…,an−1，aia_iai 是整数。
第三行有一个整数 mmm，表示操作次数。
接下来m行每行为一个操作。如果该行有两个整数 lflflf，rgrgrg 表示 rmq\operatorname{rmq}rmq 操作，如果该行有三个整数 lflflf，rgrgrg，vvv 表示 inc\operatorname{inc}inc 操作。
【输出】
对于每个 rmq\operatorname{rmq}rmq 操作输出一行答案。
题解：
环形区间RMQ。就像题意说的那样。
带修。
不难，就是断环成链即可。
但是这个断环成链就不是我们常用的二倍区间了。就是把询问区间拆开。
灵活处理即可。
线段树的讲解有不会的可以去翻我的博客。
上代码了：
#include<bits/stdc++.h>
using namespace std;
#define Maxn 1000010
typedef long long ll;
struct node
{
ll data,l,r,Min,add;
}t[4*Maxn];
ll a[Maxn],n,m,len,b[10],space=0;
ll read()
{
ll res=0,f=1;
char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
while (isdigit(c)) res=res*10+c-48,c=getchar();
if (c==' ') ++space;
return res*f;
}
void build(ll p,ll l,ll r)
{
t[p].l=l; t[p].r=r; t[p].add=0;
if (l==r) {
t[p].data=a[l];
t[p].Min=a[l];
return ;
}
ll mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
t[p].data=t[p*2].data+t[p*2+1].data;
t[p].Min=min(t[p*2].Min,t[p*2+1].Min);
}
void pushdown(ll p)
{
t[p*2].data+=(t[p*2].r-t[p*2].l+1)*t[p].add;
t[p*2].Min+=t[p].add;
t[p*2].add+=t[p].add;
t[p*2+1].data+=(t[p*2+1].r-t[p*2+1].l+1)*t[p].add;
t[p*2+1].Min+=t[p].add;
t[p*2+1].add+=t[p].add;
t[p].add=0;
}
void change(ll p,ll x,ll y,ll k)
{
if (t[p].l>=x&&t[p].r<=y) {
t[p].data+=(t[p].r-t[p].l+1)*k;
t[p].Min+=k;
t[p].add+=k;
return ;
}
pushdown(p);
ll mid=(t[p].l+t[p].r)/2;
if (x<=mid) change(p*2,x,y,k);
if (mid<y) change(p*2+1,x,y,k);
t[p].data=t[p*2].data+t[p*2+1].data;
t[p].Min=min(t[p*2].Min,t[p*2+1].Min);
}
ll query(ll p,ll x,ll y)
{
if (t[p].l>=x&&t[p].r<=y) return t[p].Min;
pushdown(p);
ll ans=1e16,mid=(t[p].l+t[p].r)/2;
if (x<=mid) ans=min(ans,query(p*2,x,y));
if (mid<y) ans=min(ans,query(p*2+1,x,y));
return ans;
}
int main()
{
cin>>n;
for(ll i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
cin>>m;
for(ll i=1;i<=m;i++)
{
ll l,r,k;
space=0;
l=read();r=read();++l;++r;
if (space==2)
{
k=read();
if (l<=r)
change(1,l,r,k);
else
{
change(1,l,n,k);
change(1,1,r,k);
}
}
else
{
if (l<=r)
cout<<query(1,l,r)<<endl;
else
cout<<min(query(1,l,n),query(1,1,r))<<endl;
}
}
return 0;
}