Simplifying the XOR Update:

Consider a simpler problem. Let's say that all values in arr can be either 0 or 1, and even $$$x$$$ can be only 0 or 1.

Now the sum of range $$$[l, r]$$$ is $$$S$$$, which indicates that there are $$$S$$$ 1s and $$$r — l + 1 — S$$$ 0s in $$$[l, r]$$$.

1. An update with $$$x = 0$$$ won’t change anything.
2. An update with $$$x = 1$$$ would flip 0s and 1s, so there will be $$$r - l + 1 - S $$$ 1s and $$$S$$$ 0s. The new sum is:

$$$r - l + 1 - S $$$

Thus, we can build a segment tree with lazy propagation for this array.

Generalizing for the Full Problem:

The key idea is to notice that each number can be at most 30 bits, and we can just maintain such arrays for each of the 30 bits.

So, we build $$$LOGMAX (=30)$$$ such arrays, and for each query:

1. For sum $$$[l, r]$$$, calculate $$${sum}_0, \text{sum}_1, \ldots, \text{sum}_{29}$$$ for each of the trees. The final sum is:

$$$\text{sum}_0 \times 2^0 + \text{sum}_1 \times 2^1 + \ldots + \text{sum}_{29} \times 2^{29}$$$

1. For the update $$$[l, r]$$$ with XOR $$$x$$$, flip $$$[l, r]$$$ for the $$$k^{th}$$$ tree if the $$$k^{th}$$$ bit of $$$x$$$ is set.

#include <bits/stdc++.h>
 
using namespace std;
 
struct LazySegmentTree {
    const int LOGMAX = 30;
    int n;
    vector<int> lazy;
    vector<vector<int>> sum;
    vector<int> L, R;

    LazySegmentTree(vector<int>& arr) {
        int sz = arr.size();
        n = 1;
        while (n < sz) n <<= 1;
        lazy.assign(2 * n, 0);
        sum.assign(2 * n, vector<int>(LOGMAX, 0));
        L.assign(2 * n, 0);
        R.assign(2 * n, 0);


        // Initialize the segment tree leaves
        for (int i = 0; i < sz; ++i) {
            for (int k = 0; k < LOGMAX; ++k) {
                sum[i + n][k] = (arr[i] >> k) & 1;
            }
        }
        for(int i = 0; i < n; ++i){
            L[i + n] = R[i + n] = i;
        }

        // Build the segment tree
        for (int i = n - 1; i > 0; --i) {
            for (int k = 0; k < LOGMAX; ++k) {
                sum[i][k] = sum[2 * i][k] + sum[2 * i + 1][k];
            }
            L[i] = L[2 * i];
            R[i] = R[2 * i + 1];
        }
    }

    void apply(int node, int x) {
        for (int k = 0; k < LOGMAX; ++k) {
            if (x & (1 << k)) {
                sum[node][k] = (R[node] - L[node] + 1) - sum[node][k];
            }
        }
        if (node < n) {
            lazy[node] ^= x;
        }
    }

    void propagate(int node) {
        if (lazy[node]) {
            apply(2 * node, lazy[node]);
            apply(2 * node + 1, lazy[node]);
            lazy[node] = 0;
        }
    }

    void update(int node) {
        for (int k = 0; k < LOGMAX; ++k) {
            sum[node][k] = sum[2 * node][k] + sum[2 * node + 1][k];
        }
    }

    void rangeUpdate(int l, int r, int x) {
        l += n;
        r += n;
        int l0 = l, r0 = r;

        // Apply any existing lazy updates
        for (int i = __lg(n); i >= 1; --i) {
            if ((l >> i) > 0) propagate(l >> i);
            if ((r >> i) > 0) propagate(r >> i);
        }

        // Update the segment tree
        for (; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) apply(l++, x);
            if (!(r & 1)) apply(r--, x);
        }

