Bakser's Blog

我是逗比。

bzoj3038&bzoj3211 奇特的线段树

| Comments

果然不刷动态树以后变得愉悦了许多。
好吧基本上都在颓废。
这题应该属于一种奇特的lazy-tag?
到1以后就不可能再变了,记录下来即可。
两道题几乎是一样的,双倍经验分外爽。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
#define N 100100
struct hh
{
    LL val;
    bool flag; 
}tree[N<<2];
inline void push_up(int x)
{
    tree[x].val=tree[x<<1].val+tree[x<<1^1].val;
    tree[x].flag=(tree[x<<1].flag&&tree[x<<1^1].flag);
}
inline LL query(int x,int l,int r,int L,int R)
{
    if(l>=L&&r<=R)return tree[x].val;
    int mid(l+r>>1);
    LL ans(0);
    if(L<=mid)ans+=query(x<<1,l,mid,L,R);
    if(R>mid)ans+=query(x<<1^1,mid+1,r,L,R);
    return ans;
}
inline void modify(int x,int l,int r,int L,int R)
{
    if(tree[x].flag)return;
    if(l==r)
    {
        tree[x].val=(LL)sqrt(tree[x].val);
        if(tree[x].val<=1)tree[x].flag=1;
        return;
    }
    int mid(l+r>>1);
    if(L<=mid)modify(x<<1,l,mid,L,R);
    if(R>mid)modify(x<<1^1,mid+1,r,L,R);
    push_up(x);
}
inline void build(int x,int l,int r)
{
    if(l==r)
    {
        scanf("%lld",&tree[x].val);
        tree[x].flag=(tree[x].val<=1);
        return;
    }
    int mid(l+r>>1);
    build(x<<1,l,mid);
    build(x<<1^1,mid+1,r);
    push_up(x);
}
int main()
{
    int n,m,q,l,r;
    scanf("%d",&n);
    build(1,1,n);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d%d",&q,&l,&r);
        if(r<l)swap(l,r);
        if(q==1)printf("%lld\n",query(1,1,n,l,r));
        else modify(1,1,n,l,r);
    }
    return 0;
}

Comments

comments powered by Disqus