Algorithmic-Coding/MO's Algo.cpp at master · sanghaisubham/Algorithmic-Coding · 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
    #include<bits/stdc++.h>
    using namespace std;
    int counts[1000005];
    int comp(pair<int,pair<int,int > > a,pair<int,pair<int,int> >b)
    {
    if(b.second.first!=a.second.first)
    return a.second.first<b.second.first;
    else
    return a.first<b.first;

    }
    int main()
    {
    ios_base::sync_with_stdio(false);
    cin.tie(false);
    fill(counts,counts+1000005,0);
    int n;
    cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++)
    cin>>a[i];
    int sq=sqrt(n);
    int q;
    vector<pair<int,pair<int,int > > >block[sq+1];
    int count1=1;
    cin>>q;
    int q1=q;
    int maa=0;
    while(q1--)
    {
    int u1,v1;
    cin>>u1>>v1;
    int ans2=ceil((double)u1/(double)sq);
    //cout<<ans2<<"\n";
    maa=max(maa,ans2);
    block[ans2-1].push_back(make_pair(u1,make_pair(v1,count1++)));
    }
    for(int i=0;i<maa;i++)
    sort(block[i].begin(),block[i].end(),comp);
    int left=1;
    int right=0;
    int ans1=0;
    int ans[q+1];
    for(int i=0;i<maa;i++)
    {
    for(int j=0;j<block[i].size();j++)
    {
    int u1=block[i][j].first;
    int v1=block[i][j].second.first;;
    int co=block[i][j].second.second;
    //cout<<"HELLO :"<<u1<<" "<<v1<<" "<<co<<"\n";
    while(right<v1)
    {
    right++;
    counts[a[right]]++;
    if(counts[a[right]]==1)
    ans1++;
    }
    //cout<<counts[1]<<"\n";
    //cout<<right<<"\n";
    //cout<<"\n";
    while(left>u1)
    {
    left--;
    counts[a[left]]++;
    if(counts[a[left]]==1)
    ans1++;
    }

    while(right>v1)
    {
    counts[a[right]]--;
    if(counts[a[right]]==0)
    ans1--;
    right--;
    }
    while(left<u1)
    {
    counts[a[left]]--;
    if(counts[a[left]]==0)
    ans1--;
    left++;
    }
    /*for(int i=1;i<=3;i++)
    cout<<counts[i]<<" ";
    cout<<"\n";*/
    ans[co]=ans1;
    }
    }
    for(int i=1;i<=q;i++)
    cout<<ans[i]<<"\n";
    }