#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	scanf("%d", &n);

	vector <int> in(n);
	vector <int> is(N);

	for(auto &p: in)
		scanf("%d", &p);
	
	for(int i = 0; i < n; ++i)
		for(int j = i + 1; j < n; ++j)
			is[in[j] - in[i]] = true;
	
	int ans = 0;
	for(auto &v: is)
		ans += v;
	printf("%d\n", ans);
}

int main() {
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	scanf("%d", &n);

	vector <int> in(n);
	for(auto &p: in)
		scanf("%d", &p);
	
	set <int> S;
	for(int i = 0; i < n; ++i)
		for(int j = i + 1; j < n; ++j)
			S.insert(in[j] - in[i]);

	printf("%d\n", (int)S.size());
}

int main() {
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

Try to solve it for $$$n, x_i \leq 10^5$$$.

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	scanf("%d", &n);
	
	int ans = 0;
	int prv = 0, ok = 0;
	
	for(int i = 1; i <= n; ++i) {
		int a;
		scanf("%d", &a);
		
		ans += (a != prv);
		ok |= (a == prv);
		
		if(prv + 1 < a)
			ans += ok, ok = 0;
		prv = a;
	}
	
	ans += ok;
	printf("%d\n", ans);
}

int main() {
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	scanf("%d", &n);

	set <int> S;
	for(int i = 1; i <= n; ++i) {
		int v;
		scanf("%d", &v);

		if(S.count(v))
			v++;
		S.insert(v);
	}
	
	printf("%d\n", (int)S.size());
}

int main() {
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

Can you solve it if we can increase note $$$x_i$$$ by any integer in $$$[0, k_i]$$$, for given $$$k_i$$$?

#include <bits/stdc++.h>

using namespace std;

const int N = 100 * 1000 + 7;

int n;
char in[N];
bool used[N];

void solve(){
	scanf("%s", in + 1);
	n = strlen(in + 1);
	
	for(int i = 1; i <= n; ++i)
		used[i] = false;
	
	int ans = 0;
	for(int i = 2; i <= n; ++i){
		bool use_need = false;
		if(in[i] == in[i - 1] && !used[i - 1])
			use_need = true;

		if(i > 2 && in[i] == in[i - 2] && !used[i - 2])
			use_need = true;

		used[i] = use_need;
		ans += used[i];
	}
	
	printf("%d\n", ans);
}

int main(){
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;

int n;
char in[N];
int dp[N][2][2];

void solve(){
	scanf("%s", in + 1);
	n = strlen(in + 1);

	for(int ta = 0; ta < 2; ++ta)
		for(int tb = 0; tb < 2; ++tb)
			dp[0][ta][tb] = 0;

	for(int i = 1; i <= n; ++i)
		for(int ta = 0; ta < 2; ++ta)
			for(int tb = 0; tb < 2; ++tb)
				dp[i][ta][tb] = N;
	
	for(int i = 1; i <= n; ++i){
		if(in[i] != in[i - 1]){
			if(in[i] != in[i - 2])
				dp[i][0][0] = min(dp[i][0][0], dp[i - 1][0][0]);
			dp[i][0][0] = min(dp[i][0][0], dp[i - 1][0][1]);
		}
		
		if(in[i] != in[i - 2])
			dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][0]);
		dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][1]);
		
		dp[i][1][0] = min(dp[i][1][0], min(dp[i - 1][0][0], dp[i - 1][0][1]) + 1);
		dp[i][1][1] = min(dp[i][1][1], min(dp[i - 1][1][0], dp[i - 1][1][1]) + 1);
	}
	
	int ans = N;
	for(int ta = 0; ta < 2; ++ta)
		for(int tb = 0; tb < 2; ++tb)
			ans = min(ans, dp[n][ta][tb]);
	printf("%d\n", ans);
}

