ZOJ 3886 Nico Number (线段树)

2024-08-24 21:08
文章标签 number 线段 zoj nico 3886

本文主要是介绍ZOJ 3886 Nico Number (线段树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目地址:ZJU 3886
这个题需要想到一点,因为对一个数x不断取模的话,而且设定他小于模才会进行取余操作的话,那么最多只会进行logx次,因为每次取模都会使x最少折半。然后想到了这点就很好做了。对于区间取模更新操作可以直接暴力更新,维护一个最大值,如果这个区间的最大值小于模的话, 就不用继续向叶子更新了。然后其他的大于模的就更新到叶子节点。
然后对于NicoNumber来说,只有6,2的幂次和素数来说是符合的。所以可以预处理出来。然后就可以用线段树来维护了。
代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
#include <time.h>
using namespace std;
#define LL long long
#define pi acos(-1.0)
#pragma comment(linker, "/STACK:1024000000")
#define root 1, n, 1
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=100000+10;
bool isprime[MAXN*100], ok[MAXN*100];
int prime[MAXN*10];
int Max[MAXN<<2], sum[MAXN<<2];
void init()
{int tot=0, i, j;ok[0]=ok[1]=1;ok[6]=1;for(i=2;i<=10000000;i++){if(!isprime[i]) {prime[tot++]=i;ok[i]=true;}for(j=0;j<tot;j++){if(i*prime[j]>10000000) break;isprime[i*prime[j]]=true;if(i%prime[j]==0) break;}}int x=2;while(x<=10000000){ok[x]=true;x<<=1;}
}
void PushUp(int rt)
{Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void Build(int l, int r, int rt)
{if(l==r){scanf("%d",&Max[rt]);sum[rt]=ok[Max[rt]];return ;}int mid=l+r>>1;Build(lson);Build(rson);PushUp(rt);
}
void Update1(int p, int x, int l, int r, int rt)
{if(l==r){Max[rt]=x;sum[rt]=ok[x];return ;}int mid=l+r>>1;if(p<=mid) Update1(p,x,lson);else Update1(p,x,rson);PushUp(rt);
}
void Update2(int ll, int rr, int x, int l, int r, int rt)
{if(ll<=l&&rr>=r){if(Max[rt]<x) return ;}if(l==r){Max[rt]%=x;sum[rt]=ok[Max[rt]];return ;}int mid=l+r>>1;if(ll<=mid) Update2(ll,rr,x,lson);if(rr>mid) Update2(ll,rr,x,rson);PushUp(rt);
}
int Query(int ll, int rr, int l, int r, int rt)
{if(ll<=l&&rr>=r){return sum[rt];}int mid=l+r>>1, ans=0;if(ll<=mid) ans+=Query(ll,rr,lson);if(rr>mid) ans+=Query(ll,rr,rson);return ans;
}
int main()
{int n, i, j, l, r, p, v, q, x;init();while(scanf("%d",&n)!=EOF){memset(Max,0,sizeof(Max));memset(sum,0,sizeof(sum));Build(root);scanf("%d",&q);while(q--){scanf("%d",&x);if(x==1){scanf("%d%d",&l,&r);printf("%d\n",Query(l,r,root));}else if(x==2){scanf("%d%d%d",&l,&r,&v);Update2(l,r,v,root);}else{scanf("%d%d",&p,&v);Update1(p,v,root);}}}return 0;
}

这篇关于ZOJ 3886 Nico Number (线段树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1103610

相关文章

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

poj 1127 线段相交的判定

题意: 有n根木棍,每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连,当他们之间有公共点时,就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析: 线段相交的判定。 首先,模板中的线段相交是不判端点的,所以要加一个端点在直线上的判定; 然后,端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的,所以要加是否端点相等的判断。 最后

数论ZOJ 2562

题意:给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最大的一个。 分析:反素数定义:对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7

HDU4737线段树

题目大意:给定一系列数,F(i,j)表示对从ai到aj连续求或运算,(i<=j)求F(i,j)<=m的总数。 const int Max_N = 100008 ;int sum[Max_N<<2] , x[Max_N] ;int n , m ;void push_up(int t){sum[t] = sum[t<<1] | sum[t<<1|1] ;}void upd

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;