首页 技术 正文
技术 2022年11月23日
0 收藏 554 点赞 2,989 浏览 2525 个字

题目:https://www.luogu.org/problemnew/show/P4145

区间开平方,可以发现其实开几次就变成1,不需要开了,所以标记一下,每次只去开需要开的地方;

原来写的并查集跳过1或0,然而WA…其实是没有记录原数组的值,因为树状数组存的是修改量;

(如果a数组<原数组>开int会RE!)

改成线段树,本来想着是这一段区间和只要小于等于其长度就可以跳过了,然而仔细想想完全不是,应为可能有多个0什么的;

所以直接开bool数组标记一下就好了;

不需要pushdown,直接去修改或是跳过。

并查集:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
int const MAXN=;
int n,m,a[MAXN],fa[MAXN];
ll f[MAXN];
int find(int x)
{
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
void add(int x,ll y)
{
for(;x<=n;x+=(x&-x))
f[x]+=y;
}
void update(int x)
{
int tmp=a[x];
a[x]=sqrt(a[x]);
if(a[x]==||a[x]==)fa[x]=find(x+);
add(x,a[x]-tmp);
// for(;x<=n;x+=(x&-x))
// f[x]-=tmp,f[x]+=a[x];
}
ll query(int x)
{
// for(int i=1;i<=n;i++)
// printf("%d ",a[i]);
// printf("\n");
ll sum=;
for(;x;x-=(x&-x))
sum+=f[x];
return sum;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
fa[i]=i;
add(i,a[i]);
}
// for(int i=1;i<=n;i++)
// printf("%lld ",f[i]);
// printf("\n");
fa[n+]=n+;
scanf("%d",&m);
while(m--)
{
int t,l,r;
scanf("%d%d%d",&t,&l,&r);
if(l>r)swap(l,r);
if(t==)
{
int x=find(l);
while(x<=r)
{
update(x);
x=find(x+);
// cout<<x<<endl;
}
}
if(t==)
{
ll s1=,s2=;
if(l-)s1=query(l-);
s2=query(r);
// printf("s1=%lld s2=%lld\n",s1,s2);
printf("%lld\n",s2-s1);
}
}
return ;
}

代码如下:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
int const MAXN=;
int n,m;
ll tr[MAXN<<],a[MAXN];
bool tg[MAXN<<];
void pushup(int nw)
{
tr[nw]=tr[nw<<]+tr[nw<<|];
tg[nw]=(tg[nw<<]&&tg[nw<<|]);
}
//void pushdown(int l,int r,int nw)
//{
// if(l==r)
// {
// tr[nw]=sqrt(tr[nw]);
// return;
// }
// while(lz[nw])
// {
// if(tr[nw]<=r-l+1)
// {
// lz[nw]=0;
// break;
// }
// int mid=((l+r)>>1);
// if(tr[nw<<1]>mid-l+1)pushdown(l,mid,nw<<1);
// if(tr[nw<<1|1]>r-mid)pushdown(mid+1,r,nw<<1|1);
// pushup(nw);
// lz[nw]--;
// }
//}
void update(int l,int r,int L,int R,int nw)
{
if(tg[nw])return;
if(l==r)
{
tr[nw]=(ll)sqrt(tr[nw]);
if(tr[nw]==||tr[nw]==)tg[nw]=;
return;
}
int mid=((l+r)>>);
if(mid>=L)update(l,mid,L,R,nw<<);
if(mid<R)update(mid+,r,L,R,nw<<|);
pushup(nw);
}
ll query(int l,int r,int L,int R,int nw)
{
// for(int i=1;i<=n;i++)
// printf("%d ",a[i]);
// printf("\n");
ll sum=;
if(l>=L&&r<=R)
{
// pushdown(l,r,nw);
return tr[nw];
}
int mid=((l+r)>>);
if(mid>=L)sum+=query(l,mid,L,R,nw<<);
if(mid<R)sum+=query(mid+,r,L,R,nw<<|);
return sum;
}
void build(int l,int r,int nw)
{
if(l==r)
{
tr[nw]=a[l];
if(a[l]==||a[l]==)tg[nw]=;
return;
}
int mid=((l+r)>>);
build(l,mid,nw<<);
build(mid+,r,nw<<|);
pushup(nw);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lld",&a[i]);
scanf("%d",&m);
build(,n,);
while(m--)
{
int d,x,y;
scanf("%d%d%d",&d,&x,&y);
if(x>y)swap(x,y);
if(d==)update(,n,x,y,);
if(d==)printf("%lld\n",query(,n,x,y,));
}
return ;
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,254
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,692
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,531
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,302
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,942
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,102