Problème A : SA

Pour résoudre ce problème, nous utilisons un tableau de suffixes. Pour chaque requête, nous modifions un caractère spécifique de la chaîne T et comptons les occurrences de cette nouvelle chaîne dans S.

La fonction f(L,R,l,r,len) permet de déterminer les intrevalles de suffixes correspondant à des sous-chaînes de longueur len. En combinant les résultats des deux parties de T, nous obtenons le nombre total de sous-chaînes avec une différence d'un caractère.

Problème B : A

Ce problème nécessite un algorithme de coupe minimum pour maximiser le bénéfice. Nous transformons les gains en coûts négatifs et utliisons un réseau de flux pour modéliser les contraintes de séquence.

Chaque travail est représenté par des nœuds connectés par des arêtes pondérées. Les contraintes sont gérées via des arêtes de capacité infinie. Le résultat est obtenu en soustrayant le flux maximum du total potentiel.

Problème C : Inversion

Pour maximiser le nombre d'inversions, les valeurs manquantes doivent être remplies de manière décroissente. Un algorithme de programmation dynamique avec optimisation de pente est utilisé pour calculer les contributions optimales.

Les précalculs w[i][j] et les transitions dynamiques permettent de réduire la complexité à O(nK). L'optimisation de pente permet de gérer les relations linéaires entre les états.

