coordinate compression

int n = a.size();
vector<pair<int, int>> pairs(n);
for(int i = 0; i < n; ++i) {
    pairs[i] = {a[i], i};
}
sort(pairs.begin(), pairs.end());
int nxt = 0;
for(int i = 0; i < n; ++i) {
    if(i > 0 && pairs[i-1].first != pairs[i].first) nxt++;
    a[pairs[i].second] = nxt;
}

Min Heap priority_queue

 priority_queue <int, vector<int>, greater<int> > pq; 

MEX with trie

int mex(int x) {
        int cur = root;
        int m = 0;
        for (int i = N; i >= 0; i--) {
            int b = (x >> i) & 1;
            if (TRIE[cur].child[b] == -1) return m;
            if (TRIE[TRIE[cur].child[b]].freq == (1 << i)) {
                b ^= 1;
                m ^= (1 << i);
            }
            if (TRIE[cur].child[b] == -1) return m;
            cur = TRIE[cur].child[b];
        }
        assert(false);
    }

Digit DP

/// integers between a and b where no two adjacent digits are the same.
///<https://cses.fi/problemset/task/2220>

#include <bits/stdc++.h>
using namespace std;

#define int long long int

vector<int> num;
int a, b, d, k;
int DP[20][12][2][2];
/// DP[p][c][lz][f] = Number of valid numbers <= b from this state
/// p = current position from left side (zero based)
/// c = number of times we have placed the digit d so far
/// f = the number we are building has already become smaller than b? [0 = no, 1 = yes]
/// lz= lead zero
int call(int pos, int x,  bool lz, bool f) {

	if (pos >= num.size()) {

		return 1;
	}

	if (x != -1 and DP[pos][x][lz][f] != -1)return DP[pos][x][lz][f];

	int res = 0;

	int LMT;

	LMT = f ? num[pos] : 9;

	/// Try to place all the valid digits such that the number doesn't exceed b
	for (int dgt = 0; dgt <= LMT; dgt++) {
		//We  have a number with same consecutive digits which is NOT the case
		//of consecutive leading zeroes
		if (x == dgt and lz == 0)continue;
		//answer gets incremented by the number of possible n - 1 digit
		//integers that can follow our current digit
		res += call(pos + 1, dgt, (lz and dgt == 0), (f and dgt == LMT));

	}
	// return res;

	return DP[pos][x][lz][f] = res;
}

int solve(int b) {

	if (b < 0)return 0;
	num.clear();
	while (b > 0) {
		num.push_back(b % 10);
		b /= 10;
	}
	reverse(num.begin(), num.end());
	/// Stored all the digits of b in num for simplicity

	memset(DP, -1, sizeof(DP));
	int res = call(0, -1, 1, 1);
	return res;
}

int32_t main () {

	cin >> a >> b;
	int res = solve(b) - solve(a - 1);
	cout << res << endl;

	return 0;
}

NCR

const int MOD = 998244353;
const int MAX = 3e5 + 5;
long long inv(long long a, long long b=MOD){
 return 1<a ? b - inv(b%a,a)*b/a : 1;
}
int fct[MAX],iv[MAX];
void pre()
{
    fct[0]=1;
    for(int i=1;i<=MAX - 1;i++)
    {
        fct[i]=(fct[i-1]*i)%MOD;
    }
    iv[MAX - 1]=inv(fct[MAX - 1]);
    for(int i=MAX - 2;i>=0;i--)
    {
        iv[i]=(iv[i+1]*(i+1))%MOD;
    }
}
int ncr(int n,int r)
{
    if(r>n)
        return 0;
    return (((fct[n]*iv[r])%MOD)*iv[n-r])%MOD;
}

Given **n** segments on a line, each described by a pair of coordinates (ai1,ai2) we have to find the length of their union.

int length_union(const vector<pair<int, int>> &a) {
    int n = a.size();
    vector<pair<int, bool>> x(n*2);
    for (int i = 0; i < n; i++) {
        x[i*2] = {a[i].first, false};
        x[i*2+1] = {a[i].second, true};
    }

    sort(x.begin(), x.end());

    int result = 0;
    int c = 0;
    for (int i = 0; i < n * 2; i++) {
        if (i > 0 && x[i].first > x[i-1].first && c > 0)
            result += x[i].first - x[i-1].first;
        if (x[i].second)
            c--;
        else
            c++;
    }
    return result;
}

sum of absolute differences of all pairs

contribution(arr[i])=arr[i]×(2i−n+1)

Divisors N log N(1e6)