3211: 花神游历各国
Time Limit: 5 Sec Memory Limit: 128 MB
[
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
Sample Output
101 11 11
HINT
对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9
Source
题意：一棵线段树，资瓷区间求和，区间开根
首先一个区间开根必须一个一个地去开，联想到指数函数增长速度，可以知道一个数开不了几次就会是1，所以对所有不能再开根的打上标记
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 100000 + 5;
int n,m,siz;
int root,ls[N*4],rs[N*4]; bool flag[N*4];
ll a[N],sum[N*4];
void update( int k ){
sum[k] = sum[ls[k]]+sum[rs[k]];
flag[k] = flag[ls[k]]&&flag[rs[k]];
}
void build( int &nd, int l, int r ){
nd = ++siz;
if( l == r ){
sum[nd] = a[l];
if( sum[nd] == 0 || sum[nd] == 1 ) flag[nd] = 1;
return;
}
int mid = (l+r)>>1;
build( ls[nd], l, mid );
build( rs[nd], mid+1, r );
update(nd);
}
void modify( int nd, int l, int r, int L, int R ){
int mid = (l+r)>>1;
if( l == r ){
sum[nd] = (ll)sqrt(sum[nd]);
if( sum[nd] == 0 || sum[nd] == 1 ) flag[nd] = 1;
return;
}
if( L <= mid && !flag[ls[nd]] ) modify( ls[nd], l, mid, L, R );
if( R > mid && !flag[rs[nd]] ) modify( rs[nd], mid+1, r, L, R );
update(nd);
}
ll query( int nd, int l, int r, int L, int R ){
int mid = (l+r)>>1; ll res=0;
if( l >= L && R >= r ) return sum[nd];
if( L <= mid ) res += query( ls[nd], l, mid, L, R );
if( R > mid ) res += query( rs[nd], mid+1, r, L, R );
return res;
}
int main(){
scanf("%d", &n);
for( int i = 1; i <= n; i++ ) scanf("%d", &a[i]);
build( root, 1, n );
scanf("%d", &m);
for( int i = 1,opt,l,r; i <= m; i++ ){
scanf("%d%d%d", &opt, &l, &r);
if( opt == 1 ) printf("%lld\n", query( root, 1, n, l, r ));
if( opt == 2 ) modify( root, 1, n, l, r );
}
return 0;
}
同3038
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 100000 + 5;
int n,m,siz;
int root,ls[N*4],rs[N*4]; bool flag[N*4];
ll a[N],sum[N*4];
void update( int k ){
sum[k] = sum[ls[k]]+sum[rs[k]];
flag[k] = flag[ls[k]]&&flag[rs[k]];
}
void build( int &nd, int l, int r ){
nd = ++siz;
if( l == r ){
sum[nd] = a[l];
if( sum[nd] == 0 || sum[nd] == 1 ) flag[nd] = 1;
return;
}
int mid = (l+r)>>1;
build( ls[nd], l, mid );
build( rs[nd], mid+1, r );
update(nd);
}
void modify( int nd, int l, int r, int L, int R ){
int mid = (l+r)>>1;
if( l == r ){
sum[nd] = (ll)sqrt(sum[nd]);
if( sum[nd] == 0 || sum[nd] == 1 ) flag[nd] = 1;
return;
}
if( L <= mid && !flag[ls[nd]] ) modify( ls[nd], l, mid, L, R );
if( R > mid && !flag[rs[nd]] ) modify( rs[nd], mid+1, r, L, R );
update(nd);
}
ll query( int nd, int l, int r, int L, int R ){
int mid = (l+r)>>1; ll res=0;
if( l >= L && R >= r ) return sum[nd];
if( L <= mid ) res += query( ls[nd], l, mid, L, R );
if( R > mid ) res += query( rs[nd], mid+1, r, L, R );
return res;
}
int main(){
scanf("%d", &n);
for( int i = 1; i <= n; i++ ) scanf("%lld", &a[i]);
build( root, 1, n );
scanf("%d", &m);
for( int i = 1,opt,l,r; i <= m; i++ ){
scanf("%d%d%d", &opt, &l, &r);
if( l > r ) swap( l, r );
if( opt == 1 ) printf("%lld\n", query( root, 1, n, l, r ));
if( opt == 0 ) modify( root, 1, n, l, r );
}
return 0;
}