int main(){
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

What if letters can change, and you need the calculate the result after each change?

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int N = 100 * 1000 + 7;

int n;
int w[N];
int deg[N];

void solve() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &w[i]);
		deg[i] = 0;
	}
	
	for(int i = 1; i < n; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);
		deg[u]++; deg[v]++;
	}
	
	LL ans = 0;
	vector <int> to_sort;

	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j < deg[i]; ++j)
			to_sort.push_back(w[i]);
		ans += w[i];
	}
	
	sort(to_sort.begin(), to_sort.end());
	reverse(to_sort.begin(), to_sort.end());
	
	for(auto &v: to_sort) {
		printf("%lld ", ans);
		ans += v;
	}
	
	printf("%lld\n", ans);
}

int main() {
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int N = 500 * 1000 + 7;
const int P = 60;
const int MX = 1e9 + 7;

int n;
LL in[N];
int cnt[P];

void solve(){
	scanf("%d", &n);
	for(int i = 0; i < P; ++i)
		cnt[i] = 0;
	
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &in[i]);
		for(int j = 0; j < P; ++j)
			cnt[j] += in[i] >> j & 1;
	}
	
	int ans = 0;
	for(int i = 1; i <= n; ++i){
		LL exp_or = 0, exp_and = 0;
		for(int j = 0; j < P; ++j){
			if(in[i] >> j & 1){
				exp_or += (1LL << j) % MX * n;
				exp_and += (1LL << j) % MX * cnt[j];
			}
			else
				exp_or += (1LL << j) % MX * cnt[j];
		}
		
		exp_and %= MX, exp_or %= MX;
		ans = (ans + 1LL * exp_or * exp_and) % MX;
	}
	
	printf("%d\n", ans);
}

int main(){
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int N = 5e5 + 7;
const int MX = 1e9 + 7;

int n, m;
int rep[N];

int Find(int a) {
	if(rep[a] == a)
		return a;
	return rep[a] = Find(rep[a]);
}

bool Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	
	rep[a] = b;
	return a != b;
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m + 1; ++i)
		rep[i] = i;
	
	vector <int> ans;
	for(int i = 1; i <= n; ++i) {
		int k;
		scanf("%d", &k);
		
		int fa, fb = m + 1;
		scanf("%d", &fa);
		
		if(k > 1)
			scanf("%d", &fb);
		
		if(Union(fa, fb))
			ans.push_back(i);
	}
	
	int res = 1;
	for(int i = 0; i < (int)ans.size(); ++i)
		res = (res + res) % MX;

	printf("%d %d\n", res, (int)ans.size());
	for(auto v: ans)
		printf("%d ", v);
	puts("");
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MAXLEN = 1e6 + 7;
const int MOD = 1e9 + 7;

int n, q;
string s, t;
vector <string> songs;

vector <int> pw;
vector <int> sum[26];

void read(string &p) {
	static char input[MAXLEN];
	scanf("%s", input);
	p = input;
}

void prepare_songs() {
	songs = {s};
	for(auto c: t) {
		if(songs.back().size() >= MAXLEN)
			break;
		
		auto p = songs.back();
		auto nxt = p + string(1, c) + p;
		songs.push_back(nxt);
	}
}

void prepare_sum() {
	for(int i = 0; i < 26; ++i) {
		char c = 'a' + i;
		sum[i].resize(n + 1, 0);
		
		for(int j = 0; j < n; ++j)
			sum[i][j + 1] = (sum[i][j] * 2 + (t[j] == c)) % MOD;
	}
	
	pw.resize(n + 1, 0);
	pw[0] = 1;
	
	for(int i = 1; i <= n; ++i)
		pw[i] = 2LL * pw[i - 1] % MOD;
}

void init() {
	scanf("%d %d", &n, &q);
	read(s), read(t);

	prepare_songs();
	prepare_sum();
}

vector <int> kmp(string &in) {
	int m = in.size(), cpref = 0;
	vector <int> dp(m, 0);
	
	for(int i = 1; i < (int)in.size(); ++i) {
		while(cpref > 0 && in[cpref] != in[i])
			cpref = dp[cpref - 1];
		
		if(in[cpref] == in[i])
			++cpref;
		dp[i] = cpref;
	}
	
	return dp;
}

