const ll N=1e6+5;
ll lp[N];
ll mob[N];
void mobiusPreCalc(){
mob[1] = 1;
for (ll i = 2; i < N; ++i) {
if (!lp[i]) for (ll j = i; j < N; j += i)
if (!lp[j]) lp[j] = i;
mob[i] = [](ll x) {
ll cnt = 0;
while (x > 1) {
ll k = 0, d = lp[x];
while (x % d == 0) {
x /= d;
++k;
if (k > 1) return 0;
}
++cnt;
}
if (cnt & 1) return -1;
return 1;
}(i);
}
}
Problem :
https://leetcode.com/problems/course-schedule-ii/
class Solution {
public:
vector<int>vis;
vector<int>vec[5005];
vector<int> ans;
bool dfsAndReturnCycle(int src)
{
if(vis[src] == 1)
return true;
if(vis[src] == 2)
return false;
vis[src] = 1;
for (const auto& nextNode: vec[src])
{
if(dfsAndReturnCycle(nextNode))
return true;
}
vis[src] = 2;
ans.push_back(src);
return false;
}
vector<int> findOrder(int numCourses, vector<vector<int>>& ar) {
int n=ar.size();
for(int i=0;i<n;i++){
int v=ar[i][0];
int u=ar[i][1];
vec[u].push_back(v);
}
int flag=0;
vis = vector<int>(numCourses+2,0);
for(int i=0;i<numCourses;i++)
{
if(vis[i]==0){
if(dfsAndReturnCycle(i))
{
return {};
}
}
}
reverse(ans.begin(),ans.end());
return ans;
}
};
Mo's Algorithm Related Problem:
1) DQUERY - D-query , 2) FREQ2 - Most Frequent Value , 3) D. Cut and Stick , 4) D. Powerful array , 5) Chef and Graph Queries 6) D. Tree and Queries 7) Sherlock and Inversions
///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define timesave ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100005
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
#define space " "
#define yesp cout<<"YES"<<endl;
#define nop cout<<"NO"<<endl;
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
#define flagone(f) cout<<(f?"YES":"NO")<<endl;
#define flagzero(f) cout<<(f?"NO":"YES")<<endl;
int ar[tz],cnt[tz],ans[tz],freq[tz];
struct node
{
int lft,right,index;
};
int mx=0;
node query[tz];
int blockSize=317;
bool cmp(node fst,node scnd)
{
if(fst.lft/blockSize == scnd.lft/blockSize)
{
return fst.right/blockSize < scnd.right/blockSize;
}
return fst.lft<scnd.lft;
}
void addValue(int pos)
{
cnt[ar[pos]]++;
freq[cnt[ar[pos]]]++;
mx=max(mx,cnt[ar[pos]]);
}
void removeValue(int pos)
{
freq[cnt[ar[pos]]]--;
if(freq[cnt[ar[pos]]]==0)
mx--;
cnt[ar[pos]]--;
}
main()
{
timesave;
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
int n,q,a,b;
sf2(n,q);
for(int i=0; i<n; i++)
{
sf(ar[i]);
}
for(int i=0; i<q; i++)
{
sf2(a,b);
query[i].lft=a;
query[i].right=b;
query[i].index=i;
}
sort(query,query+q,cmp);
int leftPointer = 0,rightPointer=0;
for(int i=0; i<q; i++)
{
int leftValue = query[i].lft;
int rightValue = query[i].right;
int queryIndex = query[i].index;
while(leftPointer<leftValue)
{
removeValue(leftPointer);
leftPointer++;
}
while(leftPointer>leftValue)
{
addValue(leftPointer-1);
leftPointer--;
}
while(rightPointer<=rightValue)
{
addValue(rightPointer);
rightPointer++;
}
while(rightPointer>rightValue+1)
{
removeValue(rightPointer-1);
rightPointer--;
}
ans[query[i].index]=mx;
//cout<<leftValue<<" "<<rightValue<<" "<<mx<<endl;
}
for(int i=0; i<q; i++)
{
printf("%d\n",ans[i]);
}
}
