Hello everyone. I am solving this problem and I get WA. I use a different approach that any of you talk about in this post. I tried a looot of testcases and they were all incorect. Please check my code. Thanks:)
#include <cstdio>
#include <algorithm>
using namespace std;
struct val {
int f, l;
};
struct n {
int v, c;
};
n tree[ 600000 ];
val array[ 300000 ];
int A[ 200000 ];
void init( int node, int i, int j ) {
if ( i == j ) {
tree[ node ] = ( ( n ) { A[ i ], 1 } );
}
else {
init( node * 2, i, ( i + j ) / 2 );
init( node * 2 + 1, ( i + j ) / 2 + 1, j );
int v1 = tree[ node * 2 ].v, v2 = tree[ node * 2 + 1 ].v, c1 = tree[ node * 2 ].c, c2 = tree[ node * 2 + 1 ].c;
if ( array[ v1 ].l > ( i + j ) / 2 ) {
if ( array[ v1 ].l > j ) {
c1 += j - ( i + j ) / 2;
}
else {
c1 += array[ v1 ].l - ( i + j ) / 2;
}
}
if ( array[ v2 ].f <= ( i + j ) / 2 ) {
if ( array[ v2 ].f < i ) {
c2 += ( i + j ) / 2 - i + 1;
}
else {
c2 += ( i + j ) / 2 + 1 - array[ v2 ].f;
}
}
if ( c1 > c2 ) {
tree[ node ] = ( ( n ) { v1, c1 } );
}
else {
tree[ node ] = ( ( n ) { v2, c2 } );
}
}
}
n query( int node, int a, int b, int l, int r ) {
if ( a > b || a > r || b < l ) {
return ( ( n ) { -1, 0 } );
}
else if ( a >= l && b <= r ) {
return tree[ node ];
}
n p1 = query( node * 2, a, ( a + b ) / 2, l, r );
n p2 = query( node * 2 + 1, ( a + b ) / 2 + 1, b, l, r );
if ( p1.v == -1 ) {
return p2;
}
if ( p2.v == -1 ) {
return p1;
}
if ( array[ p1.v ].l > ( a + b ) / 2 ) {
if ( array[ p1.v ].l > b ) {
p1.c += b - ( a + b ) / 2;
}
else {
p1.c += array[ p1.v ].l - ( a + b ) / 2;
}
}
if ( array[ p2.v ].f <= ( a + b ) / 2 ) {
if ( array[ p2.v ].f < a ) {
p2.c += ( a + b ) / 2 - a + 1;
}
else {
p2.c += ( a + b ) / 2 + 1 - array[ p2.v ].f;
}
}
if ( p1.c > p2.c ) {
return p1;
}
else {
return p2;
}
}
int main() {
int i, j, N, Q, l, r;
while ( 1 ) {
scanf( "%d", &N );
if ( N == 0 ) {
return 0;
}
scanf( "%d", &Q );
for ( i = 0; i <= 250000; ++i ) {
array[ i ] = ( ( val ) { 1000000, -1 } );
}
for ( i = 0; i < N; ++i ) {
scanf( "%d", A + i );
A[ i ] += 100001;
array[ A[ i ] ].f = min( array[ A[ i ] ].f, i );
array[ A[ i ] ].l = max( array[ A[ i ] ].l, i );
}
init( 1, 0, N - 1 );
for ( i = 0; i < Q; ++i ) {
scanf( "%d%d", &l, &r );
printf( "%d\n", query( 1, 0, N - 1, l - 1, r - 1 ).c );
}
}
}
