404 Not Found

#include <iostream>
#include <map>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	map<string, int> vals;
	vals["Tetrahedron"]  = 4;
	vals["Cube"]         = 6;
	vals["Octahedron"]   = 8;
	vals["Dodecahedron"] = 12;
	vals["Icosahedron"]  = 20;
	int n; cin >> n;
	int res = 0;
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		res += vals[s];
	}
	cout << res << endl;
	return 0;
}

import java.io.*;
import java.util.*;

public class PolyhedronSums {
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		HashMap<String, Integer> vals = new HashMap<String, Integer>();
		vals.put("Tetrahedron", 4);
		vals.put("Cube", 6);
		vals.put("Octahedron", 8);
		vals.put("Dodecahedron", 12);
		vals.put("Icosahedron", 20);
		int n = Integer.parseInt(reader.readLine());
		int res = 0;
		for (int i = 0; i < n; i++) {
			res += vals.get(reader.readLine());
		}	
		writer.write(Integer.toString(res));
		reader.close();
		writer.close();
	}
}

vals = {
	'Tetrahedron': 4,
	'Cube': 6,
	'Octahedron': 8,
	'Dodecahedron': 12,
	'Icosahedron': 20
}

n = int(input())
ans = 0
for i in range(0, n):
	ans += vals[input()]
print(ans)

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

#include <iostream>
#include <algorithm>

const int infinity = 1234567890;

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	int n; cin >> n;
	vector<pair<int, int> > a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	int m; cin >> m;
	vector<pair<int, int> > b(m);
	for (int i = 0; i < m; i++) {
		cin >> b[i].first >> b[i].second;
	}
	int minR1 = infinity, maxL1 = -infinity;
	int minR2 = infinity, maxL2 = -infinity;
	for (int i = 0; i < n; i++) {
		maxL1 = max(maxL1, a[i].first);
		minR1 = min(minR1, a[i].second);	
	}
	for (int i = 0; i < m; i++) {
		maxL2 = max(maxL2, b[i].first);
		minR2 = min(minR2, b[i].second);	
	}
	int res = max(maxL2 - minR1, maxL1 - minR2);
	cout << max(res, 0) << endl;
	return 0;
}

import java.io.*;
import java.util.*;

public class TwoSegments {
	public static final int infinity = 1234567890;
	
	public static class Segment {
		public int l;
		public int r;

		public Segment(int aL, int aR) {
			l = aL;
			r = aR;
		} 
	}
	
	private static Segment[] readList(BufferedReader reader) throws Exception {
		int n = Integer.parseInt(reader.readLine());
		Segment[] res = new Segment[n];
		for (int i = 0; i < n; i++) {
			StringTokenizer tokenizer = new StringTokenizer(reader.readLine());		
			int l = Integer.parseInt(tokenizer.nextToken());
			int r = Integer.parseInt(tokenizer.nextToken());
			res[i] = new Segment(l, r);
		}
		return res;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		Segment[] a = readList(reader);
		Segment[] b = readList(reader);
		int minR1 = infinity, maxL1 = -infinity;
		int minR2 = infinity, maxL2 = -infinity;
		for (int i = 0; i < a.length; i++) {
			maxL1 = Math.max(maxL1, a[i].l);
			minR1 = Math.min(minR1, a[i].r);	
		}
		for (int i = 0; i < b.length; i++) {
			maxL2 = Math.max(maxL2, b[i].l);
			minR2 = Math.min(minR2, b[i].r);	
		}
		int res = Math.max(maxL2 - minR1, maxL1 - minR2);
		writer.write(Integer.toString(Math.max(res, 0)));
		reader.close();
		writer.close();
	}
}

infinity = 1234567890
minR1 = minR2 = infinity
maxL1 = maxL2 = -infinity
n = int(input())
for i in range(0, n):
	(l, r) = map(int, input().split())
	maxL1 = max(maxL1, l)
	minR1 = min(minR1, r)
m = int(input())
for i in range(0, m):
	(l, r) = map(int, input().split())
	maxL2 = max(maxL2, l)
	minR2 = min(minR2, r)
res = max(maxL2 - minR1, maxL1 - minR2);
print(max(res, 0))

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