/* Get all borders based on dp from kmp */
vector <bool> get(vector <int> &dp, int m) {
	vector <bool> ret(m + 1, false);
	int cur = dp.back();
	
	while(cur) {
		ret[cur] = true;
		cur = dp[cur - 1];
	}
	
	ret[cur] = true;
	return ret;
}

int answer(int k, string &w) {
	int id = 0;
	while(songs[id].size() < w.size())
		++id;
	
	if(id > k)
		return 0;
	
	int m = w.size();
	string s_pref = w + '#' + songs[id];
	string s_suf = songs[id] + '#' + w;
	
	auto dp_pref = kmp(s_pref);
	auto dp_suf = kmp(s_suf);
	
	auto pref = get(dp_pref, m);
	auto suf = get(dp_suf, m);
	
	/* Compute all internal occurences */
	int ret = 0;
	for(auto &v: dp_pref)
		ret += (v == m);
	ret = 1LL * ret * pw[k - id] % MOD;
	
	/* Compute the remaining occurences */
	for(int i = 0; i < m; ++i) {
		if(!pref[i] || !suf[m - i - 1])
			continue;
		
		int c = w[i] - 'a';
		ret = (ret + sum[c][k] - 1LL * sum[c][id] * pw[k - id]) % MOD;
	}
	
	ret = (ret + MOD) % MOD;
	return ret;
}

void solve() {
	while(q--) {
		int k;
		string w;
		
		scanf("%d", &k);
		read(w);
		printf("%d\n", answer(k, w));
	}
}

