题解 P4145 【上帝造题的七分钟2 / 花神游历各国】

· · 题解

这种区间修改的题目，怎么能少了珂朵莉树呢QAQ

翻遍题解区，也没有找到珂朵莉树的算法QwQ

于是本蒟蒻就来献丑了QwQ

首先珂朵莉树可以看成一个支持合并和分裂的数据结构，所以这道题目可以用珂朵莉做（事实上，基本上能用分块做的题目，一般都可以用珂朵莉树过）

我们观察到10^{12}以内的数，最多只需要开6次方，就可以变成1，而\sqrt 1=1，很明显，对于这道题，只要修改操作足够多，那么到最后几乎可以全部变成1，为此，我们想到了珂朵莉树的做法。

代码:

//Copyright (c) 2019 by xiao_mmQF. All Rights Reserved.
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
#define inl inline
#define reg register
#define db long double
using namespace std;
using namespace __gnu_pbds;
const int MAXN=100050;
inl int read(){ int x=0,f=0; char ch=0; while(!isdigit(ch))f|=(ch=='-'),ch=getchar(); while(isdigit(ch))(x*=10)+=(ch^48),ch=getchar(); return f?-x:x; }
inl void Print(reg int x) { if(x<0)putchar('-'),x=-x; if(x>=10)Print(x/10); putchar(x%10+'0'); }
inl void Println(reg int x){Print(x);putchar('\n');}
inl int Max(reg int x,reg int y){return x>y?x:y;}
inl int Min(reg int x,reg int y){return x<y?x:y;}
inl int Abs(reg int x){return x<0?-x:x;}
//以上是模板
struct Node{
    int l,r;
    mutable int val;//mutable用来处理操作
    bool operator<(const Node &rhs)const{
        return l<rhs.l;
    }
};
set<Node>st;
#define It set<Node>::iterator
It split(int pos){
    It iter=st.lower_bound((Node){pos,0,0});
    if(iter!=st.end()&&iter->l==pos)return iter;
    iter--;
    int l=iter->l,r=iter->r,val=iter->val;
    if(pos>iter->r)return st.end();
    st.erase(iter);
    st.insert((Node){l,pos-1,val});
    return st.insert((Node){pos,r,val}).first;
}
//标准的split操作
void assign(int l,int r,int val){
    It iter2=split(r+1),iter=split(l);
    st.erase(iter,iter2);
    st.insert((Node){l,r,val});
}
//标准的assign操作
inl void chg(reg int l,reg int r){
    reg int tl=0,tr=0,val=0;
    It ir=split(r+1),il=split(l);
    for(It iter=il;iter!=ir;iter++){
        if(iter->val!=1)iter->val=sqrt(iter->val);//朴素开方
        if(iter->val==val)tr=iter->r;//获得连续区间的值
        else {
            if(val)//第一次val的初值是0，防止这种情况
            assign(tl,tr,val);//推平区间
            tl=iter->l,tr=iter->r,val=iter->val;
        }
    }
    assign(tl,tr,val);//推平区间
}
//开方操作
inl int query(reg int l,reg int r){
    int ret=0;
    for(reg It iter2=split(r+1),iter=split(l);iter!=iter2;iter++)
    ret+=(iter->r-iter->l+1)*iter->val;//朴素操作
    return ret;
}
//查询操作
int n,m;
int a[MAXN];
signed main(){
    n=read();
    for(reg int i=1;i<=n;i++)
    a[i]=read(),st.insert((Node){i,i,a[i]});//初始化珂朵莉树
    m=read();
    while(m--){
        // for(reg It iter=st.begin();iter!=st.end();iter++)
        // printf("[%lld %lld %lld]\n",iter->l,iter->r,iter->val);//DEBUG 用
        int op=read(),l=read(),r=read();
        if(l>r)swap(l,r);//忘了这句话T5个点QAQ
        if(op==1)Println(query(l,r));
        else chg(l,r);
    }
    return 0;
}

能用分块的题基本都能用珂朵莉哦！我永远喜欢珂朵莉.jpg