#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()

void solve(){
	int n , k;
	cin >> n >> k;
	ll arr[n];
	for(int i = 0; i < n; i++)cin >> arr[i];
	vector<ll> v;
	ll sum = 0;
	for(int i = 1; i < n; i++){
		v.pb(abs(arr[i] - arr[i-1]));
		sum += v.back();
	}
	sort(all(v));
	for(int groups = 1; groups < k; groups++){
		sum -= v.back();
		v.pop_back();
	}
	cout << sum << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	int t;cin >> t;while(t--)
	solve();
	return 0;
}

#include <iostream>
#include <vector>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()

void solve(){
	int n;
	cin >> n;
	int arr[n];
	for(int i = 0; i < n; i++)cin >> arr[i];
	int cur = arr[0];
	int part = 1;
	for(int i = 0; i < n; i++){
		cur &= arr[i];
		if(cur == 0){
			if(i == n-1)break;
			part++;
			cur = arr[i + 1];
		}
	}
	if(cur != 0)part--;
	part = max(part,1);
	cout << part << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	int t;cin >> t;while(t--)
	solve();
	return 0;
}

At the end of the array, you can only achieve xor of any subarray of the original array.

Now, we maintain a boolean array $$$b$$$ where $$$b_i$$$ is $$$1$$$ if there is some $$$j$$$ such that $$$a_1 \oplus a_2 \oplus \cdots \oplus a_j = i$$$. Initially, $$$b$$$ is all $$$0$$$. We loop $$$j$$$ from $$$1$$$ to $$$n$$$ and check for each $$$k$$$ if $$$b_k=1$$$. If it is, then there is some position $$$p < j$$$ such that $$$a_1 \oplus a_2 \oplus \cdots \oplus a_p = k$$$. If we take xor of range from $$$(p,j]$$$, then it will be $$$k \oplus a_1 \oplus a_2 \oplus \cdots \oplus a_j$$$ (as $$$a_1 \oplus a_2 \oplus \cdots \oplus a_p$$$ gets cancelled). This $$$a_1 \oplus a_2 \oplus \cdots \oplus a_j$$$ can be stored as we loop ahead. We are looping all possible prefix xors and not all prefix positions because $$$n$$$ is large.

Time Complexity — $$$O(n \cdot 2^8)$$$.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int ntest;
    cin >> ntest;
    while (ntest--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &i : a)
            cin >> i;
 
        int const max_value = 1 << 8;
        vector<char> has_pref(max_value);
        has_pref[0] = true;
        int cur_xor = 0;
        int ans = 0;
        for (auto i : a) {
            cur_xor ^= i;
            for (int pref = 0; pref < max_value; ++pref) {
                if (has_pref[pref]) {
                    ans = max(ans, pref ^ cur_xor);
                }
            }
            has_pref[cur_xor] = true;
        }
 
        cout << ans << '\n';
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define all(x) x.begin(),x.end()
 
void solve(){
	int n , m , q;
	cin >> n >> m >> q;
	string st;
	cin >> st;
	vector<pair<int,int>> ranges;
	for(int i = 0; i < m; i++){
		int l , r;
		cin >> l >> r;
		l--;
		r--;
		ranges.pb(mp(l,r));
	}
	set<int> s;
	for(int i = 0; i < n; i++)s.insert(i);
	vector<int> v;
	int pos_in_v[n];
	memset(pos_in_v,-1,sizeof pos_in_v);
	for(int i = 0; i < m; i++){
		auto it = s.lower_bound(ranges[i].vf);
		vector<int> toerase;
		while(it != s.end() && (*it) <= ranges[i].vs){
			toerase.pb((*it));
			v.pb(toerase.back());
			pos_in_v[toerase.back()] = v.size()-1;
			it++;
		}
		while(toerase.size()){
			s.erase(toerase.back());
			toerase.pop_back();
		}
	}
	int cnt = 0;
	for(int i = 0; i < n; i++){
		if(st[i] == '1')cnt++;
	}
	int ans = 0;
	for(int i = 0; i < min(cnt , (int)v.size()); i++){
		if(st[v[i]] == '0')ans++;
	}
	
	while(q--){
		int pos;
		cin >> pos;
		pos--;
		if(pos_in_v[pos] != -1 && pos_in_v[pos] < cnt){
			if(st[pos] == '0'){
				ans--;
			}
			else ans++;
		}
		if(st[pos] == '0'){
			st[pos] = '1';
			cnt++;
			if(cnt <= v.size() && st[v[cnt-1]] == '0')ans++;
		}
		else {
			st[pos] = '0';
			if(cnt > 0 && cnt <= v.size() && st[v[cnt-1]] == '0')ans--;
			cnt--;
		}
		cout << ans << '\n';
	}
}
 
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}