HDOJ 2688 HDU 2688 Rotate ACM 2688 IN HDU
6695 ワード
MiYuオリジナル、転帖は明記してください:転載は______________白い家 
から
タイトルアドレス:
http://acm.hdu.edu.cn/showproblem.php?pid=2688
タイトルの説明:
RotateTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 250 Accepted Submission(s): 68
Problem Description
Recently yifenfei face such a problem that give you millions of positive integers,tell how many pairs i and j that satisfy F[i] smaller than F[j] strictly when i is smaller than j strictly. i and j is the serial number in the interger sequence. Of course, the problem is not over, the initial interger sequence will change all the time. Changing format is like this [S E] (abs(E-S)<=1000) that mean between the S and E of the sequece will Rotate one times.
For example initial sequence is 1 2 3 4 5.
If changing format is [1 3], than the sequence will be 1 3 4 2 5 because the first sequence is base from 0.
Input
The input contains multiple test cases.
Each case first given a integer n standing the length of integer sequence (2<=n<=3000000)
Second a line with n integers standing F[i](0Third a line with one integer m (m < 10000)
Than m lines quiry, first give the type of quiry. A character C, if C is ‘R’ than give the changing format, if C equal to ‘Q’, just put the numbers of satisfy pairs.
Output
Output just according to said.
Sample Input
Sample Output
暴力であれば、一度も更新しないで計算し直すと、時間的な費用が非常に大きくなります.データを解析すると、回転するとき、最初の数を除いて、他の数の対数の数値がこの数に関係していることがわかるので、まず全体の対数sumを算出し、回転するときの各数と最初の数の大きさを比較してsumを更新すればよい.コードは次のとおりです.
コード#コード#
/*
MiYuオリジナル、転帖は明記してください:転載は_______白い家
http://www.cnblog.com/MiYu
Author By : MiYuTest : 1Program : 2688
*/
#include
<
iostream
>
#include
<
algorithm
>
using
namespace
std;
const
int
MAX
=
10000
;
int
nCount
=
0
, N, M, x , y;
int
com[MAX
+
1
], num[
300
*
MAX
+
1
];
long
long
sum
=
0
;
char
ask[
5
];inline
int
low (
int
x ) {
return
x
&
(
-
x );}
void
modify (
int
x,
int
val ){
//
変更
while
( x
<=
MAX ){ com[x]
+=
val; x
+=
low ( x ); } }
int
quy (
int
x ){
//
検索
int
sum
=
0
;
while
( x
>
0
){ sum
+=
com[x]; x
^=
low ( x ); }
return
sum ;}inline
bool
scan_d(
int
&
num)
//
入力
{
char
in
;
bool
IsN
=
false
;
in
=
getchar();
if
(
in
==
EOF)
return
false
;
while
(
in
!=
'
-
'
&&
(
in
<
'
0
'
||
in
>
'
9
'
))
in
=
getchar();
if
(
in
==
'
-
'
){ IsN
=
true
;num
=
0
;}
else
num
=
in
-
'
0
'
;
while
(
in
=
getchar(),
in
>=
'
0
'
&&
in
<=
'
9
'
){ num
*=
10
,num
+=
in
-
'
0
'
; }
if
(IsN) num
=-
num;
return
true
;}
int
main (){
while
( scan_d ( N ) ){ memset ( com,
0
,
sizeof
( com ) ); sum
=
0
;
for
(
int
i
=
0
; i
<
N;
++
i ){ scan_d ( num[i] ); modify ( num[i],
1
); sum
+=
quy ( num[i]
-
1
); } scan_d ( M );
while
( M
--
){ scanf (
"
%s
"
,ask );
int
temp;
switch
( ask[
0
] ){
case
'
Q
'
: cout
<<
sum
<<
endl;
break
;
case
'
R
'
: scan_d ( x ), scan_d ( y ); temp
=
num[x];
while
( x
<
y ) { num[x]
=
num[x
+
1
]; num[x]
>
temp
?
sum
--
: num[x]
==
temp
?
: sum
++
; x
++
; } num[y]
=
temp;
break
; } } }
return
0
;}
からタイトルアドレス:
http://acm.hdu.edu.cn/showproblem.php?pid=2688
タイトルの説明:
RotateTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 250 Accepted Submission(s): 68
Problem Description
Recently yifenfei face such a problem that give you millions of positive integers,tell how many pairs i and j that satisfy F[i] smaller than F[j] strictly when i is smaller than j strictly. i and j is the serial number in the interger sequence. Of course, the problem is not over, the initial interger sequence will change all the time. Changing format is like this [S E] (abs(E-S)<=1000) that mean between the S and E of the sequece will Rotate one times.
For example initial sequence is 1 2 3 4 5.
If changing format is [1 3], than the sequence will be 1 3 4 2 5 because the first sequence is base from 0.
Input
The input contains multiple test cases.
Each case first given a integer n standing the length of integer sequence (2<=n<=3000000)
Second a line with n integers standing F[i](0
Than m lines quiry, first give the type of quiry. A character C, if C is ‘R’ than give the changing format, if C equal to ‘Q’, just put the numbers of satisfy pairs.
Output
Output just according to said.
Sample Input
5
1 2 3 4 5
3
Q
R 1 3
Q
Sample Output
10
8
暴力であれば、一度も更新しないで計算し直すと、時間的な費用が非常に大きくなります.データを解析すると、回転するとき、最初の数を除いて、他の数の対数の数値がこの数に関係していることがわかるので、まず全体の対数sumを算出し、回転するときの各数と最初の数の大きさを比較してsumを更新すればよい.コードは次のとおりです.
コード#コード#
/*
MiYuオリジナル、転帖は明記してください:転載は_______白い家
http://www.cnblog.com/MiYu
Author By : MiYuTest : 1Program : 2688
*/
#include
<
iostream
>
#include
<
algorithm
>
using
namespace
std;
const
int
MAX
=
10000
;
int
nCount
=
0
, N, M, x , y;
int
com[MAX
+
1
], num[
300
*
MAX
+
1
];
long
long
sum
=
0
;
char
ask[
5
];inline
int
low (
int
x ) {
return
x
&
(
-
x );}
void
modify (
int
x,
int
val ){
//
変更
while
( x
<=
MAX ){ com[x]
+=
val; x
+=
low ( x ); } }
int
quy (
int
x ){
//
検索
int
sum
=
0
;
while
( x
>
0
){ sum
+=
com[x]; x
^=
low ( x ); }
return
sum ;}inline
bool
scan_d(
int
&
num)
//
入力
{
char
in
;
bool
IsN
=
false
;
in
=
getchar();
if
(
in
==
EOF)
return
false
;
while
(
in
!=
'
-
'
&&
(
in
<
'
0
'
||
in
>
'
9
'
))
in
=
getchar();
if
(
in
==
'
-
'
){ IsN
=
true
;num
=
0
;}
else
num
=
in
-
'
0
'
;
while
(
in
=
getchar(),
in
>=
'
0
'
&&
in
<=
'
9
'
){ num
*=
10
,num
+=
in
-
'
0
'
; }
if
(IsN) num
=-
num;
return
true
;}
int
main (){
while
( scan_d ( N ) ){ memset ( com,
0
,
sizeof
( com ) ); sum
=
0
;
for
(
int
i
=
0
; i
<
N;
++
i ){ scan_d ( num[i] ); modify ( num[i],
1
); sum
+=
quy ( num[i]
-
1
); } scan_d ( M );
while
( M
--
){ scanf (
"
%s
"
,ask );
int
temp;
switch
( ask[
0
] ){
case
'
Q
'
: cout
<<
sum
<<
endl;
break
;
case
'
R
'
: scan_d ( x ), scan_d ( y ); temp
=
num[x];
while
( x
<
y ) { num[x]
=
num[x
+
1
]; num[x]
>
temp
?
sum
--
: num[x]
==
temp
?
: sum
++
; x
++
; } num[y]
=
temp;
break
; } } }
return
0
;}