        // Update affected parent nodes
        for (l = l0 >> 1; l > 0; l >>= 1) propagate(l), update(l);
        for (r = r0 >> 1; r > 0; r >>= 1) propagate(r), update(r);
    }


    long long rangeQuery(int l, int r) {
        l += n;
        r += n;
        long long res = 0;

        // Apply any existing lazy updates
        for (int i = __lg(n); i >= 1; --i) {
            if ((l >> i) > 0) propagate(l >> i);
            if ((r >> i) > 0) propagate(r >> i);
        }

        // Query the segment tree
        for (; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) res += getSum(l++);
            if (!(r & 1)) res += getSum(r--);
        }

        return res;
    }

    long long getSum(int node) {
        long long result = 0;
        for (int k = 0; k < LOGMAX; ++k) {
            result += (1LL << k) * sum[node][k];
        }
        return result;
    }
};
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    LazySegmentTree tree(a);

    int q;
    cin >> q;
    while(q--){
        int type, l, r;
        cin >> type >> l >> r;
        if(type == 1){
            cout << tree.rangeQuery(l, r) << '\n';
        }
        else{
            int x;
            cin >> x;
            tree.rangeUpdate(l, r, x);
        }
    }
    return 0;
}
 

There are A number of days in a year. And you have to perform some type of work in a year. There are M types of work to be performed. And you are given a 2D array B of size M which represents the description for the different types of work.

B[i][0] means the day on which the ith work is given. B[i][1] means the ith work must be completed before this day. B[i][2] denotes the number of days it will take to complete ith work.

Now, on any day, one of these three things can be done — 1. Rest day 2. This is the deadline date for any work (i.e B[i][1]) (nothing can be done on this day) 3. You are performing any one work

If in case you cannot perform all work before the deadline return a vector of size 1 which is [-1] Else return a vector of size A + 1 whose first element is — 1 and the - ith element is 0 if it is a rest day. - ith elment is M + 1 if this day is a deadline for any type of work. - if any type of work is performed on this day then the ith element will be the type of that work. (Types are starting from 1 to m)

Note — On any day there will be a deadline for a most 1 type of work. If more than one type of work can be performed on any day then perform the one having a deadline first.

Problem Constraints: 2 <= A <= 100 1 <= M <= A 1 <= B[i][0] <= B[i][1] <= A 1 <= B[i][2] <= A

The basic idea of my solution is to follow a greedy approach and just try to implement what is given. First marks all the days that are deadlines to certain work with M + 1. They cannot be used anywhere. Then store iterate from day 1 to A. Maintain a minimum priority queue of works that can be done on this day. That is works that have start day on or before this day. Now take the day with smallest deadline(as given in the question) and remove it from priority queue and assign day to this work. Decrease this days duration and if it's still greater than 0 push it back into priority queue.

#include <bits/stdc++.h>
 
using namespace std;
 
//#pragma GCC optimize("Ofast,unroll-loops") 
//#pragma GCC target("avx,avx2,avx512,fma") 
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
 
#define ll long long
#define ld long double
 
#define PI 3.1415926535897932384626433832795l 

