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;
}