#include <iostream>
#include <cstdint>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	int64_t n, m;
	cin >> n >> m;
	if (n <= m) {
		cout << n << endl;
	} else {
		n -= m;
		int64_t l = 0, r = 2e9;
		while (l < r) {
			int64_t m = (l + r) / 2;
			int64_t val = m * (m+1) / 2;
			if (val >= n) {
				r = m;
			} else {
				l = m+1;
			}
		}
		cout << l + m << endl;
	}
	return 0;
}

import java.io.*;
import java.util.*;

public class SparrowsJava {
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		long n = Long.parseLong(tokenizer.nextToken());
		long m = Long.parseLong(tokenizer.nextToken());	
		if (n <= m) {
			writer.write(Long.toString(n));
		} else {
			n -= m;
			long l = 0, r = (long)2e9;
			while (l < r) {
				long med = (l + r) / 2;
				long val = med * (med+1) / 2;
				if (val >= n) {
					r = med;
				} else {
					l = med+1;
				}
			}
			writer.write(Long.toString(l + m));
		}
		reader.close();
		writer.close();
	}
}

(n, m) = map(int, input().split())
if n <= m:
	print(n)
else:
	aM = m
	n -= m
	(l, r) = (0, int(2e9))
	while l < r:
		m = (l + r) // 2;
		val = m * (m+1) // 2;
		if val >= n:
			r = m
		else:
			l = m+1
	print(l + aM)

Решите упрощенную версию задачи. Пусть в нашей последлвательности сначала идет x открывающих скобок, потом y закрывающих скобок, притом последнюю открывающую скобку обязательно включать в ППСП. Используйте наивное решение, чтобы посмотреть, как будет выглядеть ответ. Подумайте, как действовать дальше.

#include <iostream>
#include <vector>
#include <cstdint>

using namespace std;

int mod = (int)1e9 + 7;

int64_t extGcd(int64_t a, int64_t b, int64_t& x, int64_t& y) { 
	if (!a) {
		x = 0;
		y = 1;
		return b;
	}
	int64_t x1, y1;
	int64_t d = extGcd(b % a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
}

inline int addMod(int a, int b, int m = mod) {
	return ((int64_t)a + b) % m;
}

inline int mulMod(int a, int b, int m = mod) {
	return ((int64_t)a * b) % m;
}

inline int divMod(int a, int b, int m = mod) {
	int64_t x, y;
	int64_t g = extGcd(b, m, x, y);
	if (g != 1) {
		cerr << "Bad gcd!" << endl;
		for (;;);
	}
	x = (x % m + m) % m;
	return mulMod(a, x, m);
}

const int factRange = 1000000;
int fact[factRange];

inline void precalcFactorials() {
	fact[0] = 1;
	for (int i = 1; i < factRange; i++) {
		fact[i] = mulMod(fact[i-1], i);
	}
}

inline int F(int n) {
	return (n < 0) ? 0 : fact[n];
}

inline int C(int k, int n) {
	return divMod(F(n), mulMod(F(n-k), F(k)));
}

int main() {
	ios_base::sync_with_stdio(false);
	string s; 
	cin >> s;
	int len = s.size();
	precalcFactorials();
	vector<int> opnLeft(len), clsRight(len);
	opnLeft[0] = (s[0] == '(') ? 1 : 0;
	for (int i = 1; i < len; i++) {
		opnLeft[i] = opnLeft[i-1] + ((s[i] == '(') ? 1 : 0);
	}
	clsRight[len-1] = (s[len-1] == ')') ? 1 : 0;
	for (int i = len-2; i >= 0; i--) {
		clsRight[i] = clsRight[i+1] + ((s[i] == ')') ? 1 : 0);
	}
	int res = 0;
	for (int i = 0; i < len; i++) {
		if (s[i] != '(' || clsRight[i] == 0) {
			continue;
		}
		int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1);
		res = addMod(res, add);
	}
	cout << res << endl;
	return 0;
}

import java.io.*;
import java.util.*;

public class BracketsJava {
	public static int mod = (int)1e9 + 7;
	
	public static class ExtGcdResult {
		long x;
		long y;
	}
	
