-------------------------------FAST I/O -----------------------------------
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
-------------------MODULAR EXPONENTIATION ---------------------------------
long long fastPower(long long a, long long b, int n) {
long long res = 1;
while ( b > 0) {
if ( (b&1) != 0) {
res = (res * a % n) % n;
}
a = (a % n * a % n) % n;
b = b >> 1;
}
return res;
--------------------------------EUCLEDIAN GCD ------------------------------
static long gcdlonga, longb) {
return a % b == 0 ? b : gcd ( b, a%b);
}
----------------------SIEVE OF ERATOSTHENES----------------------------------
static boolean[] seiveOfEratoSthenes(int n) {
boolean isPrime[] = new boolean[n+1];
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
for(int i = 2; i * i <= n; i++) {
for(int j = 2*i; j<=n; j += i) {
isPrime[j] = false;
}
return isPrime;
}
----------------------COUNT OF SET BITS----------------
unsigned int countSetBits(int n)
{
unsigned int count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
OR(for C++ only)
use __builtin_popcount(int n);
------------------Longest Non Decreasing Subseq
O(N.logN)-------------------------------------------
int CeilIndex(vector<int>& v,int r, int key)
{
return upper_bound(v.begin(),v.begin()+r,key)-v.begin();
}
int LongestNonDecreasingSubseq(vector<int>& v)
{
if (v.size()==0)
return 0;
vector<int> tail(v.size(),0);
int length=1;
tail[0]=v[0];
for (int i=1;i<v.size();i++)
{
if (v[i]<tail[0])
tail[0]=v[i];
else if(v[i]>=tail[length-1])
tail[length++]=v[i];
else
tail[CeilIndex(tail,length-1,v[i])]=v[i];
}
return length;
}
------------------------------SPARSE TABLE
--------------------------------------------------
Sparse Table for Range Maximum/Minimum Queries (RMQ):-- O(NlogN)
int m;
cin>>m;
vi v(m);
rep(i,0,m){
cin>>v[i];
}
int l=log2(m)+1;
vector<vector<int>> st(m,vector<int>(l));
rep(i,0,m){
st[i][0]=v[i];
}
rep(j,1,l){
rep(i,0,m){
st[i][j]=st[i][j-1];
if(i+(1<<(j-1))<m){
st[i][j]=max(st[i][j],st[i+(1<<(j-1))][j-1]);
}
}
}
Now to Calculate max/min in array v in range from index (l to r):---
int len=r-l+1;
len=log2(len);
mx=max(mx,st[l-1][len]);
mx=max(mx,st[r-(1<<(len))][len]);
----------------------------------SQRT
DECOMPOSITION----------------------------------------
// for range sum/min/max queries O(N+Q*sqrt(n))
int query(int l, int r)
{
int sum = 0;
while (l<r and l%blk_sz!=0 and l!=0)
{
sum += arr[l];
l++;
}
while (l+blk_sz-1 <= r)
{
sum += block[l/blk_sz];
l += blk_sz;
}
while (l<=r)
{
sum += arr[l];
l++;
}
return sum;
}
void preprocess(int input[], int n)
{
int blk_idx = -1;
blk_sz = sqrt(n);
for (int i=0; i<n; i++)
{
arr[i] = input[i];
if (i%blk_sz == 0)
blk_idx++;
block[blk_idx] += arr[i];
}
}
------------------------------------SEGMENT
TREE--------------------------------------------
--------------------------------------FENWICK
TREE------------------------------------------
--------------------------------------KMP
AlGO------------------------------------------
--------------------------------------MANCHER"S
ALGO----------------------------------------
vector<int> manacher_odd(string s) {
int n = s.size();
s = "$" + s + "^";
vector<int> p(n + 2);
int l = 1, r = 1;
for(int i = 1; i <= n; i++) {
p[i] = max(0, min(r - i, p[l + (r - i)]));
while(s[i - p[i]] == s[i + p[i]]) {
p[i]++;
}
if(i + p[i] > r) {
l = i - p[i], r = i + p[i];
}
}
return vector<int>(begin(p) + 1, end(p) - 1);
}
vector<int> manacher(string s) {
string t;
for(auto c: s) {
t += string("#") + c;
}
auto res = manacher_odd(t + "#");
return vector<int>(begin(res) + 1, end(res) - 1);
}
