BZOJ 5358 [Lydsy1805 月赛] 口算训练

题意：区间询问积是否为 d 的倍数。

分解质因数，暴力插到主席树里即可。

#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100005
#define inf N
#define ll long long
using namespace std;
char xB[1<<15],*xS=xB,*xT=xB;
#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
typedef pair<int,int> pr;
#define fi first
#define se second
vector<pr> Div(int x)
{
    vector<pr> v;
    v.clear();
    for(int i=2;i*i<=x;i++)
    {
        int ret=0;
        while(x%i==0)ret++,x/=i;
        if(ret)v.push_back(make_pair(ret,i));
    }
    if(x!=1)v.push_back(make_pair(1,x));
    return v;
}
#define M N*60
int rt[M],tot;
int sum[M],ch[M][2];
#define clr(x) memset(x,0,sizeof(x))
void upd(int &x,int y,int l,int r,int v,int k)
{
    x=++tot;
    ch[x][0]=ch[y][0],ch[x][1]=ch[y][1],sum[x]=sum[y]+k;
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(v<=mid) upd(ch[x][0],ch[y][0],l,mid,v,k);
    else upd(ch[x][1],ch[y][1],mid+1,r,v,k);
}
int ask(int x,int l,int r,int v)
{
    if(!x)return 0;
    if(l==r)return sum[x];
    int mid=(l+r)>>1;
    if(v<=mid) return ask(ch[x][0],l,mid,v);
    else return ask(ch[x][1],mid+1,r,v);
}
int T,n,m;
int a[N];
int main()
{
    T=read();
    while(T--)
    {
        tot=0;
        clr(rt),clr(sum),clr(ch);
        n=read(),m=read();
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=n;i++)
        {
            rt[i]=rt[i-1];
            vector<pr> v=Div(a[i]);
            for(int j=0;j<v.size();j++)
            upd(rt[i],rt[i],1,inf,v[j].se,v[j].fi);
        }
        while(m--)
        {
            int l=read(),r=read(),x=read();
            vector<pr> v=Div(x);
            bool flag=0;
            for(int j=0;j<v.size();j++)
            {
                int y=ask(rt[r],1,inf,v[j].se)-ask(rt[l-1],1,inf,v[j].se);
                if(y<v[j].fi)
                {
                    puts("No");
                    flag=1;
                    break ;
                }
            }
            if(!flag)puts("Yes");
        }
    }
}

#include <cmath>

#include <queue>

#include <vector>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 100005

#define inf N

#define ll long long

using namespace std;

char xB[1<<15],*xS=xB,*xT=xB;

#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

typedef pair<int,int> pr;

#define fi first

#define se second

vector<pr> Div(int x)

{

vector<pr> v;

v.clear();

for(int i=2;i*i<=x;i++)

{

int ret=0;

while(x%i==0)ret++,x/=i;

if(ret)v.push_back(make_pair(ret,i));

}

if(x!=1)v.push_back(make_pair(1,x));

return v;

}

#define M N*60

int rt[M],tot;

int sum[M],ch[M][2];

#define clr(x) memset(x,0,sizeof(x))

void upd(int &x,int y,int l,int r,int v,int k)

{

x=++tot;

ch[x][0]=ch[y][0],ch[x][1]=ch[y][1],sum[x]=sum[y]+k;

if(l==r)return ;

int mid=(l+r)>>1;

if(v<=mid) upd(ch[x][0],ch[y][0],l,mid,v,k);

else upd(ch[x][1],ch[y][1],mid+1,r,v,k);

}

int ask(int x,int l,int r,int v)

{

if(!x)return 0;

if(l==r)return sum[x];

int mid=(l+r)>>1;

if(v<=mid) return ask(ch[x][0],l,mid,v);

else return ask(ch[x][1],mid+1,r,v);

}

int T,n,m;

int a[N];

int main()

{

T=read();

while(T--)

{

tot=0;

clr(rt),clr(sum),clr(ch);

n=read(),m=read();

for(int i=1;i<=n;i++)a[i]=read();

for(int i=1;i<=n;i++)

{

rt[i]=rt[i-1];

vector<pr> v=Div(a[i]);

for(int j=0;j<v.size();j++)

upd(rt[i],rt[i],1,inf,v[j].se,v[j].fi);

}

while(m--)

{

int l=read(),r=read(),x=read();

vector<pr> v=Div(x);

bool flag=0;

for(int j=0;j<v.size();j++)

{

int y=ask(rt[r],1,inf,v[j].se)-ask(rt[l-1],1,inf,v[j].se);

if(y<v[j].fi)

{

puts("No");

flag=1;

break ;

}

if(!flag)puts("Yes");

}

zgz233

BZOJ 5358 [Lydsy1805 月赛] 口算训练

BZOJ 5346 树

BZOJ 1527 [POI2005]Pun-point

l1ll5

Comments | 2 条评论

Tony Zhao 博主

l1ll5 博主

zgz233