	public static long extGcd(long a, long b, ExtGcdResult res) { 
		if (a == 0) {
			res.x = 0L;
			res.y = 1L;
			return b;
		}
		ExtGcdResult newRes = new ExtGcdResult();
		long d = extGcd(b % a, a, newRes); 
		res.x = newRes.y - (b / a) * newRes.x;
		res.y = newRes.x;
		return d; 
	}
	
	public static final int addMod(int a, int b) { 
		return (int)(((long)a + b) % mod); 
	}

	public static final int mulMod(int a, int b) { 
		return (int)(((long)a * b) % mod); 
	}
	
	public static final int divMod(int a, int b) { 
		ExtGcdResult res = new ExtGcdResult();
		long g = extGcd(b, mod, res); 
		if (g != 1) {
			System.out.println("Bad gcd!");
			for (;;);
		}
		int q = (int)((res.x % mod + mod) % mod); 
		return mulMod(a, q); 
	}
	
	public static final int[] precalcFactorials() {
		int[] fact = new int[factRange];
		fact[0] = 1;
		for (int i = 1; i < factRange; i++) {
			fact[i] = mulMod(fact[i-1], i);
		}
		return fact;
	}

	public static final int factRange = 1000000;
	public static final int[] fact = precalcFactorials();
	
	public static final int F(int n) {
		return (n < 0) ? 0 : fact[n];
	}
	
	public static final int C(int k, int n) {
		int res = divMod(F(n), mulMod(F(n-k), F(k)));
		return divMod(F(n), mulMod(F(n-k), F(k)));
	} 
	
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		String s = reader.readLine();
		int len = s.length();
		int[] opnLeft = new int[len], clsRight = new int[len];
		opnLeft[0] = (s.charAt(0) == '(') ? 1 : 0;
		for (int i = 1; i < len; i++) {
			opnLeft[i] = opnLeft[i-1] + ((s.charAt(i) == '(') ? 1 : 0);
		}
		clsRight[len-1] = (s.charAt(len-1) == ')') ? 1 : 0;
		for (int i = len-2; i >= 0; i--) {
			clsRight[i] = clsRight[i+1] + ((s.charAt(i) == ')') ? 1 : 0);
		}
		int res = 0;
		for (int i = 0; i < len; i++) {
			if (s.charAt(i) != '(' || clsRight[i] == 0) {
				continue;
			}
			int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1);
			res = addMod(res, add);
		}		
		writer.write(Integer.toString(res));
		reader.close();
		writer.close();		
	}
}

Разделите все запросы на блоков. Затем разделите элементы на подвижные (те, которые будут изменяться в данном блоке) и неподвижные. Подумайте, как действовать дальше.

// Thanks to netman for the idea for this wonderful solution :)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdint>
#include <algorithm>

using namespace std;

class SQRTDecomposition {
	private:
		int n, sz;
		vector<int> val;
		vector<int> blocks;
	public:
		inline void add(int v, int delta) {
			val[v] += delta;
			blocks[v / sz] += delta;
		}
		
		inline int sum(int l, int r) {	
			if (l < 0) {
				l = 0;
			}
			if (r >= n) {
				r = n;
			}
			r++;
			int res = 0;
			int lBlock = (l + sz - 1) / sz, rBlock = r / sz;
			for (int i = lBlock; i < rBlock; i++) {
				res += blocks[i];
			}
			int lBlockR = lBlock * sz, rBlockR = rBlock * sz;
			if (lBlockR >= rBlockR) {
				for (int i = l; i < r; i++) {
					res += val[i];
				}
			} else {
				for (int i = l; i < lBlockR; i++) {
					res += val[i];
				}
				for (int i = rBlockR; i < r; i++) {
					res += val[i];
				}
			}
			return res;
		}
		
		inline void clear() {
			val.assign(val.size(), 0);
			blocks.assign(blocks.size(), 0);
		}
		
		SQRTDecomposition(int n, int sz)
			: n(n), sz(sz), val(n, 0), blocks((n + sz - 1) / sz, 0) {
		}
};

struct ToProcess {
	int x, y1, y2, sgn, id;
};

const int BLOCK_SZ_Q = 256;
const int BLOCK_SZ_N = 512;
const int MAX_N = 200000;

