3211: 花神游历各国
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 3628 Solved: 1326
[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
/*
线段树区间开根，区间求和
以为一个一个开根很耗时间，所以要优化
想到一个数开几次根就到一了，所以用个flag记录当前是否是0或1
是的话就 return 快很多。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath> #define N 100010
#define ll long long using namespace std;
ll n,m,ans;
struct tree
{
ll l,r,sum;
bool flag;
}tr[N<<]; inline ll read()
{
ll x=,f=;char c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} inline void pushup(ll k)
{
tr[k].sum=tr[k<<].sum+tr[k<<|].sum;
tr[k].flag=tr[k<<].flag&tr[k<<|].flag;
} void build(ll k,ll l,ll r)
{
tr[k].l=l;tr[k].r=r;tr[k].sum=;
if(l==r)
{
tr[k].sum=read();
if(tr[k].sum== || tr[k].sum==) tr[k].flag=;
return;
}
ll mid=(tr[k].r+tr[k].l)>>;
build(k<<,l,mid);build(k<<|,mid+,r);
pushup(k);
} void change(ll k,ll l,ll r)
{
if(tr[k].flag) return;
if(tr[k].l==tr[k].r)
{
tr[k].sum=(ll) sqrt(tr[k].sum);
if(tr[k].sum== || tr[k].sum==) tr[k].flag=;
return;
}
ll mid=(tr[k].l+tr[k].r)>>;
if(r<=mid) change(k<<,l,r);
else if(l>mid) change(k<<|,l,r);
else change(k<<,l,mid),change(k<<|,mid+,r);
pushup(k);
} ll query(ll k,ll l,ll r)
{
if(tr[k].l==l && tr[k].r==r)
return tr[k].sum;
pushup(k);
ll mid=(tr[k].r+tr[k].l)>>;
if(r<=mid) return query(k<<,l,r);
else if(l>mid) return query(k<<|,l,r);
else return query(k<<,l,mid)+query(k<<|,mid+,r);
} int main()
{
long long x,y,z;
n=read();build(,,n);
m=read();
while(m--)
{
x=read();y=read();z=read();
if(y>z) swap(y,z);
if(x==) printf("%lld\n",query(,y,z));
else change(,y,z);
}
return ;
}