电脑制作网站总么做/天津网站seo设计

题目

n(n<=1e5)个数，m(m<=1e5)次操作，题目保证小于

操作分两种，

1 对[l,r]暴力开根一次

2 询问[l,r]的和

思路来源

傅老师

题解

暴力开根，维护整个区间有没有被开成1

如果被开成1了就不往子区间开了，

注意到1e18的数开个6次，就被开成1了，

复杂度大概是O(6*n)叭

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
ll a[maxn];
ll sum[maxn*5];
bool ok[maxn*5];//该区间是否整个区间都被开根为1
int cas,n,m;
int op,l,r;
void pushup(int p)
{sum[p]=sum[p<<1]+sum[p<<1|1];ok[p]=ok[p<<1]&ok[p<<1|1];
}
void build(int p,int l,int r)
{sum[p]=ok[p]=0; if(l==r){sum[p]=a[l];if(sum[p]==1)ok[p]=1;else ok[p]=0;return;}int mid=(l+r)/2;build(p<<1,l,mid);build(p<<1|1,mid+1,r);pushup(p);
}  
void update(int p,int l,int r,int ql,int qr)
{if(ok[p])return;//整个区间都被开成1了 if(l==r){sum[p]=sqrt(sum[p]);if(sum[p]==1)ok[p]=1;else ok[p]=0;return;}int mid=(l+r)/2;if(ql<=mid)update(p<<1,l,mid,ql,qr);if(qr>mid)update(p<<1|1,mid+1,r,ql,qr);pushup(p);
}
ll ask(int p,int l,int r,int ql,int qr)
{if(ql<=l&&r<=qr)return sum[p];ll ans=0;int mid=(l+r)/2;if(ql<=mid)ans+=ask(p<<1,l,mid,ql,qr);if(qr>mid)ans+=ask(p<<1|1,mid+1,r,ql,qr);return ans;
}
int main()
{while(~scanf("%d",&n)){for(int i=1;i<=n;++i)scanf("%lld",&a[i]);build(1,1,n);scanf("%d",&m); printf("Case #%d:\n",++cas);for(int i=1;i<=m;++i){scanf("%d%d%d",&op,&l,&r);if(l>r)swap(l,r);if(op==0)update(1,1,n,l,r);else printf("%lld\n",ask(1,1,n,l,r));}puts("");}return 0;
}