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