loj6189题解

要知道某个数的最高位,其实就是要知道它对数的小数部分,于是可以想到维护对数的和.

因为要给区间排序,容易想到线段树合并的做法,不过这里还要进行区间查询而非单点查询,理论上外面还需要套一个平衡树之类的东西,但这样就非常难写了.

注意到线段树合并的做法本来外面套着一个类似ODT的东西,而这道题的排序操作正好就相当于是区间覆盖,所以外面可以套ODT而不是平衡树,就非常好写了.

如果直接就这么交上去,你会发现前面有几个点T掉了,再仔细读一遍题,发现

对于$20\%$的数据:没有操作1

还需要对这20分专门写个暴力.

这种题精度很成问题,本来应该有spj,然后规定跟std输出不同的数不超过若干个就算A,可是这题没spj,那就得要跟出题人心灵相通了.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>
#define ele int
#define db double
using namespace std;
#define maxn 200010
#define K 500000
template<class T>struct mempool{
T *s,*t;
mempool(){ s=t=NULL; }
inline T* alloc(){
return s==t && (t=(s=new T[K])+K),s++;
}
};
struct node{
ele s;
db s1;
node *l,*r;
node(){ s=0; s1=0; l=r=NULL; }
};
ele n,m,a[maxn],tg[maxn];
db s1,s[maxn];
set<ele> S;
node *T[maxn];
mempool<node> np;
inline void maintain(node *x){
x->s=0; x->s1=0;
if (x->l) x->s+=x->l->s,x->s1+=x->l->s1;
if (x->r) x->s+=x->r->s,x->s1+=x->r->s1;
}
node* upd(node *x,ele u,ele v,ele i){
if (!x) x=np.alloc();
x->s=1; x->s1=log10(i);
if (u!=v){
ele mid=(u+v)>>1;
if (i<=mid) x->l=upd(x->l,u,mid,i);
else x->r=upd(x->r,mid+1,v,i);
}
return x;
}
node* merge(node *a,node *b){
if (!a) return b;
if (!b) return a;
a->s+=b->s; a->s1+=b->s1;
a->l=merge(a->l,b->l);
a->r=merge(a->r,b->r);
return a;
}
void split(node *x,ele k,ele u,ele v,node*&a,node*&b){
if (!x){ a=b=NULL; return; }
node *p=np.alloc();
if (!x->l && !x->r){
p->s=x->s-k; x->s=k;
p->s1=log10(u)*p->s; x->s1=log10(u)*x->s;
a=x; b=p;
return;
}
ele s=x->l?x->l->s:0,mid=(u+v)>>1;
if (k<s){
split(x->l,k,u,mid,a,b);
p->l=a; maintain(p);
x->l=b; maintain(x);
a=p; b=x;
}
else{
split(x->r,k-s,mid+1,v,a,b);
x->r=a; maintain(x);
p->r=b; maintain(p);
a=x; b=p;
}
}
inline void split(ele i){
if (S.find(i)!=S.end()) return;
S.insert(i);
auto it=S.find(i),it1=it,it2=it; --it1; ++it2;
tg[*it]=tg[*it1];
if (tg[*it1]) split(T[*it1],*it-*it1,1,n,T[*it1],T[*it]);
else split(T[*it1],*it2-*it,1,n,T[*it],T[*it1]);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=0; i<n; ++i){
scanf("%d",a+i);
S.insert(i);
T[i]=upd(NULL,1,n,a[i]);
tg[i]=1;
s[i]=log10(a[i]);
}
for (int i=1; i<n; ++i) s[i]+=s[i-1];
s1=0;
S.insert(n);
bool flag=true;
while (m--){
ele op,l,r,f;
scanf("%d%d%d",&op,&l,&r); --l,--r;
split(l); split(r+1);
if (op==1){
flag=false;
scanf("%d",&f);
node *p=NULL;
for (auto it=S.find(l); *it<=r;){
p=merge(p,T[*it]);
S.erase(it++);
}
S.insert(l);
T[l]=p; tg[l]=f;
}
else{
db tmp=0;
if (flag) tmp=s[r]-s[l-1];
else
for (auto it=S.find(l); *it<=r; ++it)
tmp+=T[*it]->s1;
tmp=tmp-trunc(tmp);
ele ans=exp(log(10)*tmp);
printf("%d\n",ans);
}
}
return 0;
}