[题解] SP2713&P1415 线段树区间每个数开方+区间和

· · 个人记录

题目链接：

SP2713\ \ P1415

1. 题意人话翻译

有一个长度为n（n\leq1e5）的序列a_n。

有m组操作

每组操作包含三个数：opt,l,r

如果opt=0，则对区间每个数开方

如果opt=1，则输出区间和

2. 条件处理

题目要求区间每个数开方，这种信息线段树区间修改lazy无法维护。

but 正解就是线段树

首先关于数据范围\sum_{i=1}^n a_i \leq 10^{18}，我们发现最多开六次就变成1了。所以我们对于一个全为1的区间就不必修改。

其余信息递归到叶子结点修改。

可是我们要如何维护这个信息呢？

法一：建两个线段树，一个维护区间和，一个维护区间最大

如果建立一个维护区间最大的树，我们可以较快维护这个信息。我们只需同时维护两个树上的信息就可以了。

代码（以SP2713为例）：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<stack>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<deque>
#include<bitset>
#include<set>

using namespace std;

#define int long long
#define ull unsigned long long
#define rg register

namespace MySpace{
    inline int read(){
        rg int s=0,f=0;
        rg char ch=getchar();

        while(not isdigit(ch)) f|=(ch=='-'),ch=getchar();
        while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();

        return f?-s:s;
    }

    const int N=1e5+15;
    int sumv[N<<2],maxv[N<<2],a[N],n,m;

    #define ls (now<<1)
    #define rs (now<<1|1)

    inline void pushup(int now){
        sumv[now]=sumv[ls]+sumv[rs];
        maxv[now]=max(maxv[ls],maxv[rs]);
    }

    inline void build(int now,int l,int r){
        if(l==r){ sumv[now]=maxv[now]=a[l]; return; }
        rg int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(now);
    }

    inline void change(int now,int l,int r,int ql,int qr){
        if(maxv[now]==1) return;
        if(l==r){ sumv[now]=maxv[now]=(int)sqrt(sumv[now]); return; }
        rg int mid=(l+r)>>1;
        if(ql<=mid) change(ls,l,mid,ql,qr);
        if(mid<qr) change(rs,mid+1,r,ql,qr);
        pushup(now);
    }

    inline int query(int now,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return sumv[now];
        rg int mid=(l+r)>>1,ans=0;
        if(ql<=mid) ans+=query(ls,l,mid,ql,qr);
        if(mid<qr) ans+=query(rs,mid+1,r,ql,qr);
        return ans;
    }

    inline void main(){
        rg int cnt=0;
        while(scanf("%d",&n)!=EOF){
            printf("Case #%lld:\n",++cnt);

            for(rg int i=1;i<=n;i++) a[i]=read();
            build(1,1,n);
            m=read();
            for(rg int i=1;i<=m;i++){
                rg int opt=read(),l=read(),r=read();
                if(l>r) swap(l,r);
                if(opt==0) change(1,1,n,l,r);
                else printf("%lld\n",query(1,1,n,l,r));
            }
        }
    }
}

signed main(){
    MySpace::main();
    return 0;
}

法二：记一个标记代表全为0或一

我们可以知道全0或1的标记可以用简单的逻辑运算来解决。

如果两个子区间均为0或1，那么合并起来的区间也为0或1。

（类似题目：P1087 FBI树题解传送门 题目传送门）

3.后记

后来发现，分块5其实就是这个操作。具体思想和上面的法二差不多，也不再赘述。

题目链接：数列分块入门5