SP19568 题解
a2lyaXNhbWUgbWFyaXNh
·
·
题解
前言
有区间推平，第一时间想到的就是珂朵莉树。还好数据够水。
秉着能写 odt 绝不写线段树的原则，这篇题解诞生了。
做法
操作 1
单点修改。当成 l~l 区间修改就行。
操作 2
区间赋值。珂朵莉树基本操作。
重点：操作 3
**但是**，请注意，判断的时候你不能
```cpp
if(!f[it->v]&&it->v<=10000000)
```
判，会 RE。你得
```cpp
if(it->v<=10000000&&!f[it->v])
```
这样判。
因为根据短路的原则（即，对于逻辑与运算，第一个为假就不会继续计算，表达式直接为假；对于逻辑或运算，第一个为真就不会继续计算，表达式直接为真），你才躲掉了毒瘤数据。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define TIPS "ctjzm"
#define IT set<node>::iterator
typedef long long TYPE;
int prime[10000007];
bool f[10000007];
void sieve(){
int n=10000000;
f[0]=f[1]=1;
int cnt=1;
for(int i=2;i<=n;i++){
if(!f[i])
prime[cnt++]=i;
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
f[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}//线性筛
struct node{
unsigned int l,r;
mutable TYPE v;
node(unsigned int left,unsigned int right=0,TYPE value=0);
};
bool operator<(node a,node b){
return a.l<b.l;
}
node::node(unsigned int left,unsigned int right,TYPE value){
l=left;
r=right;
v=value;
}
set<node>odt;
inline IT split(unsigned int p){
IT it=odt.lower_bound(node(p));
if(it!=odt.end()&&it->l==p)
return it;
--it;
unsigned r=it->r,l=it->l;
TYPE v=it->v;
odt.erase(it);
odt.insert(node(l,p-1,v));
return odt.insert(node(p,r,v)).first;
}//珂朵莉树核心——分裂操作
inline void assign(int l, int r, int v) {
IT itr=split(r+1),itl=split(l);
odt.erase(itl, itr);
odt.insert(node(l, r, v));
}//操作2+珂朵莉树核心——推平操作
//祖传珂朵莉树模板↑
inline void update(int p,int v){
split(p+1),split(p)->v+=v;
}//操作 1，单点修改
inline int getsum(int l,int r){
long long sum=0;
IT itr=split(r+1),itl=split(l);
for(IT it=itl;it!=itr;++it)
if(it->v<=10000000&&!f[it->v])
sum+=it->r-it->l+1;
return sum;
}//操作3，统计素数
int n,m,x,y,z;
char ch;
int main(){
sieve();//预处理
cin>>n>>m;
for(unsigned i=1;i<=n;++i){
int t;
cin>>t;
odt.insert(node(i,i,t));
}
for(unsigned i=1;i<=m;++i){
cin>>ch;
switch(ch){
case 'A':
cin>>x>>y;
update(y,x);
break;
case 'R':
cin>>x>>y>>z;
assign(y,z,x);
break;
case 'Q':
cin>>x>>y;
cout<<getsum(x,y)<<endl;
break;
}
}
return 0;//好习惯
}
```