摘要:毒瘤区间除区间求和

P3987 我永远喜欢珂朵莉~

题面

题目分析

然而我喜欢奈芙莲.

题目意思很好懂,就是一个区间除和一个区间求和.

考虑用splay每次旋转出要操作的区间,打标记求解.

但是发现这个标记没法维护,但是发现数的大小只有5e6,可以对每一个数字建一颗平衡树,里面插入的点是原序列上被这个数字整除的数的下标,平衡树按照下标排序,操作中的要除以这个数直接用这个数的平衡树旋转出要除的区间即可,求和使用树状数组求解.

先找出操作区间的左端点在除数对应的树上的前驱和右端点在树上的后继,把前驱旋转到根,把后继旋转到前驱的下面,因为后继一定大于前驱,所以后继这个点在前驱的右儿子上,很显然后继的左儿子就全部包含了在操作区间内的点了.

然后在后继的左儿子这颗子树上进行dfs,直接在原序列上除以操作的数,并在树状数组上更改一下.如果除以了这个数之后这个原序列上的数不被这个数整除了,就把它从这个数字对应的splay上删掉,为了防止影响递归结构,我们可以在回溯的时候判断是否删除,要删的话就将它的儿子节点不断上旋,把它旋到叶子节点上直接删除即可.

对于建树,我们可以直接预处理出原序列上哪些位置的数被某个数整除,然后插入这个数对应的splay上,按照原序列下标处理的话预处理出的位置是有序的,所以可以直接递归建立一颗完美的splay.

代码

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#define lxl int
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define lowbit(x) (x&-x)
const lxl maxn=40000010,maxm=500010,maxt=100010;
lxl n,m,NodeCnt,MaxA;
lxl root[maxm],a[maxt],fa[maxn],c[maxn][2],size[maxn],val[maxn],q[maxn];
long long t[maxt];
std::vector<lxl>v[maxm];
inline void modify(lxl x,lxl val){for(;x<maxt;x+=lowbit(x))t[x]+=val;}
inline long long query(lxl x)
{
long long sum=0;
for(;x;x-=lowbit(x))sum+=t[x];
return sum;
}
struct _Spaly
{
inline void rotate(lxl x)
{
lxl y=fa[x],z=fa[y],d=c[y][1]==x;
c[z][c[z][1]==y]=x;
fa[x]=z,fa[y]=x,fa[c[x][d^1]]=y;
c[y][d]=c[x][d^1],c[x][d^1]=y;
PushUp(y),PushUp(x);
}
inline void spaly(lxl x,lxl goal,lxl id)
{
while(fa[x]!=goal)
{
lxl y=fa[x],z=fa[y];
if(fa[y]!=goal)rotate((c[y][0]==x)^(c[z][0]==y)?x:y);
rotate(x);
}
if(!goal)root[id]=x;
}
inline void PushUp(lxl x){size[x]=size[c[x][0]]+size[c[x][1]]+1;}
lxl suc(lxl x,lxl v)
{
lxl tmp;
if(!x)return v;
if(v<=val[x])return suc(c[x][0],v);
else
{
tmp=suc(c[x][1],v);
if(tmp==v)tmp=x;
return tmp;
}
}
lxl aft(lxl x,lxl v)
{
lxl tmp;
if(!x)return v;
if(v>=val[x])return aft(c[x][1],v);
else
{
tmp=aft(c[x][0],v);
if(tmp==v)tmp=x;
return tmp;
}
}
inline void div(lxl id,lxl l,lxl r)
{
if(!size[root[id]])return;
l=suc(root[id],l),r=aft(root[id],r);
spaly(l,0,id),spaly(r,l,id);
if(!c[r][0])return;
dfs(c[r][0],id);
}
void dfs(lxl now,lxl id)
{
if(!(a[val[now]]%id))modify(val[now],a[val[now]]/id-a[val[now]]),a[val[now]]/=id;
if(c[now][0])dfs(c[now][0],id);
if(c[now][1])dfs(c[now][1],id);
if(a[val[now]]%id)del(now);
PushUp(now);
}
inline void del(lxl now)
{
while(true)
{
if(c[now][0])rotate(c[now][0]);
else if(c[now][1])rotate(c[now][1]);
else break;
}
c[fa[now]][c[fa[now]][1]==now]=0;
--size[fa[now]],fa[now]=0,size[now]=0;
}
void build(lxl id,lxl &t,lxl l,lxl r,lxl from)
{
if(l>r)return;
if(!t)t=++NodeCnt;
lxl mid=(l+r)>>1;
fa[t]=from,val[t]=q[mid];
if(l==r){size[t]=1;return;}
build(id,c[t][0],l,mid-1,t),build(id,c[t][1],mid+1,r,t);
PushUp(t);
}
}splay;
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
int main(void)
{
n=read(),m=read();
for(R int i(1);i<=n;++i)
{
a[i]=read(),modify(i,a[i]),MaxA=std::max(a[i],MaxA);
for(R int j(1);j*j<=a[i];++j)
if(!(a[i]%j))
{
v[j].push_back(i);
if(j*j!=a[i])v[a[i]/j].push_back(i);
}
}
for(R int i(1);i<maxm;++i)
{
lxl cur=0;
for(std::vector<lxl>::iterator it=v[i].begin();it!=v[i].end();++it)q[++cur]=*it;
q[0]=-INF,q[cur+1]=INF;
splay.build(i,root[i],0,cur+1,0);
}
for(R int i(1);i<=m;++i)
{
lxl opt=read(),l=read(),r=read(),x;
if(opt==1)
{
x=read();
if(x>1)splay.div(x,l,r);
}
else printf("%lld\n",query(r)-query(l-1));
}
return 0;
}