int n, q;
vector<ToProcess> sortedL[MAX_N], sortedR[MAX_N];
SQRTDecomposition sum(MAX_N, BLOCK_SZ_N);
int64_t ans[MAX_N], preAns[MAX_N];
pair<int, int> queries[MAX_N];
vector<int> goods;
int p[MAX_N];
bool good[MAX_N];

inline void add(int q, int sgn, int id) {
	if (q-1 >= 0) {
		sortedL[q-1].push_back({q-1, p[q]+1, n-1, sgn, id});
	}
	if (q+1 < n) {
		sortedR[q+1].push_back({q+1, 0, p[q]-1, sgn, id});
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		p[i] = i;
	}
	for (int i = 0; i < q; i++) {
		cin >> queries[i].first >> queries[i].second;
		queries[i].first--; queries[i].second--;
	}
	int64_t cnt = 0;
	for (int i = 0; i < q; i += BLOCK_SZ_Q) {
		int iEnd = min(q, i + BLOCK_SZ_Q);
		for (int j = 0; j < n; j++) {
			good[j] = false;
		}
		for (int j = i; j < iEnd; j++) {
			good[queries[j].first] = true;
			good[queries[j].second] = true;
		}
		goods.clear();
		for (int j = 0; j < n; j++) {
			if (good[j]) {
				goods.push_back(j);
			}
		}
		int64_t goodCnt = 0;
		for (int j = 0; j < n; j++) {
			sortedL[j].clear();
			sortedR[j].clear();
		}
		for (int j = i; j < iEnd; j++) {
			int a = queries[j].first, b = queries[j].second;
			if (a == b) {
				ans[j] += goodCnt;
				continue;
			}
			for (int k = 0; k < (int)goods.size(); k++) {
				int q = goods[k];
				if (q == a || q == b) {
					continue;
				}
				if ((p[q] < p[a] && q > a) ||
				    (p[q] > p[a] && q < a)) {
					goodCnt--;
				}
				if ((p[q] < p[b] && q > b) ||
				    (p[q] > p[b] && q < b)) {
					goodCnt--;
				}
				if ((p[q] < p[b] && q > a) ||
				    (p[q] > p[b] && q < a)) {
					goodCnt++;
				}
				if ((p[q] < p[a] && q > b) ||
				    (p[q] > p[a] && q < b)) {
					goodCnt++;
				}
			}
			if ((a < b && p[a] > p[b]) ||
				(a > b && p[a] < p[b])) {
				goodCnt--;
			} else {
				goodCnt++;
			}
			ans[j] += goodCnt;
			add(a, -1, j);
			add(b, -1, j);
			swap(p[a], p[b]);
			add(a, +1, j);
			add(b, +1, j);
		}
		sum.clear();
		for (int j = 0; j < n; j++) {
			if (!good[j]) {
				sum.add(p[j], 1);
			}
			for (int k = 0; k < (int)sortedL[j].size(); k++) {
				ToProcess &cur = sortedL[j][k];
				int64_t res = sum.sum(cur.y1, cur.y2);
				res *= cur.sgn;
				preAns[cur.id] += res;
			}
		}
		sum.clear();
		for (int j = n-1; j >= 0; j--) {
			if (!good[j]) {
				sum.add(p[j], 1);
			}
			for (int k = 0; k < (int)sortedR[j].size(); k++) {
				ToProcess &cur = sortedR[j][k];
				int64_t res = sum.sum(cur.y1, cur.y2);
				res *= cur.sgn;
				preAns[cur.id] += res;
			}
		}
		for (int j = i; j < iEnd; j++) {
			if (j != i) {
				preAns[j] += preAns[j-1];	
			}
			ans[j] += cnt + preAns[j];
		}
		cnt = ans[iEnd - 1];
	}
	for (int i = 0; i < q; i++) {
		cout << ans[i] << "\n";
	}
	return 0;
}

import java.io.*;
import java.util.*;

public class InversionNSqrtNNoVectors {
	private static final int BLOCK_SZ_Q = 256;
	private static final int BLOCK_SZ_N = 512;
	
	public static class ToProcess {
		public int x, y1, y2, sgn, id;
		
		public void set(int pX, int pY1, int pY2, int pSgn, int pId) {
			x = pX;
			y1 = pY1;
			y2 = pY2;
			sgn = pSgn;
			id = pId;
		}
		
