Subarray Sum Constraints

Explicación

Observemos que podemos reescribir cada restricción $x_l + x_{l+1} + \dots + x_r$ como $p_r - p_{l-1}$ , donde $p$ es el arreglo de sumas de prefijos.

Reordenar $p_r - p_{l-1} = s$ nos da $p_r = p_{l-1} + s$ y $p_{l-1} = p_r - s$ . Si cada elemento de nuestro arreglo de sumas de prefijos es un “nodo”, entonces estas restricciones se pueden representar como “aristas” dirigidas y ponderadas, donde una “arista” nos dice en cuánto un nodo vecino es mayor que el nodo actual.

Con el grafo construido, ejecutamos una DFS sobre él. Cada vez que encontramos un nodo nuevo le asignamos un valor arbitrario (usamos $0$ , pero sirve cualquier número).

Desde este nodo nuevo, recorremos todos los demás nodos alcanzables y o bien les asignamos un valor según los pesos de las aristas que hemos recorrido, o bien comprobamos si el valor ya calculado coincide con el que tenemos ahora.

Si hay una discrepancia, entonces hay una contradicción y no podemos construir el arreglo.

Implementación

Complejidad temporal: $\mathcal{O}(N + M)$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
	int n, m;
	cin >> n >> m;
 
	// .first es el otro nodo, .second es el peso
	vector<pair<int, int>> adj[n + 1];
	vector<ll> pref(n + 1);
	vector<bool> visited(n + 1);
 
	for (int i = 0; i < m; i++) {
		int l, r, s;
		cin >> l >> r >> s;
		// p[r] - p[l - 1] = s
		adj[l - 1].push_back({r, s});
		adj[r].push_back({l - 1, -s});
	}
 
	bool valid = true;
	function<void(int)> dfs = [&](int s) -> void {
		if (visited[s]) { return; }
		visited[s] = true;
 
		for (const pair<int, int> &u : adj[s]) {
			int v = u.first;
			ll val = pref[s] + u.second;
 
			if (!visited[v]) {
				pref[v] = val;
				dfs(v);
				if (!valid) { return; }
			} else if (pref[v] != val) {
				valid = false;
				return;
			}
		}
	};
 
	for (int i = 0; i <= n; i++) {
		if (visited[i]) { continue; }
		pref[i] = 0;
		dfs(i);
		if (!valid) {
			cout << "NO" << '\n';
			return 0;
		}
	}
 
	cout << "YES" << '\n';
	for (int i = 1; i <= n; i++) { cout << pref[i] - pref[i - 1] << ' '; }
}


import java.io.*;
import java.util.*;
 
public class SubSumConstraints {
	private static List<int[]>[] adj;
	private static long[] pref;
	private static boolean[] visited;
	private static boolean valid;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		visited = new boolean[n + 1];
		pref = new long[n + 1];
		adj = new ArrayList[n + 1];
		valid = true;
 
		for (int i = 0; i <= n; i++) { adj[i] = new ArrayList<>(); }
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			adj[l - 1].add(new int[] {r, s});
			adj[r].add(new int[] {l - 1, -s});
		}
 
		for (int i = 0; i <= n; i++) {
			if (visited[i]) { continue; }
			pref[i] = 0;
			dfs(i);
			if (!valid) {
				System.out.println("NO");
				return;
			}
		}
 
		StringBuilder sb = new StringBuilder();
		sb.append("YES\n");
		for (int i = 1; i <= n; i++) { sb.append(pref[i] - pref[i - 1] + " "); }
		System.out.println(sb);
	}
 
	private static void dfs(int s) {
		if (visited[s]) { return; }
		visited[s] = true;
 
		for (int[] u : adj[s]) {
			int v = u[0];
			long val = pref[s] + u[1];
 
			if (!visited[v]) {
				pref[v] = val;
				dfs(v);
				if (!valid) { return; }
			} else if (pref[v] != val) {
				valid = false;
				return;
			}
		}
	}
}


import sys
 
sys.setrecursionlimit(10**5)
 
n, m = map(int, input().split())
 
adj = [[] for _ in range(n + 1)]
pref = [0] * (n + 1)
visited = [False] * (n + 1)
 
 
def dfs(s: int):
	if visited[s]:
		return
	visited[s] = True
 
	for v, w in adj[s]:
		val = pref[s] + w
 
		if not visited[v]:
			pref[v] = val
			dfs(v)
		elif pref[v] != val:
			print("NO")
			exit()
 
 
for _ in range(m):
	l, r, s = map(int, input().split())
	adj[l - 1].append((r, s))
	adj[r].append((l - 1, -s))
 
for i in range(n + 1):
	if not visited[i]:
		pref[i] = 0
		dfs(i)
 
print("YES")
print(" ".join(str(pref[i] - pref[i - 1]) for i in range(1, n + 1)))