【题解】Philosopher 线段树合并分裂+Splay loj#6189 ——litble

这是一个悲伤的故事
别人在博弈论，我在哲学家；
别人在学数学，我在哲学家；
别人在吉司机，我在哲学家；
别人在剩余系，我在哲学家；
别人在改考试题，我 TM 还在哲学家；

我怀疑这道题叫哲学家，就是因为你写完后，会对人生有一种船新的思考。

首先，乘积的十进制最高位，可以就把每个数都取 log，这样乘就变成了加，就不会大到爆炸。然后提取了和之后，去掉整数部分，pow 一下就能得到十进制最高位了。

原序列看做若干权值线段树，一棵权值线段树里维护的元素是有序的，至于是升序还是降序，打个标记就好了。然后每一次操作，我们首先要将 l 和 r 所在的线段树分裂一下，这样若干棵权值线段树就构成了我们的操作区间，若是修改操作，就将这些线段树合并，是询问就查询它们的元素和。

有一个关键的问题就是要随时维护这些权值线段树放的顺序，来保持它们的有序，所以需要一棵平衡树。

你会发现这题需要查询区间和，所以就不能用 set，必须手写 splay……QAQ

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=200005;
typedef double db;
const db eps=1e-8;
typedef pair<int,int> PR;
int n,m,rt,last_ins,js,tg[N],p[N];

struct node{
    int ls,rs,sz;db sum;
    void clear() {ls=rs=sz=0,sum=0;}
};
struct segment_tree{
    int SZ;stack<int> rub;
    node tr[N*60];
    int newnode() {
        if(!rub.empty()) {int re=rub.top();rub.pop();return re;}
        else return ++SZ;
    }
    void up(int k) {
        tr[k].sum=tr[tr[k].ls].sum+tr[tr[k].rs].sum;
        tr[k].sz=tr[tr[k].ls].sz+tr[tr[k].rs].sz;
    }
    int ins(int x,int s,int t,int k,db v) {//插入
        if(!k) k=newnode();
        int mid=(s+t)>>1;
        if(s==t) {tr[k].sum+=v,++tr[k].sz;return k;}
        if(x<=mid) tr[k].ls=ins(x,s,mid,tr[k].ls,v);
        else tr[k].rs=ins(x,mid+1,t,tr[k].rs,v);
        up(k);return k;
    }
    int mix(int a,int b) {
        if(!a&&!b) return 0;
        int k=newnode(); tr[k].ls=a,tr[k].rs=b,up(k); return k;
    }
    PR split(int k,int sz_to_split) {//分裂
        if(!k) return (PR){0,0};
        if(tr[k].sz==sz_to_split) return (PR){k,0};
        if(!sz_to_split) return (PR){0,k};
        if(!tr[k].ls&&!tr[k].rs) {
            int a_new_node=newnode();
            tr[a_new_node].sum=tr[k].sum/(db)tr[k].sz*(db)sz_to_split;
            tr[a_new_node].sz=sz_to_split;
            tr[k].sz-=sz_to_split,tr[k].sum-=tr[a_new_node].sum;
            return (PR){a_new_node,k};
        }
        if(sz_to_split<=tr[tr[k].ls].sz) {
            PR re=split(tr[k].ls,sz_to_split);
            re=(PR){mix(re.first,0),mix(re.second,tr[k].rs)};
            tr[k].clear(),rub.push(k);
            return re;
        }
        else {
            PR re=split(tr[k].rs,sz_to_split-tr[tr[k].ls].sz);
            re=(PR){mix(tr[k].ls,re.first),mix(0,re.second)};
            tr[k].clear(),rub.push(k);
            return re;
        }
    }
    int merge(int x,int y) {//合并
        if(!x||!y) return x|y;
        tr[x].ls=merge(tr[x].ls,tr[y].ls);
        tr[x].rs=merge(tr[x].rs,tr[y].rs);
        tr[x].sz+=tr[y].sz,tr[x].sum+=tr[y].sum;
        tr[y].clear(),rub.push(y);
        return x;
    }
}T;

