Any array can be sorted using no more than $$$\frac{n(n-1)}2$$$ operations. Think or guess when we need exactly $$$\frac{n(n-1)}2$$$ operations.

#include<iostream>

using namespace std;

int a[1000000+5];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while (t--)
    {
        int n;
        cin>>n;
        for (int i=0; i<n; i++)
        {
            cin>>a[i];
        }
        bool can=false;
        for (int i=1; i<n; i++)
        {
            if (a[i]>=a[i-1])
            {
                can=true;
                break;
            }
        }
        if (can) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
}

Think of a simple criteria when a_i & a_j >= a_i ^ a_j by considering the bits from highest to lowest. Apply your observations to calculate the answer fast.

#include<iostream>
#include<vector>
#include<algorithm>
#include<ctime>
#include<random>

using namespace std;

mt19937 rnd(time(NULL));

int a[1000000+5];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while (t--)
    {
        int n;
        cin>>n;
        for (int i=0; i<n; i++)
        {
            cin>>a[i];
        }
        int64_t ans=0;
        for (int j=29; j>=0; j--)
        {
            int64_t cnt=0;
            for (int i=0; i<n; i++)
            {
                if (a[i]>=(1<<j)&&a[i]<(1<<(j+1)))
                {
                    cnt++;
                }
            }
            ans+=cnt*(cnt-1)/2;
        }
        cout<<ans<<'\n';
    }
}

Use dynamic programming.

#include <iostream>
#include <vector>

using namespace std;

inline int64_t calc(const vector<int> &a) {
	int n = a.size();
	vector<int64_t> d1(n+1), d2(n+1);
	d1[0] = -static_cast<int64_t>(1e18);
	d2[0] = 0;
	for (int i = 0; i < n; ++i) {
		d1[i+1] = max(d1[i], d2[i] + a[i]);
		d2[i+1] = max(d2[i], d1[i] - a[i]);
	}
	return max(d1.back(), d2.back());
}

int main() {
	ios_base::sync_with_stdio(false);
	int t; cin >> t;
	while (t--) {
		int n, q; cin >> n >> q;
		vector<int> a(n);
		for (int i = 0; i < n; ++i) {
			cin >> a[i];
		}
		cout << calc(a) << "\n";
		for (int i = 0; i < q; ++i) {
			int l, r; cin >> l >> r; --l; --r;
			swap(a[l], a[r]);
			cout << calc(a) << "\n";
		}
	}
	return 0;
}

The dynamic programming doesn't work here. Consider taking only local minima and maxima and think whether we need to take something else.

import java.io.*;
import java.util.*;

public class C2_Java {
    int[] a;
    int n;
    long ans;
    
    void add(int i, int sign) {
        if (i == 0 || i == n+1) return;
        if (a[i-1] < a[i] && a[i] > a[i+1]) ans += sign * a[i];
        if (a[i-1] > a[i] && a[i] < a[i+1]) ans -= sign * a[i];
    }
    
    void addTwo(int l, int r, int sign) {
        if (l == r) return;
        if (l+1 == r) {
            add(l-1, sign);
            add(l, sign);
            add(r, sign);
            add(r+1, sign);
            return;
        }
        add(l-1, sign);
        add(l, sign);
        add(l+1, sign);
        if (l+2 != r) add(r-1, sign);
        add(r, sign);
        add(r+1, sign);
    }
    
    public void run() throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer tok = new StringTokenizer(in.readLine());
        int t = Integer.parseInt(tok.nextToken());
        while (t --> 0) {
            tok = new StringTokenizer(in.readLine());
            n = Integer.parseInt(tok.nextToken());
            int q = Integer.parseInt(tok.nextToken());
            a = new int[n + 2];
            tok = new StringTokenizer(in.readLine());
            for (int i = 1; i <= n; ++i) {
                a[i] = Integer.parseInt(tok.nextToken());
            }
            a[0] = -1;
            a[n+1] = -1;
            ans = 0;
            StringBuilder builder = new StringBuilder();
            for (int i = 1; i <= n; ++i) {
                if (a[i-1] < a[i] && a[i] > a[i+1]) ans += a[i];
                if (a[i-1] > a[i] && a[i] < a[i+1]) ans -= a[i];
            }
            builder.append(ans).append("\n");
            while (q --> 0) {
                tok = new StringTokenizer(in.readLine());
                int l = Integer.parseInt(tok.nextToken());
                int r = Integer.parseInt(tok.nextToken());
                if (l == r) {
                    builder.append(ans).append("\n");
                    continue;
                }
                addTwo(l, r, -1);
                int tmp = a[l];
                a[l] = a[r];
                a[r] = tmp;
                addTwo(l, r, +1);
                builder.append(ans).append("\n");
            }
            out.write(builder.toString());   
        }
        
        in.close();
        out.close();        
    }

    public static void main(String[] args) throws IOException {
        (new C2_Java()).run();
    }
}

#include<iostream>

using namespace std;

#define int long long

int a[1000000+5];

int n;

int ans=0;

inline void insert(int i)
{
    if (i==0||i==n+1) return;
    if (a[i-1]<a[i]&&a[i]>a[i+1]) ans+=a[i];
    if (a[i-1]>a[i]&&a[i]<a[i+1]) ans-=a[i];
}