int main() {
	init();
	solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

#define st first
#define nd second
#define PII pair <int, int>

const int N = 60;
const int MX = 1e9 + 7;

struct state {
	int sum_picked = 0;
	int last_picked = 0, cur_picked = 0;
	int iterator = 0;
	vector <PII> lengths;
	
	state(vector <PII> _lengths) {
		lengths = _lengths;
	}
	
	/* operators for map comparisons */
	bool operator<(const state &s) const {
		if(lengths != s.lengths)			return lengths < s.lengths;
		if(last_picked != s.last_picked)	return last_picked < s.last_picked;
		if(cur_picked != s.cur_picked)		return cur_picked < s.cur_picked;
		return iterator < s.iterator;
	}
	
	bool operator==(const state &s) const {
		if(last_picked != s.last_picked)	return false;
		if(cur_picked != s.cur_picked)		return false;
		if(iterator != s.iterator)			return false;
		if(lengths != s.lengths)			return false;
		return true;
	}
};

int n;
vector <PII> cycles;
map <state, int> dp;

int sil[N], rv[N];
int pre[N][N][N];

int fast(int a, int b) {
	int ret = 1;
	while(b) {
		if(b & 1)
			ret = 1LL * ret * a % MX;
		
		b >>= 1;
		a = 1LL * a * a % MX;
	}
	
	return ret;
}

int newt(int a, int b) {
	if(b < 0 || a < b)
		return 0;
	return 1LL * sil[a] * rv[b] % MX * rv[a - b] % MX;
}

PII get_ways(int a, int b) {
	if(a == 0 && b == 0)
		return {sil[n - 1], 0};

	int ret = 0, ret2 = 0;
	int c = n - a - 1;
	
	for(int t = 1; t + c <= n; ++t) {
		ret = (ret + 1LL * newt(n - t, c) * sil[c] % MX * newt(n - c - 1, b) % MX * sil[b] % MX * sil[a - b]) % MX;
		ret2 = (ret2 + 1LL * newt(n - t, c) * sil[c] % MX * newt(n - t - c, b) % MX * sil[b] % MX * sil[a - b]) % MX;
	}

	return {ret, ret2};
}

void precalc() {
	sil[0] = 1;
	for(int i = 1; i <= n; ++i)
		sil[i] = 1LL * sil[i - 1] * i % MX;
	
	rv[n] = fast(sil[n], MX - 2);
	for(int i = n; i >= 1; --i)
		rv[i - 1] = 1LL * rv[i] * i % MX;
	
	for(int i = 0; i < n; ++i)
		for(int j = 0; j <= i; ++j) {
			if(i && j == 0)
				continue;
			
			auto [val, val2] = get_ways(i, j);
			pre[i][j][0] = 1;

			int res = 1, res2 = 1;
			for(int k = 1; k <= n; ++k) {
				res = 1LL * res * val % MX;
				res2 = 1LL * res2 * val2 % MX;
				pre[i][j][k] = (res + MX - res2) % MX;
			}
		}
}

void read() {
	scanf("%d", &n);
	precalc();

	vector <int> input(n);
	for(auto &v: input) {
		scanf("%d", &v);
		v--;
	}
	
	vector <bool> vis(n);
	vector <int> cycle_lengths;

	for(int i = 0; i < n; ++i) {
		if(vis[i])
			continue;
		
		int cur = i;
		int cycle_length = 0;
		
		while(!vis[cur]) {
			++cycle_length;
			vis[cur] = true;
			cur = input[cur];
		}
		
		cycle_lengths.push_back(cycle_length);
	}
	
	sort(cycle_lengths.begin(), cycle_lengths.end());
	for(auto v: cycle_lengths) {
		if(cycles.size() && cycles.back().st == v)
			cycles.back().nd++;
		else
			cycles.push_back({v, 1});
	}
}

int solve(state &cur) {
	if(cur.sum_picked == n)
		return 1;
	
	if(dp.count(cur))
		return dp[cur];
	
	if(cur.iterator == (int)cur.lengths.size()) {
		if(cur.cur_picked == 0)
			return dp[cur] = 0;
		
		state nxt = cur;
		nxt.sum_picked += nxt.cur_picked;
		nxt.last_picked = nxt.cur_picked;
		nxt.cur_picked = 0;
		nxt.iterator = 0;
		return dp[cur] = solve(nxt);
	}
	
	state nxt = cur;
	nxt.iterator++;
	
	int ret = 0, tmp = 1;
	auto [length, count] = cur.lengths[cur.iterator];

	for(int i = 0; i <= count; ++i) {
		nxt.cur_picked = cur.cur_picked + i * length;
		nxt.lengths[cur.iterator].nd = count - i;
		ret = (ret + 1LL * solve(nxt) * tmp % MX * newt(count, i)) % MX;
		tmp = 1LL * tmp * pre[cur.sum_picked][cur.last_picked][length] % MX;
	}
	
	return dp[cur] = ret;
}

int main() {
	read();
	state start = state(cycles);
	int ans = solve(start);
	printf("%d\n", ans);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second

int n, b;

void write(int i, string y){
	printf("%d ", i);
	for(auto p: y)
		printf("%c", p);
	puts("");
	fflush(stdout);
}

bool ask(int i, string y){
	write(i, y);
	string ans;
	cin >> ans;
	return ans == "yes";
}

void solve(vector <int> cur, string pref){
	if(pref.size() == b){
		write(0, pref);
		return;
	}

	stack <pair <int, string> > S;
	S.push({0, pref});
	
	for(auto v: cur){
		while(S.size() > 1){
			auto prv = S.top().nd;
			while(prv.size() < b)
				prv.push_back('1');

			if(!ask(v, prv))
				break;
			S.pop();
		}
		
		if(S.top().nd.size() == b)
			continue;
		
		auto prv = S.top().nd;
		prv.push_back('0');

		while(prv.size() < b)
			prv.push_back('1');

		if(ask(v, prv)){
			prv = S.top().nd + "1";
			S.push({v, prv});
		}
		else{
			prv = S.top().nd + "0";
			S.push({v, prv});
		}
	}
	
	vector <int> nxt;
	string ans = S.top().nd;
	
	while(S.size() > 1){
		auto p = S.top();
		S.pop();
		
		string tmp = ans;
		while(tmp.size() < b)
			tmp.push_back('1');
		
		if(ask(p.st, tmp)){
			nxt.clear();
			ans = p.nd;
		}
		
		nxt.push_back(p.st);
	}
	
	solve(nxt, ans);
}

int main(){
	scanf("%d %d", &n, &b);
	vector <int> all_ids;
	for(int i = 0; i < n; ++i)
		all_ids.push_back(i + 1);
	solve(all_ids, "");
	return 0;
}