## 12299 - RMQ with Shifts

All about problems in Volume 122. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

fR0D
New poster
Posts: 29
Joined: Mon Feb 11, 2008 5:59 am
Contact:

### 12299 - RMQ with Shifts

What is wrong with my code for 12299 - RMQ with Shifts?

Code: Select all

``````#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<string>

using namespace std;

typedef vector<int> VI;

#define REP(i,N) for(int i=0; i<(N); ++i)
#define FOREACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)

#define PB push_back

template<class T>
class SegmentTree
{
int *A,size;
public:
SegmentTree(int N)
{
size = 1;
while(size < N) size *= 2;
size *= 2;
size -= 1;
A = new int[size];
memset(A,-1,4*size);
}
void initialize(int node, int start,int end, T *array)
{
if (start==end)
A[node] = start;
else
{
int mid = (start+end)/2;
initialize(2*node+1,start,mid,array);
initialize(2*node+2,mid+1,end,array);
if (array[A[2*node+1]]<=array[A[2*node+2]])
A[node] = A[2 * node + 1];
else
A[node] = A[2 * node + 2];
}
}
void update(int node, T *array) {
int index = size/2 + node;
//
node = (index - 1 ) / 2;
while( A[2 * node + 1] == -1 || A[2 * node + 2] == -1) node = (node - 1)/2;
while (node >= 0) {
if (array[A[2*node+1]]<=array[A[2*node+2]])
A[node] = A[2 * node + 1];
else
A[node] = A[2 * node + 2];
if(node == 0) break;
node = (node - 1) / 2;
}
}
int query(int node, int start,
int end, int i, int j, T *array)
{
int id1,id2;
if (i>end || j<start)
return -1;

if (start>=i && end<=j)
return A[node];

int mid = (start+end)/2;
id1 = query(2*node+1,start,mid,i,j,array);
id2 = query(2*node+2,mid+1,end,i,j,array);

if (id1==-1)
return id2;
if (id2==-1)
return id1;

if (array[id1]<=array[id2])
return id1;
else
return id2;
}
};

int main()
{
int n, q, a, b, j, k;
scanf("%d%d",&n,&q);
int *A = new int[n];
REP(i,n) scanf("%d",&A[i]);
SegmentTree<int> s(n);

s.initialize(0,0,n-1,A);
char str[100];
getchar();
REP(i,q) {
gets(str);
if(str[0]=='q') {
j = 0;
while(!isdigit(str[j])) j++;

a = str[j] - '0';
j++;
while(isdigit(str[j])) {
a = a * 10 + str[j] - '0';
++j;
}

j++;
b = str[j] - '0';
j++;
while(isdigit(str[j])) {
b = b * 10 + str[j] - '0';
++j;
}
printf("%d\n",A[s.query(0,0,n-1,a-1,b-1,A)]);
}
else {
VI ind;
VI value;
j = 5;
while(1) {
if(str[j] == ')') break;
j++;
a = 0;
while(isdigit(str[j])) {
a = a * 10 + str[j] - '0';
++j;
}
ind.PB(a-1);
value.PB(A[a-1]);
}
j = 1;
k = ind.size();
FOREACH(it, ind) {
A[*it] = value[j % k];
s.update(*it, A);
++j;
}
}
}
}
``````