# Basic algorithm template (Acwing)

## 1. Quick sorting( Acwing 785. Quick sort)

```void quick_sort(int a[],int l,int r)
{
if(l>=r)return;
int i=l-1,j=r+1,x=l+r>>1;//'+' takes precedence over '>' shift operator
while(i<j)
{
do i++;while(a[i]<x);
do j--;while(a[j]>x);
if(i<j) swap(a[i],a[j]);
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
```

Analysis:
1. Set an X to divide the array into two arrays;
2. Set two pointers i and j close to each other from both ends of the head and tail respectively, and put the data smaller than x on the left side of X, and the data larger than x on the right side of X. When the two hands meet, continue to the next step;
3. Continue the above operations with the data on the left and the data on the right;
4. Repeat the above process, and it can be seen that this is a recursive process; when the data on the left and right sides are in order, the whole array will be in order naturally.

## 2. Merge and sort Acwing 787. Merge sort

```void merge_sort(int a[],int l,int r)
{
if(l>=r)return;
int mid=l+r>>1;
merge_sort(a,l,mid);
merge_sort(a,mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r)
{
if(q[i]<q[j])tmp[k++]=q[i++];
else
tmp[k++]=q[j--];
}
while(i<=mid)tmp[k++]=q[i++];
while(j<=r)tmp[k++]=q[j--];
for(int i=l,k=0;i<=r;i++)
q[k++]=tmp[i++];
}
```

## 3. Integer binary algorithm template Acwing 789. Number range

```bool check(int x)
{
/* ... */
}//Check whether x satisfies certain properties
//Use when the interval [l,r] is divided into [l,mid] and [mid+1,r]
int bsearsh_1(int l,int r)
{
while(l<r){
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
return l;
}
//Use when the interval [l,r] is divided into [l,mid-1] and [mid,r]
int bsearsh_2(int l,int r)
{
while(l<r){
int mid=l+r+1>>1;
if(check(mid))l=mid;
r=mid-1;
}
return l;
}
```

## 4. Floating point binary template The cubic root of Acwing 790

```bool check(int x)
{
/*  */
}//Check whether x obeys certain properties
double bsearsh(double l,double r)
{
const double e=1e-6;
while(l<r)
{
double mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
return l;
}
```

```//C=A+B,A>=0,B>=0
{
int t=0;
vector<int> C;
for(int i=0;i<A.size();i++)
{
t+=A[i];
if(i<B.size())t+=B[i];
C.push_back(t%10);
t/=10;
}
if(t)C.push_back(t);
return C;
}
```

## 6. High precision subtraction Acwing 792. High precision subtraction

```//C=A-B,A>=B,A>=0,B>=0
vector<int>sub(vector<int> &A,vector<int> &B)
{
if(A.size()<B.size()) return sub(B,A);
vector<int> C;
for(int i=0,t=0;i<A.size();i++)
{
t=A[i]-t;
if(i<B.size())t-=B[i];
C.push_back(t+10%10);
if(t<0) t=1;
else t=0;
}
return C;
}
```

## 7. High precision multiplied by low precision Acwing 793. High precision multiplication

```//C=A*b,A>0,b>0
vector<int>mul(vector<int> &A,int b)
{
vector<int> C;
int t=0;
for(int i=0;i<A.size()||t;i++)
{
if(i<A.size())t+=b*A[i];
C.push_back(t%10);
t/=10;
}
return C;
}
```

## 8. High precision divided by low precision Acwing 794. High precision Division

```//C=A*b,A>0,b>0
vector<int>div(vector<int> &A,int b)
{
vector<int> C;
int r=0;
for(int i=A.size()-1;i>=0;i--)
{
r=r*10+A[i];
C.push_back(r/b);
r%=b;
}
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0)C.pop_back();
return C;
}
```

## 9. One dimensional prefix and Acwing 795. Prefix and

```S[i]=a[1]+a[2]+...a[i]
a[l]+...+a[r]=S[r]-S[l-1]
```

## 10. Two dimensional prefix and Acwing 796. Sum of submatrix

```S[i,j] = sum of all elements in the upper left part of column j of row i
Taking (x1,y1) as the upper left corner and (x2,y2) as the lower right corner, the sum of submatrixes is:
S[x2,y2]-S[x1-1,y1-1]+S[x2,y1-1]+S[x1-1,y1-1]
```

## 11. One dimensional difference Acwing 797. Differential

```Add c:B[l]+=c,B[r+1]-=c to each number in the interval [l,r]
```

## 12. Two dimensional difference Acwing 798. Difference matrix

```Given that (x1,y1) is the upper left corner, (x2,y2) is all elements in the submatrix of the lower right corner plus c:
S[x1,y1]+=c,S[x2+1,y1]-=c,S[x1,y2+1]-=c,S[x2+1,y2+1]+=c
```

## 13. bit operation Acwing 801. Number of 1 in binary

```Find the number k of N: n > > K-1
Returns the last bit of N: lowbit (n) = n & - n
```

## 14. Double pointer algorithm Acwing 799. Longest continuous disrepeat subsequence，Acwing 800. Target and

```for(int i=0,j=0;i<n;i++)
{
while(j<i&&check(i,j)) j++;
//The logic of specific problems
}
Common classification questions:
(1) For a sequence, maintain an interval with two pointers
(2) For two sequences, maintain a certain order, such as merging two ordered sequences in merge sort

```

## 15. discretization Acwing 802. Interval and

```vector<int> alls;//Store all values to be discretized
sort(alls.begin(),alls.end());//Sort all values
alls.erase(unique(alls.begin(),alls.end()));//Remove duplicate elements

//Bisection to find the value of x corresponding to discretization
int find(int x)//Find the first position greater than or equal to x
{
int l=0,r=all.size()-1;
while(l<r)
{
int mid=l+r>>1;
if(alls[mid]>=x)r=mid;
else  l=mid+1;
}
return r+1;//Map to 1, 2,... n
}
```

## 16. Interval consolidation Acwing 803. Interval merging

```//Merge all intervals with intersection
typedef pair<int, int> PII;
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(),segs.end());
int st=-2e9,ed=-2e9;
for(auto seg:segs)
if(ed<seg.first)
{
if(st!=-2e9)  res.push_back({st,ed});
st=seg.first,seg.second;
}
else
ed=max(ed,seg.second);
if(st!=-2e9)res.push_back({st,ed});
segs=res;
}
```
Published 18 original articles, won praise 0, visited 415

Added by Ghettobusta on Mon, 27 Jan 2020 10:06:10 +0200