// -------------------------<rng>------------------------- 
// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUF(v) shuffle(all(v), RNG); 
// Use mt19937_64 for 64 bit random numbers.
 
 
#define pii  pair<int, int>
vector<int> solve(int A, vector<vector<int>> &b){
    int m = b.size();
    vector<int> start(m + 1), end(m + 1), dur(m + 1);
    for(int i = 0; i < m; ++i){
        start[i + 1] = b[i][0];
        end[i + 1] = b[i][1];
        dur[i + 1] = b[i][2];
    }
    priority_queue<pii, vector<pii>, greater<pii>> pqs, pqe;
    for(int i = 1; i <= m; ++i){
        pqs.push({start[i], i});
    }
    vector<int> ans(A + 1);
    ans[0] = -1;
    bool isPossible = true;
    for(int day = 1; day <= A; ++day){
        while(!pqs.empty() && (pqs.top().first <= day)){
            int id, _;
            tie(_, id) = pqs.top();
            pqs.pop();
            pqe.push({end[id], id});
        }
        if(ans[day] == m + 1){
            continue;
        }
        if(!pqe.empty()){
            int id, _;
            tie(_, id) = pqe.top();
            pqe.pop();
            ans[day] = id;
            if(end[id] < day){
                isPossible = false;
                break;
            }
            --dur[id];
            if(dur[id] != 0){
                pqe.push({end[id], id});
            }
        }
    }
    if(!pqe.empty() || !pqs.empty()){
        isPossible = false;
    }
    if(!isPossible){
        ans.assign(1, -1);
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int A, M;
    cin >> A >> M;
    vector<vector<int>> B(M, vector<int>(3));
    for(int i = 0; i < M; ++i){
        cin >> B[i][0] >> B[i][1] >> B[i][2];
    }
    for(int elem : solve(A, B)){
        cout << elem << ' ';
    }
    cout << '\n';
    
    return 0;
}
 

You are given an integer A and an integer array B, which is the permutation of A integers. Now, you have to perform some swap poerations on this permutation B. Now, after this swap operation B should be such that it can be made to identity permutation by exactly C swaps (which is minimum required)

You have to return a 2D array D which denotes the minimum swaaps you have to perform so that B will become identity after exactly C swaps. D[i][0] adn D[i][1] deontes the index of swap operation you are performing. Return the lexicographically smallest array D.

If you don't need to perform any swap operation then return D = -1, -1

Note — Identity permutation is a permutation where B[i] = i, for each 1 <= i <= A

Problem Constraints: 1 <= A <= 3000 0 <= C < A

Please go through this blog before continuing if you are new to permutations. The basic idea is that since we want a permutation that can be transformed to identity in exactly C transformations at minimum, then that permutation must have exactly N — C cycles, where N is size of the permutation. Let r = N — C = required number of cycles. and nc = number of cycles in the given permutation

Now there are two cases:

Case 1 : nc >= r In this case we need to merge cycles till we get exactly r cycles. Each merge reduces number of cycles by 1 so we must perform nc — r merges. Now each merge can be performed by swapping two elements in different cycles. What we do is we take the minimum element in each cycle as it's head. Then we swap the two smalles heads for each of teh nc — r merges and remove the second smallest head. I have used priority_queue for this. However it's also possible to do this by simply sorting an array of heads.

Case 2: nc < r In this case we have to split cycles till we get exactly r cycles. How do we split a cycle ? By swapping two elements in that cycle.

To split a cycle, we perform swaps between two elements within the cycle. This splitting process continues until each cycle contains a single element.

The key challenge here is to ensure the swaps are performed in a way that generates a lexicographically smallest array of swaps D.

To achieve this, we aim to minimize the value of the first element in each cycle, which leads to a lexicographically smaller result.

We repeatedly swap the minimum and second minimum elements within a cycle to achieve this goal. Finally we sort the array of swaps and take the first r — nc swaps because we wish to perform only r — nc merges.

#include <bits/stdc++.h>
 
using namespace std;
 
//#pragma GCC optimize("Ofast,unroll-loops") 
//#pragma GCC target("avx,avx2,avx512,fma") 
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
 
#define ll long long
#define ld long double
 
#define PI 3.1415926535897932384626433832795l 

// -------------------------<rng>------------------------- 
// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUF(v) shuffle(all(v), RNG); 
// Use mt19937_64 for 64 bit random numbers.
 
vector<vector<int>> getCycles(vector<int> &p){
    int n = p.size();
    vector<bool> vis(n);
    vector<int> ind(n);

    for(int i = 0; i < n; ++i){
        --p[i];
        ind[p[i]] = i;
    }

    vector<vector<int>> cycles;
    for(int i = 0; i < n; ++i){
        if(vis[i]){
            continue;
        }
        int cur = i;
        vector<int> c;
        while(!vis[cur]){
            vis[cur] = true;
            c.push_back(cur);
            cur = ind[cur];
        }
        cycles.push_back(c);
    }
    for(auto &c : cycles){
        for(auto &ind : c){
            ++ind;
        }
    }
    return cycles;
}
 
vector<vector<int>> solve(vector<int> &p, int k) {
    int n = p.size();
    vector<vector<int>> ans;
    // all cycles cycles
    vector<vector<int>> cycles = getCycles(p);

    // req cycles
    int req_cycles = n - k;
    int no_cycles = cycles.size();
    if(req_cycles < no_cycles){
        ll diff = cycles.size() - req_cycles;
        priority_queue<int, vector<int>, greater<int>> pq;
        for(auto c : cycles){
            pq.push(c.front());
        }
        while(diff--){
            int u = pq.top();
            pq.pop();
            int v = pq.top();
            pq.pop();
            ans.push_back({u, v});
            pq.push(u);
        }
    }
    else if(req_cycles > no_cycles){
        while(!cycles.empty()){
            vector<int> c = cycles.back();
            cycles.pop_back();
            if(c.size() == 1){
                continue;
            }
            if(c.size() == 2){
                ans.push_back({c[0], c[1]});
                continue;
            }
            int mn_ind = min_element(c.begin() + 1, c.end()) - c.begin();
            ans.push_back({c[0], c[mn_ind]});
            vector<int> c1, c2;
            c1.push_back(c[0]);
            for(int i = mn_ind + 1; i < no_cycles; ++i){
                c1.push_back(c[i]);
            }
            c2.push_back(c[mn_ind]);
            for(int i = 1; i < mn_ind; ++i){
                c2.push_back(c[i]);
            }
            cycles.push_back(c1);
            cycles.push_back(c2);
        }
        int diff = req_cycles - no_cycles;
        sort(ans.begin(), ans.end());
        ans.resize(diff);
    }
    if(ans.empty()){
        ans = {{-1, -1}};
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for(int i = 0; i < n; ++i){
        cin >> p[i];
    }
    for(auto v : solve(p, k)){
        cout << v[0] << ' ' << v[1] << '\n';
    }
    
    return 0;
}
 

You are given an 2D array A which indicates |A| segments covered. ith segment cover integer points from A[i][0] to A[i][1] inclusive.

Now, your task is to find the number of integer points that are covered by exactly i number of segments for each 1 <= i <= |A|.

Return an arrray B of size |A| + 1, where B[i] denotes the number of integer points that are covered by exactly i segments.

Note: B[0] must be equal to 0.

Problem Constraints 1 <= |A| <= 2 * (10 ** 5) 0 <= A[i][0] <= A[i][1] <= 10 ** 18

This is a bit of modified version of the prefix sum solution which would work for r <= 10**5. Other solutions using sweepline algorithms not requiring maps also exist.

#include <bits/stdc++.h>
 
using namespace std;
 
//#pragma GCC optimize("Ofast,unroll-loops") 
//#pragma GCC target("avx,avx2,avx512,fma") 
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
 
#define ll long long
#define ld long double
 
#define PI 3.1415926535897932384626433832795l 

// -------------------------<rng>------------------------- 
// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUF(v) shuffle(all(v), RNG); 
// Use mt19937_64 for 64 bit random numbers.
 
 
vector<ll> solve(vector<vector<ll>> &a) {
    int n = a.size();
    vector<ll> ans(n + 1);
    map<ll, ll> points;

    for(auto &v : a){
        ll l = v[0], r = v[1];
        ++points[l];
        --points[r + 1];
    }
    ll cur_points = 0;
    ll prev_ind = -1;
    for(auto [ind, p] : points){
        if(cur_points > 0){
            ans[cur_points] += ind - prev_ind;
        }
        prev_ind = ind;
        cur_points += p;
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<vector<ll>> a(n);
    for(int i = 0; i < n; ++i){
        ll l, r;
        cin >> l >> r;
        a[i] = {l, r};
    }
    for(auto u : solve(a)){
        cout << u << ' ';
    }

    return 0;
}