3038: 上帝造题的七分钟2/3211: 花神游历各国

题目链接

题目大意：维护序列，致辞区间开根号，求和

题解：由于普通的加/乘法标记利用的是区间更新的量相同的特点，开根号无法使用这样的打标记方法。暴力出奇迹……显然不能直接修改一条线段，而是应该修改叶子，用tag[x]=1表示x不需要修改(为0或1)，上传这个标记，遇到tag[x]等于1时直接return。考虑到开根号次数大概是loglog级的，于是跑得飞快

我的收获：加深了对标记上/下传的理解

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

#define M 100005
#define ls x<<1
#define rs x<<1|1
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
#define root 1,n,1

int n,m;
bool tag[M<<2];
long long a[M],sum[M<<2];

inline void pushup(int x){sum[x]=sum[ls]+sum[rs];tag[x]=tag[ls]&&tag[rs];}

void build(int l,int r,int x)
{
    tag[x]=0;
if(l==r){sum[x]=a[l];return ;}
int m=(l+r)>>1;
    build(lson);build(rson);
    pushup(x);
}

void updata(int L,int R,int l,int r,int x)
{
if(tag[x]) return ;
if(l==r){sum[x]=sqrt(sum[x]);if(sum[x]==0||sum[x]==1) tag[x]=1;return ;}//只修改叶子，向上传递标记 
int m=(l+r)>>1;
if(L<=m) updata(L,R,lson);
if(R>m) updata(L,R,rson);
    pushup(x);
}

long long query(int L,int R,int l,int r,int x) 
{
if(L<=l&&r<=R) return sum[x];
int m=(l+r)>>1;long long ans=0;
if(L<=m) ans+=query(L,R,lson);
if(R>m) ans+=query(L,R,rson);
return ans;
}

void work()
{
int opt,x,y;
for(int i=1;i<=m;i++)
    {
scanf("%d%d%d",&opt,&x,&y);
if(x>y) swap(x,y);
if(opt==1) printf("%lld\n",query(x,y,root));
else updata(x,y,root);
    }
}

void init()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
     build(root);
scanf("%d",&m);
}

int main()
{
    init();
    work();
return 0;
}