[Bzoj5358][Lydsy1805月赛]口算训练（预处理+动态开点线段树）

5358: [Lydsy1805月赛]口算训练

---

Time Limit: 5 Sec  Memory Limit: 512 MB
Submit: 318  Solved: 105
[Submit][Status][Discuss]

Description

---

begin.lydsy.com/JudgeOnline/upload/201805.pdf

Input

---

 

Output

---

 

Sample Input

---

 

Sample Output

---

 

HINT

---

 

Source

---

鸣谢claris提供

分析：

---

首先看到数最大只有10w，美滋滋，筛出素数，预处理出每个数包含哪些质数，且包含多少个。

然后对于每个质数开棵线段树。

d = （p1^c1）（p2^c2）……（pk^ck），

查询的时候只用查询d的每个质数在[L,R]范围内出现次数是否大于d中次数就行

AC代码：

---

# include <iostream>

# include <cstdio>

# include <cstring>

# include <vector>

# include <algorithm>

using namespace std;

const int N = 1e5;

vector<pair<int,int> > t[N + ];

int prime[N + ],cnt,root[N + ],lc[N * ],rc[N * ],s[N * ],p,a[N + ];bool vis[N + ];

void shai()

{

    for(int i = ;i <= N;i++)

    {

        if(!vis[i])prime[++cnt] = i;

        for(int j = ;j <= cnt;j++)

        {

            if(i * prime[j] > N)break;

            vis[i * prime[j]] = true;

            if(i % prime[j] == )break;

        }

    }

    for(int i = ;i <= cnt;i++)

     for(int j = prime[i];j <= N;j += prime[i])

     {

        t[j].push_back(make_pair(prime[i],j / prime[i]));

     }

}

void updata(int &k,int L,int l,int r,int d)

{

    if(!k){k = ++p;lc[k] = rc[k] = s[k] = ;}

    s[k] += d;

    if(l == r)return;

    int mid = l + r >> ;

    if(L <= mid)updata(lc[k],L,l,mid,d);

    else updata(rc[k],L,mid + ,r,d);

}

int Query(int &k,int L,int R,int l,int r)

{

    if(!k)return ;

    if(L <= l && r <= R)return s[k];

    int mid = l + r >> ;

    if(L > mid)return Query(rc[k],L,R,mid + ,r);

    if(R <= mid)return Query(lc[k],L,R,l,mid);

    return Query(lc[k],L,R,l,mid) + Query(rc[k],L,R,mid + ,r);

}

int n,m;

int main()

{

 shai();int Case;

 scanf("%d",&Case);

 while(Case--)

 {

    memset(root,,sizeof root);p = ;

    scanf("%d %d",&n,&m);

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

    {

        scanf("%d",&a[i]);

        for(int j = ;j < (int)t[a[i]].size();j++)

        updata(root[t[a[i]][j].first],i,,n,t[a[i]][j].second);

    }

    int x,y,z;

    while(m--)

    {

        scanf("%d %d %d",&x,&y,&z);bool f = true;

        for(int j = ;j < (int)t[z].size();j++)

        if(Query(root[t[z][j].first],x,y,,n) < t[z][j].second){f = false;break;}

        if(f)puts("Yes");else puts("No");

    }

 }

}