Любой массив можно отсортировать не более, чем за $$$\frac{n(n-1)}2$$$ операций. Подумайте либо угадайте, в каком случае понадобится ровно $$$\frac{n(n-1)}2$$$.

#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';
    }
}

Придумайте простой критерий, когда a_i & a_j >= a_i ^ a_j, рассмотрев биты от старшего к младшему. Примените его, чтобы быстро вычислить ответ.

#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';
    }
}

Используйте динамическое программирование.

#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;
}

Здесь динамическое программирование не сработает. Подумайте, выгодно ли брать в ответ что-либо, кроме локальных минимумов и максимумов.

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';
        }
    }
}

Пересечение любых $$$k$$$ отрезков либо пусто, либо дает отрезок. Зафиксируйте левую границу пересечения и посчитайте количество наборов из $$$k$$$ отрезков, у которых пересечение начинается в этой левой границе.

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();
	}
}

Давайте вместо массива из нулей и единиц будем хранить количество нулей между каждой парой соседних единиц. Как тогда будут выглядеть операции обмена? А как посчитать защищенность армии в таком случае?

Пусть нам дан исходный массив и конечный. Подумайте, за сколько операций можно первый превратить во второй.

Соедините все вместе и напишите ДП.

#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;
}