Nico Number ZOJ - 3886(선형 체 + 세그먼트 트리 구간 업데이트 모드)
1848 단어 세그먼트 트리
#include
#include
#include
#include
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int MAXN=111111;
int stree[MAXN<<2];
int sum[MAXN<<2];
bool nico[11111111];
void init()
{
memset(nico,1,sizeof(nico));
for(int i=2;i<11111111;i++)
{
if(nico[i])
{
for(int j=2*i;j<11111111;j+=i)
nico[j]=0;
}
}
nico[6]=1;
for(int i=2;i<11111111;i<<=1)
{
nico[i]=1;
}
}
void pushup(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
stree[rt]=max(stree[rt<<1],stree[rt<<1|1]);
}
void build(int l,int r,int rt)
{
stree[rt]=0;
sum[rt]=0;
if(l==r)
{
int k;
scanf("%d",&k);
stree[rt]=k;
sum[rt]=nico[k]?1:0;
return;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return sum[rt];
}
int mid=(l+r)>>1;
int ans=0;
if(L<=mid) ans+=query(L,R,lson);
if(R>mid) ans+=query(L,R,rson);
return ans;
}
void update(int L,int R,int c,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
if(stree[rt]>1;
if(L<=mid) update(L,R,c,lson);
if(R>mid) update(L,R,c,rson);
pushup(rt);
}
void update3(int k,int c,int l,int r,int rt)
{
if(l==r)
{
stree[rt]=c;
sum[rt]=nico[stree[rt]]?1:0;
return;
}
int mid=(l+r)>>1;
if(k<=mid) update3(k,c,lson);
else update3(k,c,rson);
pushup(rt);
}
int main()
{
init();
int n;
while(scanf("%d",&n)!=EOF)
{
build(1,n,1);
int m;
scanf("%d",&m);
for(int i=0;i
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준 알고리즘 14427번 : 수열과 쿼리 15길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.