Amar Jyoti kachari Jangwa

## LIS "Length"O(nLog(n) ).cpp
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

int a,num[120000],n,ans[120000],sz;

int main(){
	while (scanf("%d",&n) == 1){

## Segment Tree Lazy Propagation.cpp
#include<iostream>
#include<algorithm>
using namespace std;

#include<string.h>
#include<math.h>

#define N 20
#define MAX (1+(1<<6)) // Why? :D
#define inf 0x7fffffff

## 2D BIT.cpp
void update(int x , int y , int val){
	while (x <= max_x){
		updatey(x , y , val);
		// this function should update array tree[x]
		x += (x & -x);
	}
}

void updatey(int x , int y , int val){
	while (y <= max_y){

## Binary Indexed Tree.cpp
Isolating the last digit
NOTE: Instead of "the last non-zero digit," it will write only "the last digit."

There are times when we need to get just the last digit from a binary number, so we need an efficient way to do that. Let num be the integer whose last digit we want to isolate. In binary notation num can be represented as a1b, where a represents binary digits before the last digit and b represents zeroes after the last digit.

Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. b consists of all zeroes, so b¯ consists of all ones. Finally we have
-num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0...0)¯ + 1 = a¯0(1...1) + 1 = a¯1(0...0) = a¯1b.
Now, we can easily isolate the last digit, using bitwise operator AND (in C++, Java it is &) with num and -num:

        a1b

## Fast Input.cpp
#define getcx getchar_unlocked
inline void inp( int &n )//fast input function
{
   n=0;
   int ch=getcx();int sign=1;
   while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}

   while(  ch >= '0' && ch <= '9' )
           n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
   n=n*sign;

## nCr With MOD.cpp

#include<iostream>
using namespace std;
#include<vector>
/* This function calculates (a^b)%MOD */
long long pow(int a, int b, int MOD)
{
    long long x=1,y=a;
    while(b > 0)
    {

## RANGE QUERY with Sparse Table (ST) algorithm.cpp
RANGE QUERY

Given a (big) array r[0..n-1], and a lot of queries of certain type. We may want to pre-process the data so that each
query can be performed fast. In this section, we use T (f, g) to denote the running time for an algorithm is O(f(n))
for pre-processing, and O(g(n)) for each query.

If the queries are of type getsum(a, b), which asks the sum of all the elements between a and b, inclusive,
we have a T (n, 1) algorithm: Compute s[i] to be the sum from r[0] to r[i-1], inclusive, then getsum(a,b) simply
returns s[b+1]-s[a].

## KMP.cpp
The Naive pattern searching algorithm doesn’t work well in cases where we see many matching characters followed by
a mismatching character. Following are some examples.

   txt[] = "AAAAAAAAAAAAAAAAAB"
   txt[] = "ABABABCABABABCABABABC"
   lps[i] = the longest proper prefix of pat[0..i] Searching Algorithm:Preprocessing Algorithm:
   if (pattern[0] == '\0')     /* Construct the lookup table */     /* Perform the search */     free(T);

   pat[] = "AAAAB"

## Josephus Problem.cpp


Iterative version

int jos(int K,int N)
{
        int r =0;
        for(int i=1;i<=N;i++)
       {
	#include <iostream>
	#include <vector>
	#include <cstdio>
	#include <algorithm>
	using namespace std;

	int a,num[120000],n,ans[120000],sz;

	int main(){
	while (scanf("%d",&n) == 1){
	#include<iostream>
	#include<algorithm>
	using namespace std;

	#include<string.h>
	#include<math.h>

	#define N 20
	#define MAX (1+(1<<6)) // Why? :D
	#define inf 0x7fffffff
	void update(int x , int y , int val){
	while (x <= max_x){
	updatey(x , y , val);
	// this function should update array tree[x]
	x += (x & -x);
	}
	}

	void updatey(int x , int y , int val){
	while (y <= max_y){
	Isolating the last digit
	NOTE: Instead of "the last non-zero digit," it will write only "the last digit."

	There are times when we need to get just the last digit from a binary number, so we need an efficient way to do that. Let num be the integer whose last digit we want to isolate. In binary notation num can be represented as a1b, where a represents binary digits before the last digit and b represents zeroes after the last digit.

	Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. b consists of all zeroes, so b¯ consists of all ones. Finally we have
	-num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0...0)¯ + 1 = a¯0(1...1) + 1 = a¯1(0...0) = a¯1b.
	Now, we can easily isolate the last digit, using bitwise operator AND (in C++, Java it is &) with num and -num:

	a1b
	#define getcx getchar_unlocked
	inline void inp( int &n )//fast input function
	{
	n=0;
	int ch=getcx();int sign=1;
	while( ch < '0' \|\| ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}

	while( ch >= '0' && ch <= '9' )
	n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
	n=n*sign;

	#include<iostream>
	using namespace std;
	#include<vector>
	/* This function calculates (a^b)%MOD */
	long long pow(int a, int b, int MOD)
	{
	long long x=1,y=a;
	while(b > 0)
	{
	RANGE QUERY

	Given a (big) array r[0..n-1], and a lot of queries of certain type. We may want to pre-process the data so that each
	query can be performed fast. In this section, we use T (f, g) to denote the running time for an algorithm is O(f(n))
	for pre-processing, and O(g(n)) for each query.

	If the queries are of type getsum(a, b), which asks the sum of all the elements between a and b, inclusive,
	we have a T (n, 1) algorithm: Compute s[i] to be the sum from r[0] to r[i-1], inclusive, then getsum(a,b) simply
	returns s[b+1]-s[a].
	The Naive pattern searching algorithm doesn’t work well in cases where we see many matching characters followed by
	a mismatching character. Following are some examples.

	txt[] = "AAAAAAAAAAAAAAAAAB"
	txt[] = "ABABABCABABABCABABABC"
	lps[i] = the longest proper prefix of pat[0..i] Searching Algorithm:Preprocessing Algorithm:
	if (pattern[0] == '\0') /* Construct the lookup table / / Perform the search */ free(T);

	pat[] = "AAAAB"



	Iterative version

	int jos(int K,int N)
	{
	int r =0;
	for(int i=1;i<=N;i++)
	{