		public ToProcess() {
		}
	}
	
	public static class ToProcessCompareAsc implements Comparator<ToProcess> {
		@Override
		public int compare(ToProcess o1, ToProcess o2) {
			return o1.x - o2.x;
		}
	}
	
	public static class ToProcessCompareDesc implements Comparator<ToProcess> {
		@Override
		public int compare(ToProcess o1, ToProcess o2) {
			return o2.x - o1.x;
		}
	}
	
	static int n, q;
	static int[] p;
	static ToProcess[] queryL, queryR;
	static int queryLCnt, queryRCnt;
	static SQRTDecomposition sum;
	static ToProcessCompareAsc ascCmp = new ToProcessCompareAsc();
	static ToProcessCompareDesc descCmp = new ToProcessCompareDesc();
	
	public static final void add(int q, int sgn, int id) {
		if (q-1 >= 0) {
			queryL[queryLCnt++].set(q-1, p[q]+1, n-1, sgn, id);
		}
		if (q+1 < n) {
			queryR[queryRCnt++].set(q+1, 0, p[q]-1, sgn, id);
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		n = Integer.parseInt(tokenizer.nextToken());
		q = Integer.parseInt(tokenizer.nextToken());
		int[] qL = new int[q], qR = new int[q];
		long[] ans = new long[q], preAns = new long[q];
		p = new int[n];
		for (int i = 0; i < n; i++) {
			p[i] = i;
		}
		for (int i = 0; i < q; i++) {
			tokenizer = new StringTokenizer(reader.readLine());
			qL[i] = Integer.parseInt(tokenizer.nextToken()) - 1;
			qR[i] = Integer.parseInt(tokenizer.nextToken()) - 1;
		}
		long cnt = 0;
		boolean[] good = new boolean[n];
		int[] goods = new int[n];
		int goodsSize = 0;
		queryL = new ToProcess[4 * BLOCK_SZ_Q]; queryR = new ToProcess[4 * BLOCK_SZ_Q];
		for (int j = 0; j < 4 * BLOCK_SZ_Q; j++) {
			queryL[j] = new ToProcess();
			queryR[j] = new ToProcess();
		}
		SQRTDecomposition sum = new SQRTDecomposition(n, BLOCK_SZ_N);
		for (int i = 0; i < q; i += BLOCK_SZ_Q) {
			int iEnd = Math.min(q, i + BLOCK_SZ_Q);
			Arrays.fill(good, false);
			for (int j = i; j < iEnd; j++) {
				good[qL[j]] = true;
				good[qR[j]] = true;
			}
			goodsSize = 0;
			for (int j = 0; j < n; j++) {
				if (good[j]) {
					goods[goodsSize++] = j;
				}
			}
			long goodCnt = 0;
			queryLCnt = 0;
			queryRCnt = 0;
			for (int j = i; j < iEnd; j++) {
				int a = qL[j], b = qR[j];
				if (a == b) {
					ans[j] += goodCnt;
					continue;
				}
				for (int k = 0; k < goodsSize; k++) {
					int q = goods[k];
					if (q == a || q == b) {
						continue;
					}
					if ((p[q] < p[a] && q > a) ||
						(p[q] > p[a] && q < a)) {
						goodCnt--;
					}
					if ((p[q] < p[b] && q > b) ||
						(p[q] > p[b] && q < b)) {
						goodCnt--;
					}
					if ((p[q] < p[b] && q > a) ||
						(p[q] > p[b] && q < a)) {
						goodCnt++;
					}
					if ((p[q] < p[a] && q > b) ||
						(p[q] > p[a] && q < b)) {
						goodCnt++;
					}
				}
				if ((a < b && p[a] > p[b]) ||
					(a > b && p[a] < p[b])) {
					goodCnt--;
				} else {
					goodCnt++;
				}
				ans[j] += goodCnt;
				add(a, -1, j);
				add(b, -1, j);
				int tmp = p[a];
				p[a] = p[b];
				p[b] = tmp;
				add(a, +1, j);
				add(b, +1, j);
			}
			sum.clear();
			Arrays.sort(queryL, 0, queryLCnt, ascCmp);
			int curL = 0;
			for (int j = 0; j < n; j++) {
				if (!good[j]) {
					sum.add(p[j], 1);
				}
				for (; curL < queryLCnt; curL++) {
					ToProcess cur = queryL[curL];
					if (cur.x != j) {
						break;
					}
					int res = sum.sum(cur.y1, cur.y2);
					res *= cur.sgn;
					preAns[cur.id] += res;
				}
			}
			sum.clear();
			Arrays.sort(queryR, 0, queryRCnt, descCmp);
			int curR = 0;
			for (int j = n-1; j >= 0; j--) {
				if (!good[j]) {
					sum.add(p[j], 1);
				}
				for (; curR < queryRCnt; curR++) {
					ToProcess cur = queryR[curR];
					if (cur.x != j) {
						break;
					}
					int res = sum.sum(cur.y1, cur.y2);
					res *= cur.sgn;
					preAns[cur.id] += res;
				}
			}
			for (int j = i; j < iEnd; j++) {
				if (j != i) {
					preAns[j] += preAns[j-1];	
				}
				ans[j] += cnt + preAns[j];
			}
			cnt = ans[iEnd - 1];
		}
		for (int i = 0; i < q; i++) {
			writer.write(Long.toString(ans[i]));
			writer.newLine();
		}
		reader.close();
		writer.close();
	}
}

class SQRTDecomposition {
	private int n;
	private int sz;
	private int[] val;
	private int[] blocks;
	
