Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 52 Solved: 24
[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
SPOJ2713 數據已加強
不用猶豫，本題正宗線段樹。
不過線段樹不支持區間開方，但是10^9最多開5次方就到1了-_-
所以暴力改也就MAXN*5 無壓力。
用線段樹存儲一段是否需要開方（2-需要,1-不用)+暴力改
無壓力
[cpp] #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MAXN (200000+10)
#define MAXM (400000+10)
#define Lson (x<<1)
#define Rson ((x<<1)+1)
int n,m,a[MAXN*2]={0},b[MAXN*2]={0};
long long sum[MAXN*2];
void update(int x)
{
if (b[Lson]==2||b[Rson]==2) b[x]=2;
else b[x]=1;
sum[x]=sum[Lson]+sum[Rson];
}
void build(int x,int l,int r)
{
if (l==r)
{
scanf("%d",&a[x]);sum[x]=a[x];
if (a[x]<=1) b[x]=1;
else b[x]=2;
}
if (l>=r) return;
int m=(l+r)>>1;
build(Lson,l,m);
build(Rson,m+1,r);
update(x);
}
void pushdown(int x,int l,int r)
{
if (b[x]<=1) return;
if (l==r)
{
a[x]=sum[x]=sqrt(a[x]);
if (a[x]<=1) b[x]=1;
return;
}
int m=(l+r)>>1;
pushdown(Lson,l,m);
if (m<r) pushdown(Rson,m+1,r);
update(x);
}
void change(int x,int l,int r,int L,int R)
{
if (b[x]<=1) return;
int m=(l+r)>>1;
if (L<=l&&r<=R)
{
pushdown(x,l,r);
return;
}
if (L<=m) change(Lson,l,m,L,R);
if (m<R) change(Rson,m+1,r,L,R);
update(x);
}
long long qur(int x,int l,int r,int L,int R)
{
int m=(l+r)>>1;
if (L<=l&&r<=R)
{
return sum[x];
}
long long ans=0;
if (L<=m) ans+=qur(Lson,l,m,L,R);
if (m<R) ans+=qur(Rson,m+1,r,L,R);
return ans;
}
int main()
{
// freopen("bzoj3211.in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d",&n);
build(1,1,n);
scanf("%d",&m);
For(i,m)
{
int x,l,r;
scanf("%d%d%d",&x,&l,&r);
if (x==1) printf("%lld\n",qur(1,1,n,l,r));
else change(1,1,n,l,r);
}
return 0;
}
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MAXN (200000+10)
#define MAXM (400000+10)
#define Lson (x<<1)
#define Rson ((x<<1)+1)
int n,m,a[MAXN*2]={0},b[MAXN*2]={0};
long long sum[MAXN*2];
void update(int x)
{
if (b[Lson]==2||b[Rson]==2) b[x]=2;
else b[x]=1;
sum[x]=sum[Lson]+sum[Rson];
}
void build(int x,int l,int r)
{
if (l==r)
{
scanf("%d",&a[x]);sum[x]=a[x];
if (a[x]<=1) b[x]=1;
else b[x]=2;
}
if (l>=r) return;
int m=(l+r)>>1;
build(Lson,l,m);
build(Rson,m+1,r);
update(x);
}
void pushdown(int x,int l,int r)
{
if (b[x]<=1) return;
if (l==r)
{
a[x]=sum[x]=sqrt(a[x]);
if (a[x]<=1) b[x]=1;
return;
}
int m=(l+r)>>1;
pushdown(Lson,l,m);
if (m<r) pushdown(Rson,m+1,r);
update(x);
}
void change(int x,int l,int r,int L,int R)
{
if (b[x]<=1) return;
int m=(l+r)>>1;
if (L<=l&&r<=R)
{
pushdown(x,l,r);
return;
}
if (L<=m) change(Lson,l,m,L,R);
if (m<R) change(Rson,m+1,r,L,R);
update(x);
}
long long qur(int x,int l,int r,int L,int R)
{
int m=(l+r)>>1;
if (L<=l&&r<=R)
{
return sum[x];
}
long long ans=0;
if (L<=m) ans+=qur(Lson,l,m,L,R);
if (m<R) ans+=qur(Rson,m+1,r,L,R);
return ans;
}
int main()
{
// freopen("bzoj3211.in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d",&n);
build(1,1,n);
scanf("%d",&m);
For(i,m)
{
int x,l,r;
scanf("%d%d%d",&x,&l,&r);
if (x==1) printf("%lld\n",qur(1,1,n,l,r));
else change(1,1,n,l,r);
}
return 0;
}