/*
* @Auteur: wxyww
* @Date:   2020-06-03 08:36:02
* @Dernière modification: 2020-06-03 22:05:14
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 500010;
ll read() {
	ll x = 0,f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1; c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x * 10 + c - '0'; c = getchar();
	}
	return x * f;
}
int n,sa[N],c[N],x[N],m,rk[N],y[N];
char s[N];
void calculer_sa() {
	for(int i = 1;i <= n;++i) c[x[i] = s[i]]++;
	for(int i = 1;i <= m;++i) c[i] += c[i - 1];
	for(int i = n;i >= 1;--i) sa[c[x[i]]--] = i;

	for(int k = 1;k <= n;k <<= 1) {
		int num = 0;
		for(int i = n - k + 1;i <= n;++i) y[++num] = i;
		for(int i = 1;i <= n;++i) if(sa[i] > k) y[++num] = sa[i] - k;
		for(int i = 2;i <= m;++i) c[i] = 0;
		for(int i = 1;i <= n;++i) ++c[x[i]];
		for(int i = 1;i <= m;++i) c[i] += c[i - 1];
		for(int i = n;i >= 1;--i) sa[c[x[y[i]]]--] = y[i];

		swap(x,y);
		num = 0;
		x[sa[1]] = ++num;
		for(int i = 2;i <= n;++i) {
			if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num;
			else x[sa[i]] = ++num;
		}
		if(num == n) break;
		m = num;
	}
	for(int i = 1;i <= n;++i) rk[sa[i]] = i;
}

void recuperer(int L,int R,int LL,int RR,int &x,int &y,int len) {
	int l = L,r = R;

	x = l,y = r;
	if(L > R) return;
	x = R + 1,y = L - 1;

	while(l <= r) {
		int mid = (l + r) >> 1;
		if(rk[sa[mid] + len] >= LL) x = mid,r = mid - 1;
		else l = mid + 1;
	}
	l = L,r = R;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(rk[sa[mid] + len] <= RR) y = mid,l = mid + 1;
		else r = mid - 1;
	}
}
char t[N];
int L[N],R[N],Lc[N],Rc[N];
int main() {
	scanf("%s",s + 1);
	n = strlen(s + 1);
	m = 'z';
	calculer_sa();
	for(int i = 'a';i <= 'z';++i) Lc[i] = n,Rc[i] = 1;

	for(int i = 1;i <= n;++i) {
		Lc[s[sa[i]]] = min(Lc[s[sa[i]]],i);
		Rc[s[sa[i]]] = max(Rc[s[sa[i]]],i);
	}

	int T = read();
	while(T--) {
		scanf("%s",t + 1);
		int mm = strlen(t + 1);
		ll ans = 0;
		L[mm + 1] = 0,R[mm + 1] = n;
		for(int i = mm;i >= 1;--i)
			recuperer(Lc[t[i]],Rc[t[i]],L[i + 1],R[i + 1],L[i],R[i],1);
		int tl = 1,tr = n;
		for(int i = 1;i <= mm;++i) {
			for(int j = 'a';j <= 'z';++j) {
				if(j == t[i]) continue;
				int x,y;
				recuperer(tl,tr,Lc[j],Rc[j],x,y,i - 1);

				recuperer(x,y,L[i + 1],R[i + 1],x,y,i);

				ans += max(0,y - x + 1);
			}
			recuperer(tl,tr,Lc[t[i]],Rc[t[i]],tl,tr,i - 1);
		}
		cout<<ans return=""></ans>

/*
* @Auteur: wxyww
* @Date:   2020-06-03 09:34:34
* @Dernière modification: 2020-06-03 10:10:55
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 1000010,INF = 1e9;
ll read() {
	ll x = 0,f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1; c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x * 10 + c - '0'; c = getchar();
	}
	return x * f;
}
struct noeud {
	int v,suiv,flux;
}arête[N << 1];
int tête[N],ejs = 1;

void ajouter(int u,int v,int flux) {
	// printf("!!%d %d %d\n",u,v,flux);
	arête[++ejs].v = v;arête[ejs].suiv = tête[u];tête[u] = ejs;arête[ejs].flux = flux;
	arête[++ejs].v = u;arête[ejs].suiv = tête[v];tête[v] = ejs;arête[ejs].flux = 0;
}

int w[110][110],n,m,K,S,T;
int pos(int x,int y) {
	return (x - 1) * (m + 1) + y;
}
int profondeur[N];
queue<int>file;
int bfs() {
	memset(profondeur,0,sizeof(profondeur));
	profondeur[S] = 1;file.push(S);
	// cout<<t :="" ajouter="" ar="" cout="" cur="" dfs="" dinic="" for="" i="tête[u];i;i" if="" inf="" int="" j="1;j" k="dfs(v,min(arête[i].flux,now" m="" main="" memcpy="" n="read(),m" now="" printf="" profondeur="" puts="" read="" ret="0;" return="" s="n" t="" u="file.front();file.pop();" v="arête[i].v;" while="" x="read();"></t></int>

/*
* @Auteur: wxyww
* @Date:   2020-06-03 09:05:56
* @Dernière modification: 2020-06-03 19:24:45
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 200004;
#define int ll
ll read() {
	ll x = 0,f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1; c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x * 10 + c - '0'; c = getchar();
	}
	return x * f;
}
ll tab[N][104],dp[2][N];
int arbre_gauche[N],arbre_droit[N],n,K,b[N],a[N],m;
void mettre_a_jour(int x,int c) {
	while(x <= K) arbre_droit[x] += c,++x;
}
void mettre_a_jour_gauche(int x,int c) {
	while(x >= 1) arbre_gauche[x] += c,--x;
}
int file[2][N],tete[2],queue[2];
ll get_b(int k,int j) {
	return dp[j & 1][k] - tab[k][j - 1] - m * k;
}
ll calcul(int k,int i,int j) {
	ll b = get_b(k,j);
	return b + i * k;
}
ll verifier(int k1,int k2,int k3,int j) {
	int b1 = get_b(k1,j),b2 = get_b(k2,j),b3 = get_b(k3,j);
	return (b3 - b1) * (k1 - k2) < (b2 - b1) * (k1 - k3);
}
signed main() {
	n = read(),K = read();
	ll ans = 0,ret = 0;
	for(int i = 1;i <= n;++i) {
		a[i] = read();
		if(!a[i]) b[++m] = i;
		if(a[i]) {
			mettre_a_jour(a[i],1);
		}
	}
	int p = 1;
	for(int i = 1;i <= m;++i) {
		while(p < b[i]) {
			if(!a[p]) {++p;continue;}
			ret += arbre_gauche[a[p] + 1];
			mettre_a_jour_gauche(a[p],1);
			mettre_a_jour(a[p],-1);
			++p;
		}
		for(int j = 1;j <= K;++j) {
			tab[i][j] = tab[i - 1][j] + arbre_droit[j - 1] + arbre_gauche[j + 1];
		}
	}

	while(p <= n) {
		if(!a[p]) {++p;continue;}
		ret += arbre_gauche[a[p] + 1];
		mettre_a_jour_gauche(a[p],1);
		++p;
	}


	for(int j = K;j >= 1;--j) {
		
		int t = j & 1,t_1 = t ^ 1;
		tete[t_1] = 0;queue[t_1] = 0;
		
		for(int i = 1;i <= m;++i) {
			dp[t][i] = dp[t_1][i];
			while(tete[t_1] < queue[t_1] && calcul(file[t_1][tete[t_1]],i,j + 1) < calcul(file[t_1][tete[t_1] + 1],i,j + 1)) {
				++tete[t_1];
			}
			
			dp[t][i] = max(dp[t][i],tab[i][j] - i * i + m * i + calcul(file[t_1][tete[t_1]],i,j + 1));
		
			while(tete[t_1] < queue[t_1] && verifier(file[t_1][queue[t_1] - 1],file[t_1][queue[t_1]],i,j + 1)) --queue[t_1];
			
			file[t_1][++queue[t_1]] = i;
		}

		ans = max(ans,dp[t][m]);
	}
	cout<<ans ret="" return=""></ans>