	public final void add(int v, int delta) {
		val[v] += delta;
		blocks[v / sz] += delta;
	}
		
	public final int sum(int l, int r) {	
		if (l < 0) {
			l = 0;
		}
		if (r >= n) {
			r = n;
		}
		r++;
		int res = 0;
		int lBlock = (l + sz - 1) / sz, rBlock = r / sz;
		for (int i = lBlock; i < rBlock; i++) {
			res += blocks[i];
		}
		int lBlockR = lBlock * sz, rBlockR = rBlock * sz;
		if (lBlockR >= rBlockR) {
			for (int i = l; i < r; i++) {
				res += val[i];
			}
		} else {
			for (int i = l; i < lBlockR; i++) {
				res += val[i];
			}
			for (int i = rBlockR; i < r; i++) {
				res += val[i];
			}
		}
		return res;
	}
	
	public void clear() {
		Arrays.fill(val, 0);
		Arrays.fill(blocks, 0);
	}
		
	SQRTDecomposition(int pN, int pSz) {
		n = pN;
		sz = pSz;
		val = new int[n];
		blocks = new int[(n + sz - 1) / sz];
	}
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <iomanip>

#define sqr(a) (a)*(a)
#define all(a) (a).begin(), (a).end()
using namespace std;

template <typename T>
T next_int() {
    T ans = 0, t = 1;
    char ch;
    do { ch = getchar(); } while(ch <= ' ') ;
    if(ch == '-') {
        t = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        ans = ans * 10 + (ch - '0');
        ch = getchar();
    }
    return ans * t;
}

string next_token() {
    char ch;
    string ans = "";
    do { ch = getchar(); } while(ch <= ' ') ;
    while(ch >= ' ') {
        ans += ch;
        ch = getchar();
    }
    return ans;
}

const long long INF = (long long)1e18 + 227 + 1;
const int INFINT = (int)1e9 + 227 + 1;
const int MAXN = (int)2e5 + 227 + 1;
const int MOD = (int)1e9 + 7;
const long double EPS = 1e-9;

long long bin_pow(long long n, long long k) {
    if(!k) return 1;
    long long ans = bin_pow(n, k / 2);
    ans = ans * ans % MOD;
    if(k % 2) ans = ans * n % MOD;
    return ans;
}

struct tree {
    int size_block;
    int len; 
 
    tree(int len) : len(len) {
        size_block = sqrt(len);
 
        kek.resize(len / size_block + 1, vector<int>(size_block, 0));
 
        pr_block.resize(len / size_block + 1, 0);
    }
 
    vector<int> pr_block;
    vector<vector<int> > kek;
 
