Circular RMQ
You are given circular array a0, a1, ..., an - 1. There are two types of operations with it:
- inc(lf, rg, v) — this operation increases each element on the segment [lf, rg] (inclusively) by v;
- rmq(lf, rg) — this operation returns minimal value on the segment [lf, rg] (inclusively).
Assume segments to be circular, so if n = 5 and lf = 3, rg = 1, it means the index sequence: 3, 4, 0, 1.
Write program to process given sequence of operations.
Input
The first line contains integer n (1 ≤ n ≤ 200000). The next line contains initial state of the array: a0, a1, ..., an - 1 ( - 106 ≤ ai ≤ 106), aiare integer. The third line contains integer m (0 ≤ m ≤ 200000), m — the number of operartons. Next m lines contain one operation each. If line contains two integer lf, rg (0 ≤ lf, rg ≤ n - 1) it means rmq operation, it contains three integers lf, rg, v(0 ≤ lf, rg ≤ n - 1; - 106 ≤ v ≤ 106) — inc operation.
Output
For each rmq operation write result for it. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).
Sample test(s)
input
4 1 2 3 4 4 3 0 3 0 -1 0 1 2 1
output
1 0 0
------------------------------------------------------editorial------------------------
for this problem main thing is how to read input .. in string and convert to range and val for update and range for query
now
since array is circulat .. so
for query
if l<=r normal query
else
query will be in the range o ,r and l to n-1
similarly for update also there are 2 cases
..
-------------------------------------------code----------------------------------------
#include<iostream>
using namespace std;
typedef long long int lli;
lli arr[1010000];
lli tree[1010000];
lli laz[10100000];
#define inf 999999999
#include<bits/stdc++.h>
#include<stdlib.h>
char str[100];
int query(lli node,lli start,lli end,lli r1,lli r2)
{
// cout<<start<<" "<<end<<endl;
if(laz[node])
{
tree[node]+=laz[node];
laz[2*node]+=laz[node];
laz[2*node+1]+=laz[node];
laz[node]=0;
}
if(start>end || r1>end || r2<start) return inf;
if(r1<=start && r2>=end)
{
return tree[node];
}
else
{
lli q1=query(2*node,start,(start+end)/2,r1,r2);
lli q2=query(2*node+1,((start+end)/2)+1,end,r1,r2);
return min(q1,q2);
}
}
void update(lli node ,lli start,lli end,lli r1,lli r2,lli val)
{
if(laz[node]!=0)
{
tree[node]+=laz[node];
laz[2*node+1]+=laz[node];
laz[2*node]+=laz[node];
laz[node]=0;
}
if(r1>end || r2<start || start>end) return ;
if(r1<=start && r2>=end)
{
tree[node]+=val;
if(start!=end)
{
laz[2*node]+=val;
laz[2*node+1]+=val;
}
return ;
}
update(2*node, start,(start+end)/2,r1,r2,val);
update(2*node+1, ((start+end)/2)+1,end,r1,r2,val);
tree[node]=min(tree[2*node],tree[2*node+1]);
}
void build(lli node , lli start,lli end)
{
if(start==end) tree[node]=arr[start];
else if(start>end) return ;
else
{
build(2*node,start,(start+end)/2);
build(2*node+1,((start+end)/2)+1,end);
tree[node]=min(tree[2*node],tree[2*node+1]);
}
}
int main()
{
lli n;
cin>>n;
for(lli i=0;i<n;i++)
cin>>arr[i];
build(1,0,n-1);
lli q;
cin>>q;
char c;
getchar();
while(q--)
{
gets(str);
lli l=strlen(str);
lli cnt=0;
for(lli i=0;i<l;i++)
{
if(str[i]==' ')
{
cnt++;
}
}
if(cnt==1)
{
lli q1=0,q2=0;
lli num=0;
lli b1=0;
for(lli i=0;i<l;i++)
{
if(str[i]==' ')
{
b1=i;
break;
}
}
//cout<<" b is at "<<b1<<endl;
for(lli i=0;i<b1;i++)
{
q1=q1*10+(str[i]-'0');
}
for(lli i=b1+1;i<l;i++)
{
q2=q2*10+(str[i]-'0');
}
// cout<<q1<<"query "<<q2<<endl;
lli a,b;
a=q1;
b=q2;
if(a>b)
{
//cout<<" query in the range "<<a<<" "<<n-1<<" and "<<"0 "<<b<<endl;
lli ans1=query(1,0,n-1,a,n-1);
// cout<<"ans1"<<ans1<<endl;
lli ans2=query(1,0,n-1,0,b);
// cout<<"ans2"<<endl;
cout<<min(ans1,ans2)<<endl;
}
else
{
lli ans1;
// cout<<" query in the range "<<a<<" "<<n-1<<endl;//<<" "<<"0 "<<b<<endl;
ans1=query(1,0,n-1,a,b);
cout<<ans1<<endl;
}
}
else
{
lli q1=0;
lli q2=0;
lli q3=0;
lli f=0;
lli b1,b2;
for(lli i=0;i<l;i++)
{
if(str[i]==' ' && f==0)
{
b1=i;
f=1;
}
else if(str[i]==' ' && f==1)
{
b2=i;
}
}
for(lli i=0;i<b1;i++)
{
q1=q1*10+(str[i]-'0');
}
for(lli i=b1+1;i<b2;i++)
{
q2=q2*10+(str[i]-'0');
}
bool bitfact=0;
for(lli i=b2+1;i<l;i++)
{
if(str[i]=='-')
{
bitfact=1;
}
else
q3=q3*10+(str[i]-'0');
}
if(bitfact==1)
q3=-q3;
// cout<<q1<<" "<<q2<<" "<<q3<<endl;
lli a=q1;
lli b=q2;
lli val=q3;
if(a<=b)
{
// cout<<"update in the range "<<a<<" "<<b<<endl;
update(1,0,n-1,a,b,val);
}
else
{
// cout<<"update in the range "<<a<<" "<<n-1<<" and 0 "<<b<<endl;
update(1,0,n-1,a,n-1,val);
update(1,0,n-1,0,b,val);
}
}
}
return 0;
}
No comments:
Post a Comment