2018.07.08 NOIP模拟 好数(线段树)
好数
题目背景
SOURCE:NOIP2016-AHSDFZ T3
题目描述
我们定义一个非负整数是“好数”,当且仅当它符合以下条件之一:
1. 这个数是 0 或 1 。
2. 所有小于这个数且与它互质的正整数可以排成一个等差数列,例如,8 就是一个好数,因为 1,3,5,7 排成了等差数列。
给出 N 个非负整数,然后进行如下三个操作:
1. 询问区间 [L,R] 有多少个好数。
2. 将区间 [L,R] 内所有数对 S 取余(S≤1000000)。
3. 将第 C 个数更改为 X 。
提示:如果你不知道如何判断一个数是否为好数,你可以打个表找找规律。
输入格式
第一行包含两个正整数 N 和 M ,M 表示操作数目。
第二行包含 N 个非负整数。
接下来的 M 行每行表示 1 个操作:“1 L R”表示第 1 个操作,“2 L R S”表示第 2 个操作,“3 C X”表示第 3 个操作。
输出格式
对每个操作1,输出一个非负整数,表示区间内好数的个数。
样例数据 1
输入
3 6
4 6 9
1 1 3
1 3 3
2 1 1 10
1 1 3
3 2 4
1 1 3
输出
2
0
2
2
样例数据 2
输入
8 5
12 24 17 31 16 21 18 30
1 2 5
2 4 7 7
3 2 13
1 1 8
1 3 6
输出
3
6
4
备注
【数据规模与约定】
事实上在打表找完规律之后会发现好数只有质数,0,6,和2的非负整数次幂。这样的话,我们可以快速判断一个数是不是好数。然后分析一下算法,每个数每次被取模至少变成原来的0.5倍,于是logn" role="presentation" style="position: relative;">lognlogn次取模之后就成1了,这样的话直接暴力修改,每次单点修改会为时间复杂度提供logn" role="presentation" style="position: relative;">lognlogn的贡献,最多是O(nlogn)" role="presentation" style="position: relative;">O(nlogn)O(nlogn)的贡献,于是将区间取模分解成单点取模,记录区间最大值剪枝就行了。实在不放心的可以线性筛个素数什么的。
代码如下:
#include<bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
#define N 100005
using namespace std;
inline long long read(){
long long ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-1;
ch=getchar();
}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
return ans*w;
}
inline int lowbit(int x){return x&-x;}
int n,m,k,a[N];
bool f[105];
inline int prime(int x){
for(int i=2;i*i<=x;++i)if(x%i==0)return 0;
return 1;
}
inline int check(int x){
if(x<=6)return 1;
if(x==lowbit(x))return 1;
return prime(x);
}
struct Node{int minn,maxn,lz,l,r,sum,up;}T[N<<2];
inline void pushup(int p){
T[p].maxn=max(T[lc].maxn,T[rc].maxn);
T[p].minn=min(T[lc].minn,T[rc].minn);
T[p].sum=T[lc].sum+T[rc].sum;
}
inline void pushnow(int p,int v,int t){T[p].maxn=T[p].minn=T[p].lz=v,T[p].sum=(T[p].up=t)*(T[p].r-T[p].l+1);}
inline void pushdown(int p){
if(!T[p].lz)return;
pushnow(lc,T[p].lz,T[p].up);
pushnow(rc,T[p].lz,T[p].up);
T[p].lz=0;
T[p].up=0;
}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r,T[p].lz=0,T[p].up=0;
if(l==r){
T[p].maxn=T[p].minn=a[l];
T[p].sum=check(a[l]);
return;
}
build(lc,l,mid);
build(rc,mid+1,r);
pushup(p);
}
inline void modify(int p,int k,int v){
if(T[p].l==T[p].r){
T[p].maxn=T[p].minn=v;
T[p].sum=check(v);
return;
}
pushdown(p);
if(k<=mid)modify(lc,k,v);
else modify(rc,k,v);
pushup(p);
}
inline void update(int p,int ql,int qr,int v){
if(qr<T[p].l||T[p].r<ql||T[p].maxn<v)return;
if(ql<=T[p].l&&T[p].r<=qr&&T[p].maxn==T[p].minn){
pushnow(p,v,check(v));
return;
}
pushdown(p);
if(qr<=mid)update(lc,ql,qr,v);
else if(ql>mid)update(rc,ql,qr,v);
else update(lc,ql,mid,v),update(rc,mid+1,qr,v);
pushup(p);
}
inline int query(int p,int ql,int qr){
if(qr<T[p].l||T[p].r<ql)return 0;
if(ql<=T[p].l&&T[p].r<=qr)return T[p].sum;
pushdown(p);
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return query(lc,ql,mid)+query(rc,mid+1,qr);
}
int main(){
freopen("good.in","r",stdin);
freopen("good.out","w",stdout);
n=read(),m=read();
if(n<=100&&m<=100){
f[0]=1;
f[1]=1;
f[2]=1;
f[3]=1;
f[4]=1;
f[5]=1;
f[6]=1;
f[7]=1;
f[8]=1;
f[11]=1;
f[13]=1;
f[16]=1;
f[17]=1;
f[19]=1;
f[23]=1;
f[29]=1;
f[31]=1;
f[32]=1;
f[37]=1;
f[41]=1;
f[43]=1;
f[47]=1;
f[53]=1;
f[59]=1;
f[61]=1;
f[64]=1;
f[67]=1;
f[71]=1;
f[73]=1;
f[79]=1;
f[83]=1;
f[89]=1;
f[97]=1;
for(int i=1;i<=n;++i)a[i]=read();
while(m--){
int op=read(),l=read(),r=read();
if(op==1){
int ans=0;
for(int i=l;i<=r;++i)ans+=f[a[i]];
printf("%d\n",ans);
}
else if(op==2){
int s=read();
for(int i=l;i<=r;++i)a[i]%=s;
}
else a[l]=r;
}
}
else{
build(1,1,n);
while(m--){
int op=read(),l=read(),r=read();
if(op==1)printf("%d\n",query(1,l,r));
else if(op==2){
int s=read();
update(1,l,r,s);
}
else modify(1,l,r);
}
}
return 0;
}
最新文章
- mydumper linux mysql 备份利器
- php分享三十四:待排查问题
- ActiveX控件(ATL篇)
- windows批处理命令之ren
- openldap---ldapsearch使用
- Genymotion error:The virtual device got no IP address
- mac os x10.11.2系统eclipse无法读取环境变量的问题
- SSH整合缓存之-Memcached作为hibernate的二级缓存
- Nodejs的模块系统以及require的机制
- C# Split 根据组合字符进行拆分数组用法
- C# 使用反射 遍历输出 对象的属性
- MySql登陆密码忘记了怎么办?MySQL重置root密码方法
- Linux_(2)基本命令(下)
- Linux线程的信号量同步
- CodeM Qualifying Match Q5
- C++ new动态数组初始化
- _BV()
- linLINUX中常用操作命令
- 事件循环进阶:macrotask与microtask
- Java实现 lower_bound() 和 upper_bound()