• 1 l r t: 将区间 [l,r] 降序排序 (t = 0) 或升序排序 (t = 1)
• 2 l r: 询问区间 [l,r] 内元素之积的十进制下最高位
雅礼集训的题目，当时因为空间开小了爆零了
先考虑一下询问，我们发现并不好直接做，所以可以对原数取log10，最后询问区间和的小数部分即可
让后现在问题就在修改这里，这是一个非常经典的线段树合并可以解决的问题
每次排序就将对应区间的线段树链接起来，查询的时候断开
所有根节点用一个zkw线段树来存，根节点的值放在一个fenwick里面方便查询
除了精度被卡了一下其他基本一次写对，3k的代码，是本题平均代码长度的一半
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 200010
#define db double
using namespace std;
struct tree{ int l,r,c; double s; } s[N*60];
struct fenwick{
db w[N],S; int n;
inline void add(int x,db k){ for(;x<=n;x+=x&-x) w[x]+=k; }
inline db sum(int x){ for(S=0;x;x&=x-1) S+=w[x]; return S; }
} w;
struct seg{
int s[N<<2],M;
inline void init(int n){
for(M=1;M<n;M<<=1); --M;
for(int i=M+1;i<=M+n;++i) s[i]=1;
for(int i=M;i;--i) s[i]=s[i<<1]+s[i<<1|1];
}
inline void insert(int x){ for(x+=M;x;x>>=1) ++s[x]; }
inline void remove(int x){ for(x+=M;x;x>>=1) --s[x]; }
inline int at(int x){ return s[x+M]; }
inline int gPre(int x){
for(x+=M;x;x>>=1)
if((x&1)&&s[x^1]){
for(--x;x<=M;x=(s[x<<1|1]?x<<1|1:x<<1));
return x-M;
}
return -1;
}
inline int gSuc(int x){
for(x+=M;x;x>>=1)
if((~x&1)&&s[x^1]){
for(++x;x<=M;x=(s[x<<1]?x<<1:x<<1|1));
return x-M;
}
return -1;
}
} T;
inline void ps(int x){
s[x].c=s[s[x].l].c+s[s[x].r].c;
s[x].s=s[s[x].l].s+s[s[x].r].s;
}
int n,m,rt[N],v[N],rev[N],r[N],sa[N],cnt=0;
inline void merge(int& x,int y){
if(!y || !x){ x+=y; return; }
merge(s[x].l,s[y].l);
merge(s[x].r,s[y].r);
ps(x);
}
inline void split(int k,int& x,int& y){
if(k==0){ x=0; y=x; return; }
else if(k==s[x].c) return; y=++cnt;
if(s[s[x].l].c>=k){
s[y].r=s[x].r; s[x].r=0;
split(k,s[x].l,s[y].l);
} else {
split(k-s[s[x].l].c,s[x].r,s[y].r);
}
ps(x); ps(y);
}
inline void link(int l,int r,int o){
int x=T.gSuc(l); w.add(l,-s[rt[l]].s);
for(;~x&&x<=r;x=T.gSuc(x)){
w.add(x,-s[rt[x]].s);
merge(rt[l],rt[x]);
T.remove(x);
}
w.add(l,s[rt[l]].s); rev[l]=o;
}
inline void cut(int x){
if(T.at(x) || x>n) return;
int l=T.gPre(x),r=T.gSuc(x); if(r<0) r=n+1;
w.add(l,-s[rt[l]].s); T.insert(x);
if(!rev[l]) split(x-l,rt[l],rt[x]);
else split(r-x,rt[l],rt[x]),swap(rt[l],rt[x]);
rev[x]=rev[l]; w.add(l,s[rt[l]].s); w.add(x,s[rt[x]].s);
}
inline void insert(int l,int r,int& x,int k,double p){
x=++cnt;
if(l==r){ s[x]=(tree){0,0,1,p}; return; }
int m=l+r>>1;
if(k<=m) insert(l,m,s[x].l,k,p);
else insert(m+1,r,s[x].r,k,p);
ps(x);
}
inline bool c1(int i,int j){ return v[i]<v[j]; }
inline db g(db x){ return x-(int)x+1e-7; } db p;
int main(){
freopen("zkb.in","r",stdin);
freopen("zkb.out","w",stdout);
scanf("%d%d",&n,&m); w.n=n;
for(int i=1;i<=n;++i){
scanf("%d",v+i); sa[i]=i;
}
sort(sa+1,sa+1+n,c1); T.init(n);
for(int i=1;i<=n;++i) r[sa[i]]=i;
for(int i=1;i<=n;++i){
insert(1,n,rt[i],r[i],p=log10(v[i]));
w.add(i,p);
}
for(int o,l,r;m--;){
scanf("%d%d%d",&o,&l,&r);
if(o==1){
scanf("%d",&o);
cut(l);
cut(r+1);
link(l,r,!o);
} else {
cut(l);
cut(r+1);
printf("%d
",(int)floor(pow(10,g(w.sum(r)-w.sum(l-1)))));
}
// for(int i=1;i<=n;++i){
// if(T.at(i)) printf("[%d %d]",i,i+s[rt[i]].c-1);
//
// }
// puts("");
}
}