3211: 花神游历各国
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 2549 Solved: 946
[Submit][Status][Discuss]
Description
Input
Output
每次x=1时，每行一个整数，表示这次旅行的开心度
Sample Input
4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
Sample Output
101
11
11
11
11
HINT
对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9
Solution
区间开根号看似十分难处理，实际不妨找规律。data[ i ] 的值最大为109。
( 109 )½ = 105
( ( 109 )½)½ = 103
( ( ( 109 )½ )½ )½ = 102
( ( ( ( 109 )½ )½ )½ )½ = 101
( ( ( ( ( 109 )½ )½ )½ )½ )½ = 1
一个很大的数，五次根号后全部是1，当某个区间的值被开过5次根号，那么该区间所有值都是1.
根据以上结论，不难写出代码。
/**************************************************************
Problem: 3211
User: shadowland
Language: C++
Result: Accepted
Time:1568 ms
Memory:40372 kb
****************************************************************/ #include "bits/stdc++.h" using namespace std ;
typedef long long QAQ ;
struct SegTree { int l , r , sqr ; QAQ sum ; } ;
const int maxN = ; SegTree tr[ maxN << ] ; void Push_up ( const int i ) {
tr[ i ].sum = tr[ i << ].sum + tr[ i << | ].sum ;
} int INPUT ( ) {
int x = , f = ; char ch = getchar ( ) ;
while ( ch < '' || ch > '' ) { if ( ch == '-' ) f = - ; ch = getchar ( ) ; }
while ( ch >= '' && ch <='' ) { x = ( x << ) + ( x << ) + ch - '' ; ch = getchar ( ) ; }
return x * f ;
} void Build_Tree ( const int x , const int y , const int i ) {
tr[ i ].l = x ; tr[ i ].r = y ;
if ( x == y ) tr[ i ].sum = INPUT ( ) ;
else {
int mid = ( tr[ i ].l + tr[ i ].r ) >> ;
Build_Tree ( x , mid , i << ) ;
Build_Tree ( mid + , y , i << | ) ;
Push_up ( i ) ;
}
}
void Update_Tree ( const int q , const int w , const int i ) {
if ( q <= tr[ i ].l && tr[ i ].r <= w ) {
++ tr[ i ].sqr ;
if ( tr[ i ].l == tr[ i ].r ) {
tr[ i ].sum = sqrt ( tr[ i ].sum ) ;
return ;
}
} int mid = ( tr[ i ].l + tr[ i ].r ) >> ;
if ( tr[ i ].sqr <= ) {
if ( q > mid ) Update_Tree ( q , w , i << | ) ;
else if ( w <= mid ) Update_Tree ( q , w , i << ) ;
else {
Update_Tree ( q , w , i << | ) ;
Update_Tree ( q , w , i << ) ;
}
Push_up ( i ) ;
} } QAQ Query_Tree ( const int q , const int w , const int i ) {
if ( q <= tr[ i ].l && tr[ i ].r <= w ) {
return tr[ i ].sum ;
}
else {
int mid = ( tr[ i ].l + tr[ i ].r ) >> ;
if ( q > mid ) return Query_Tree ( q , w , i << | ) ;
else if ( w <= mid ) return Query_Tree ( q , w , i << ) ;
else return Query_Tree ( q , w , i << | ) + Query_Tree ( q , w , i << ) ;
}
} int main ( ) {
int N = INPUT ( ) ;
Build_Tree ( , N , ) ;
int Q = INPUT( ) ;
while ( Q-- ) {
int op = INPUT ( ) ;
if( op == ) {
int l = INPUT( ) , r = INPUT( ) ;
printf ( "%lld\n" , Query_Tree ( l , r , ) ) ;
}
else if ( op == ) {
int l = INPUT ( ) , r = INPUT ( ) ;
Update_Tree ( l , r , ) ;
}
}
return ;
}
2016-10-13 22:10:52
(完)