    void inc(int pos, int num) {
        int x = pos / size_block;
 
        for(int i = pos % size_block; i < size_block; i++) {
            kek[x][i] += num;
        }
 
        for(int i = 0; i <= len / size_block; i++)
            if(i == 0) {
                pr_block[i] = kek[i][size_block - 1];
            } else {
                pr_block[i] = pr_block[i - 1] + kek[i][size_block - 1]; 
            }
    }
 
    int f(int a) {
        return a / size_block;
    }
 
    long long get(vector<int> &a, int l, int r, bool ok = 1) {
        if(ok == 1) {
            l %= size_block;
            r %= size_block;
        }
 
        return a[r] - (l ? a[l - 1] : 0);
    }
 
    int get(int l, int r) {
        if(l > r) return 0;

        r = min(r, len);
  
        if(f(l) == f(r))
            return get(kek[f(l)], l, r);
     
        int ans = 0;
 
        if(l % size_block) {
            ans += get(kek[f(l)], l, size_block - 1);
 
            l += size_block - l % size_block;
        }
 
        if(r % size_block != size_block - 1) {
            ans += get(kek[f(r)], 0, r);
 
            r -= r % size_block + 1;
        }
 
        ans += get(pr_block, f(l), f(r), 0);
 
        return ans;
    }
 
    int get_pref(int p) {
        return get(1, p - 1);
    }

    int get_suff(int p) {
        return get(p + 1, len);
    }
} ;

struct mda {
    vector<int> a;
    vector<tree> t;
    int len, sz;
    long long ans;

    mda(int len) : len(len) {
        sz = 2000;
        ans = 0;

        a.resize(len + 1);
        for(int i = 1; i <= len; i++)
            a[i] = i;

        for(int i = 1; i <= len; i += sz) {
            t.push_back(tree(len));
            for(int j = i; j < i + sz && j <= len; j++)
                add(j, j);
        }
    }

    int get_pref(int L, int R, int k) {
        int ans = 0;

        for(int l = 1; l <= R; l += sz) {
            int r = l + sz - 1;

            if(r < L || l > R) continue;

            if(L <= l && r <= R)
                ans += t[(l - 1) / sz].get_pref(k);
            else
                for(int i = max(l, L); i <= min(r, R); i++) 
                    ans += (a[i] < k);
        }

        return ans;
    }

    int get_suff(int L, int R, int k) {
        int ans = 0;

        for(int l = 1; l <= R; l += sz) {
            int r = l + sz - 1;

            if(r < L || l > R) continue;

            if(L <= l && r <= R)
                ans += t[(l - 1) / sz].get_suff(k);
            else
                for(int i = max(l, L); i <= min(r, R); i++) 
                    ans += (a[i] > k);
        }

        return ans;
    }

    void del(int p, int k) {
        p = (p - 1) / sz;
        t[p].inc(k, -1);
    }

    void add(int p, int k) {
        p = (p - 1) / sz;
        t[p].inc(k, 1);
    }