struct nico{
    int l,r,id,s[2],f;db sum,v;
    void clear() {sum=v=0;f=s[0]=s[1]=id=l=r=0;}
};
struct Splay{
    int SZ;stack<int> rub;
    nico tr[N];
    int newnode() {
        if(!rub.empty()) {int re=rub.top();rub.pop();return re;}
        else return ++SZ;
    }
    int is(int k) {return tr[tr[k].f].s[1]==k;}
    void up(int k) {tr[k].sum=tr[tr[k].s[0]].sum+tr[tr[k].s[1]].sum+tr[k].v;}
    void spin(int x,int &mb) {
        int fa=tr[x].f,g=tr[fa].f,t=is(x);
        if(fa==mb) mb=x;
        else tr[g].s[is(fa)]=x;
        tr[x].f=g,tr[fa].f=x,tr[tr[x].s[t^1]].f=fa;
        tr[fa].s[t]=tr[x].s[t^1],tr[x].s[t^1]=fa;
        up(fa),up(x);
    }
    void splay(int x,int &mb) {
        while(x!=mb) {
            if(tr[x].f!=mb) {
                if(is(x)^is(tr[x].f)) spin(x,mb);
                else spin(tr[x].f,mb);
            }
            spin(x,mb);
        }
    }
    void ins(int &k,int fa,int L,int R,int id,db v) {//插入
        if(!k) {
            k=last_ins=newnode();
            tr[k].l=L,tr[k].r=R,tr[k].id=id,tr[k].f=fa;
            tr[k].sum=tr[k].v=v;
            return;
        }
        if(L<tr[k].l) ins(tr[k].s[0],k,L,R,id,v);
        else ins(tr[k].s[1],k,L,R,id,v);
        up(k);
    }
    int find(int k,int wz) {//查找
        if(tr[k].l<=wz&&wz<=tr[k].r) return k;
        if(tr[k].r<=wz) return find(tr[k].s[1],wz);
        else return find(tr[k].s[0],wz);
    }
    void del(int k) {//删除
        splay(k,rt);
        if(!tr[k].s[0]||!tr[k].s[1]) rt=tr[k].s[0]|tr[k].s[1],tr[rt].f=0;
        else {
            int x=tr[k].s[1];
            while(tr[x].s[0]) x=tr[x].s[0];
            tr[x].s[0]=tr[k].s[0],tr[tr[k].s[0]].f=x;
            rt=tr[k].s[1],tr[rt].f=0;
            while(x) up(x),x=tr[x].f;
        }
        tr[k].clear(),rub.push(k);
    }
}S;

void Ins(int l,int r,int k)
    {S.ins(rt,0,l,r,k,T.tr[k].sum),S.splay(last_ins,rt);}
void QAQ(int l,int r) {
    int k1=S.find(rt,l),tmp_tg1=tg[k1];nico nico1=S.tr[k1];
    if(nico1.l<l) {
        S.del(k1);
        int ksz=(tmp_tg1?l-nico1.l:nico1.r-l+1);
        PR tmp_pair=T.split(nico1.id,ksz);
        if(!tmp_tg1) swap(tmp_pair.first,tmp_pair.second);//若是降序，小的值在后
        Ins(nico1.l,l-1,tmp_pair.first),tg[last_ins]=tmp_tg1;//记得维护升序降序标记
        Ins(l,nico1.r,tmp_pair.second),tg[last_ins]=tmp_tg1;
    }
    int k2=S.find(rt,r),tmp_tg2=tg[k2];nico nico2=S.tr[k2];
    if(nico2.r>r) {
        S.del(k2);
        int ksz=(tmp_tg2?r-nico2.l+1:nico2.r-r);
        PR tmp_pair=T.split(nico2.id,ksz);
        if(!tmp_tg2) swap(tmp_pair.first,tmp_pair.second);
        Ins(nico2.l,r,tmp_pair.first),tg[last_ins]=tmp_tg2;
        Ins(r+1,nico2.r,tmp_pair.second),tg[last_ins]=tmp_tg2;
    }
    S.splay(S.find(rt,l-1),rt),S.splay(S.find(rt,r+1),S.tr[rt].s[1]);
    //套路，将区间放在根的右儿子的左子树
}
void dfs(int x) {
    if(S.tr[x].s[0]) dfs(S.tr[x].s[0]);
    if(S.tr[x].s[1]) dfs(S.tr[x].s[1]);
    p[++js]=S.tr[x].id,S.tr[x].clear(),S.rub.push(x);
}
int main()
{
    int op,l,r,x,k;
    n=read(),m=read();
    Ins(0,0,0),Ins(n+1,n+1,0);
    for(RI i=1;i<=n;++i)
        x=read(),k=T.ins(x,1,n,0,log10((db)x)),Ins(i,i,k);
    while(m--) {
        op=read(),l=read(),r=read();
        QAQ(l,r);
        int x=S.tr[S.tr[rt].s[1]].s[0];
        if(op==1) {
            js=0,dfs(x),k=p[1];
            S.tr[S.tr[rt].s[1]].s[0]=0;
            for(RI i=2;i<=js;++i) k=T.merge(k,p[i]);
            Ins(l,r,k),tg[last_ins]=read();
        }
        else {
            db ans=S.tr[x].sum;
            ans-=floor(ans+eps),ans=pow(10,ans);
            printf("%d\n",(int)floor(ans+eps)%10);
        }
    }
    return 0;
}