inline void erase(int i)
{
    if (i==0||i==n+1) return;
    if (a[i-1]<a[i]&&a[i]>a[i+1]) ans-=a[i];
    if (a[i-1]>a[i]&&a[i]<a[i+1]) ans+=a[i];
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while (t--)
    {
        int q;
        cin>>n>>q;
        for (int i=1; i<=n; i++)
        {
            cin>>a[i];
        }
        a[0]=-1;
        a[n+1]=-1;
        ans=0;
        for (int i=1; i<=n; i++)
        {
            if (a[i-1]<a[i]&&a[i]>a[i+1]) ans+=a[i];
            if (a[i-1]>a[i]&&a[i]<a[i+1]) ans-=a[i];
        }
        cout<<ans<<'\n';
        while (q--)
        {
            int l,r;
            cin>>l>>r;
            erase(l-1);
            erase(l);
            erase(l+1);
            if (l!=r)
            {
                if (r-1!=l+1&&r-1!=l) erase(r-1);
                if (r!=l+1) erase(r);
                erase(r+1);
            }
            swap(a[l],a[r]);
            insert(l-1);
            insert(l);
            insert(l+1);
            if (l!=r)
            {
                if (r-1!=l+1&&r-1!=l) insert(r-1);
                if (r!=l+1) insert(r);
                insert(r+1);
            }
            cout<<ans<<'\n';
        }
    }
}

The intersection of any $$$k$$$ segments is either empty or is a segment. Let's fix the left bound of the intersection and calculate the number of sets of $$$k$$$ segments such that their intersection starts in this left bound.

import java.io.*;
import java.util.*;

public class D_Java {
	public static final int MOD = 998244353;
	
	public static int mul(int a, int b) {
		return (int)((long)a * (long)b % MOD);
	}
	
	int[] f;
	int[] rf;
	
	public int C(int n, int k) {
		return (k < 0 || k > n) ? 0 : mul(f[n], mul(rf[n-k], rf[k]));
	}
	
	public static int pow(int a, int n) {
		int res = 1;
		while (n != 0) {
			if ((n & 1) == 1) {
				res = mul(res, a);
			}
			a = mul(a, a);
			n >>= 1;
		}
		return res;
	}
	
	static void shuffleArray(int[] a) {
		Random rnd = new Random();
		for (int i = a.length-1; i > 0; i--) {
			int index = rnd.nextInt(i + 1);
			int tmp = a[index];
			a[index] = a[i];
			a[i] = tmp;
		}
	}
	
	public static int inv(int a) {
		return pow(a, MOD-2);
	}
	
	public void doIt() throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer tok = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(tok.nextToken());
		int k = Integer.parseInt(tok.nextToken());
		
		f = new int[n+42];
		rf = new int[n+42];
		f[0] = rf[0] = 1;
		for (int i = 1; i < f.length; ++i) {
			f[i] = mul(f[i-1], i);
			rf[i] = mul(rf[i-1], inv(i));
		}
		
		int[] events = new int[2*n];
		for (int i = 0; i < n; ++i) {
			tok = new StringTokenizer(in.readLine());
			int le = Integer.parseInt(tok.nextToken());
			int ri = Integer.parseInt(tok.nextToken());
			events[i] = le*2;
			events[i + n] = ri*2 + 1;
		}
		shuffleArray(events);
		Arrays.sort(events);
		
		int ans = 0;
		int balance = 0;
		for (int r = 0; r < 2*n;) {
			int l = r;
			while (r < 2*n && events[l] == events[r]) {
				++r;
			}
			int added = r - l;
			if (events[l] % 2 == 0) {
				// Open event
				ans += C(balance + added, k);
				if (ans >= MOD) ans -= MOD;
				ans += MOD - C(balance, k);
				if (ans >= MOD) ans -= MOD;
				balance += added;
			} else {
				// Close event
				balance -= added;
			}
		}
		
		in.close();
		System.out.println(ans);
	}
	
	public static void main(String[] args) throws IOException {
		(new D_Java()).doIt();
	}
}

Let's keep the number of zeroes between any pair consecutive ones instead of the original array of zeroes and ones. How will the swap operation look in this case. How to calculate the protection?

Suppose we have the initial array and the final array. Think of the number of operations you need to make the first one equal to the second one.

Join all your observations together and use DP.

#include <cassert>
#include <climits>
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

template<typename T>
inline void umin(T &a, const T &b) {
	a = min(a, b);
}

template<typename T>
inline void umax(T &a, const T &b) {
	a = max(a, b);
}

int main() {
	ios_base::sync_with_stdio(false);
	
	int n; cin >> n;
	vector<int> a(n);
	for (int &x : a) {
		cin >> x;
	}
	a.push_back(1);
	
	vector<int> gg;
	for (int i = 0; i <= n; ++i) {
		int s = i;
		while (a[i] == 0) ++i;
		gg.push_back(i - s);
	}
	
	vector<int> p = gg;
	partial_sum(begin(p), end(p), begin(p));
	
	constexpr int mx = 103;
	constexpr int dx = mx + 1, dy = mx + 1, dz = mx * (mx + 1) / 2 + 1;
	static int dp[dx][dy][dz] = {};
	
	for (int i = 0; i < dx; ++i) {
		for (int j = 0; j < dy; ++j) {
			for (int k = 0; k < dz; ++k) {
				dp[i][j][k] = INT_MAX;
			}
		}
	}
	dp[0][0][0] = 0;
	
	int k = gg.size(), l = p.back();
	for (int i = 0; i < k; ++i) {
		for (int j = 0; j <= l; ++j) {
			for (int s = 0; s <= n * (n-1) / 2; ++s) {
				if (dp[i][j][s] == INT_MAX) continue;
				for (int q = j; q <= l; ++q) {
					umin(dp[i+1][q][s + abs(q - p[i])], dp[i][j][s] + (q-j)*(q-j));
				}
			}
		}
	}
	
	int mn = INT_MAX;
	for (int s = 0; s <= n * (n-1) / 2; ++s) {
		umin(mn, dp[k][l][s]);
		int val = l*l - mn;
		assert(val % 2 == 0);
		cout << val/2 << " ";
	}
	cout << endl;
	
	return 0;
}