    void sw(int i, int j) {
        if(i == j) return;
        if(i > j) swap(i, j);

        ans -= get_pref(i, j, a[i]);
        ans -= get_suff(i, j, a[j]);

        if(a[i] > a[j]) ans++;

        del(i, a[i]);
        del(j, a[j]);
        swap(a[i], a[j]);
        add(i, a[i]);
        add(j, a[j]);

        ans += get_pref(i, j, a[i]);
        ans += get_suff(i, j, a[j]);

        if(a[i] > a[j]) ans--;
    }
} ;

int main() {
    // freopen(".in", "r", stdin);

    int n, m; cin >> n >> m;

    mda t(n);

    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;

        t.sw(x, y);
        
        cout << t.ans << "\n";
    }
}

import java.io.*;
import java.util.*;

public class NsqrtNlogNnetman implements Runnable {
    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;
        InputReader(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in), 32768);
            tokenizer = null;
        }
        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static class Fenwick {
        int[] ft;
        Fenwick(int n) {
            ft = new int[n];
        }
        void add(int r, int val) {
            while (r < ft.length) {
                ft[r] += val;
                r |= r + 1;
            }
        }
        int sum(int r) {
            int res = 0;
            while (r >= 0) {
                res += ft[r];
                r = (r & (r + 1)) - 1;
            }
            return res;
        }
        void clear() {
            Arrays.fill(ft, 0);
        }
    }

    static class Query {
        int x, bound, sign, id;
        Query(int x, int bound, int sign, int id) {
            this.x = x;
            this.bound = bound;
            this.sign = sign;
            this.id = id;
        }
    }

    static void getOnPrefSmaller(List<Query> qrs, int r, int y, int id, int sign) {
        qrs.add(new Query(r, y, sign, id));
    }

    static void getOnPrefBetween(List<Query> qrs, int r, int x, int y, int id, int sign) {
        getOnPrefSmaller(qrs, r, y, id, sign);
        getOnPrefSmaller(qrs, r, x, id, -sign);
    }

    static void getOnSegmentBetween(List<Query> qrs, int l, int r, int x, int y, int id, int sign) {
        if (x > y) return;
        getOnPrefBetween(qrs, r, x, y, id, sign);
        getOnPrefBetween(qrs, l, x, y, id, -sign);
    }

    @Override
    public void run() {

        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int q = in.nextInt();

        int[] l = new int[q];
        int[] r = new int[q];

        for (int i = 0; i < q; i++) {
            l[i] = in.nextInt() - 1;
            r[i] = in.nextInt() - 1;
        }

        int[] perm = new int[n];

        for (int i = 0; i < n; i++) {
            perm[i] = n - i - 1;
        }

        final int BLOCK = 300;

        long inv = 0L;

        boolean[] isInteresting = new boolean[n];

        long[] add = new long[q];

        Fenwick f = new Fenwick(n);

        for (int i = 0; i < q; i += BLOCK) {
            int from = i, to = Math.min(i + BLOCK, q) - 1;
            List<Integer> lst = new ArrayList<>();
            for (int j = from; j <= to; j++) {
                lst.add(l[j]);
                lst.add(r[j]);
            }
            lst.sort(Integer::compareTo);
            lst = new ArrayList<>(new HashSet<>(lst));
            int[] interestingPositions = lst.stream().mapToInt(x -> x).toArray();
            for (int pos : interestingPositions) {
                isInteresting[pos] = true;
            }
            List<Query> qrs = new ArrayList<>();
            for (int j = from; j <= to; j++) {
                if (l[j] == r[j]) continue;
                if (l[j] > r[j]) {
                    int tmp = l[j];
                    l[j] = r[j];
                    r[j] = tmp;
                }
                if (perm[l[j]] < perm[r[j]]) {
                    getOnSegmentBetween(qrs, l[j], r[j], perm[l[j]], perm[r[j]], j,-1);
                    int leftValue = perm[l[j]];
                    int rightValue = perm[r[j]];
                    for (int pos : interestingPositions) {
                        if (pos > l[j] && pos < r[j] && perm[pos] > leftValue && perm[pos] < rightValue) {
                            add[j] -= 2;
                        }
                    }
                    add[j]--;
                } else {
                    getOnSegmentBetween(qrs, l[j], r[j], perm[r[j]], perm[l[j]], j,1);
                    int leftValue = perm[l[j]];
                    int rightValue = perm[r[j]];
                    for (int pos : interestingPositions) {
                        if (pos > l[j] && pos < r[j] && perm[pos] > rightValue && perm[pos] < leftValue) {
                            add[j] += 2;
                        }
                    }
                    add[j]++;
                }
                int tmp = perm[l[j]];
                perm[l[j]] = perm[r[j]];
                perm[r[j]] = tmp;
            }
            qrs.sort(Comparator.comparingInt(a -> -a.x));

            f.clear();
            for (int pos = 0; pos < n; pos++) {
                if (!isInteresting[pos]) {
                    f.add(perm[pos], 1);
                }
                while (!qrs.isEmpty() && qrs.get(qrs.size() - 1).x == pos) {
                    Query t = qrs.get(qrs.size() - 1);
                    qrs.remove(qrs.size() - 1);
                    add[t.id] += 2 * t.sign * f.sum(t.bound);
                }
            }
            for (int j = from; j <= to; j++) {
                inv += add[j];
                out.println(inv);
            }
            for (int pos : interestingPositions) {
                isInteresting[pos] = false;
            }
        }



        out.close();
    }

    public static void main(String[] args) {
        new Thread(null, new NsqrtNlogNnetman(), "1", 1L << 28).run();
    }
}