【bzoj3211】花神游历各国
Description
.jpg)
Input
.jpg)
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
题解
这道题目记录，因为一个数经过较少的次数就会被开根号到1；
所以势能分析即可，
最坏情况是O（log * 10^9 m）
1 #include<cstring> 2 #include<cmath> 3 #include<algorithm> 4 #include<iostream> 5 #include<cstdio> 6 7 #define N 100007 8 #define ll long long 9 using namespace std; 10 inline int read() 11 { 12 int x=0,f=1;char ch=getchar(); 13 while(ch>'9'||ch<'0'){if (ch=='-') f=-1;ch=getchar();} 14 while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 int n,m; 18 ll a[N]; 19 struct data 20 { 21 int l,r; 22 ll sum; 23 bool flag; 24 }tr[N<<2]; 25 26 inline void update(int p) 27 { 28 tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum; 29 tr[p].flag=tr[p<<1].flag&tr[p<<1|1].flag; 30 } 31 void build(int p,int l,int r) 32 { 33 tr[p].l=l;tr[p].r=r; 34 if(l==r) 35 { 36 tr[p].sum=a[l]; 37 if(a[l]==1||a[l]==0)tr[p].flag=1; 38 return; 39 } 40 int mid=(l+r)>>1; 41 build(p<<1,l,mid),build(p<<1|1,mid+1,r); 42 update(p); 43 } 44 void modify(int p,int x,int y) 45 { 46 if(tr[p].flag)return; 47 int l=tr[p].l,r=tr[p].r; 48 if(l==r) 49 { 50 tr[p].sum=(ll)sqrt(tr[p].sum); 51 if(tr[p].sum==1||tr[p].sum==0)tr[p].flag=1; 52 return; 53 } 54 int mid=(l+r)>>1; 55 if(mid>=y) modify(p<<1,x,y); 56 else if(mid<x) modify(p<<1|1,x,y); 57 else modify(p<<1,x,mid),modify(p<<1|1,mid+1,y); 58 update(p); 59 } 60 ll query(int p,int x,int y) 61 { 62 int l=tr[p].l,r=tr[p].r; 63 if(l==x&&r==y)return tr[p].sum; 64 int mid=(l+r)>>1; 65 if(mid>=y)return query(p<<1,x,y); 66 else if(mid<x)return query(p<<1|1,x,y); 67 else return query(p<<1,x,mid)+query(p<<1|1,mid+1,y); 68 } 69 int main() 70 { 71 n=read(); 72 for(int i=1;i<=n;i++) 73 a[i]=read(); 74 build(1,1,n); 75 m=read(); 76 for(int i=1;i<=m;i++) 77 { 78 int k=read(),x=read(),y=read(); 79 if(x>y)swap(x,y); 80 if(k==2 )modify(1,x,y); 81 else printf("%lld ",query(1,x,y)); 82 } 83 }