Competitive-Programming---Solutions/prmq2.cpp at master · yvdyash/Competitive-Programming---Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// Author: yvdyash
// Segment Tree Implementation

#include <bits/stdc++.h>
using namespace std;

#define MAXN 1000005
#define INF 99999999

int spf[MAXN];
int a[MAXN];

vector<vector<int> > primefactors(1000006);
vector<vector<int> > segmentTree(4000006);


void findSmallestPrimeFactors()
{
    spf[1]=1;
    for (int i=2;i<MAXN;i++)
        spf[i]=i;

    for (int i=4;i<MAXN;i+=2)
        spf[i]=2;

    for (int i=3;i*i<MAXN;i++)
    {
        if (spf[i]==i)
        {
            for (int j=i*i;j<MAXN;j+=i)
               	if (spf[j]==j)
                    spf[j]=i;
        }
    }
}


void buildDivisorsArray(int a[],int n)
{
    for (int i=1;i<n+1;i++)
    {
        int ni=i,p=spf[a[i]];

        while (a[ni]>1)
        {
            primefactors[i].push_back(p);
            a[ni]=a[ni]/p;
            p=spf[a[ni]];
        }
    }
}


void buildSegtmentTree(int node,int a,int b)
{
    if (a==b)
    {
	for(int i=0;i<primefactors[a].size();i++)
        segmentTree[node].push_back(primefactors[a][i]);
        return ;
    }

    buildSegtmentTree(2*node,a,(a+b)/2);
    buildSegtmentTree(2*node+1,((a+b)/2)+1,b);


    for(int i=0;i<segmentTree[2*node].size();i++)
    segmentTree[node].push_back(segmentTree[2*node][i]);
    for(int i=0;i<segmentTree[2*node+1].size();i++)
    segmentTree[node].push_back(segmentTree[2*node+1][i]);


    sort(segmentTree[node].begin(),segmentTree[node].end());
}


int query(int a[],int node,int c,int d,int l,int r,int x,int y,int ans)
{

    if (l>d||c>r)
   	return 0;


    if (c>=l&&d<=r)
    {
    	int x1=lower_bound(segmentTree[node].begin(),segmentTree[node].end(),x)- segmentTree[node].begin();
    	int y1=upper_bound(segmentTree[node].begin(),segmentTree[node].end(),y)- segmentTree[node].begin();

    	ans+=y1-x1;

        return ans ;
    }

    return (query(a,2*node,c,(c+d)/2,l,r,x,y,ans)+query(a,2*node+1,((c+d)/2)+1,d,l,r,x,y,ans));
}


int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    findSmallestPrimeFactors();
    int n;
    cin>>n;
    for(int i=1;i<n+1;i++)
    cin>>a[i];

    buildDivisorsArray(a,n);
    buildSegtmentTree(1, 1,n);

    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
	    int l,r,x,y;
	    cin>>l>>r>>x>>y;
	    cout<<query(a,1,1,n,l,r,x,y,0)<<"\n";
    }
}