codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

785.md (32262B)


      1 Source: https://codeforces.com/blog/entry/50996
      2 
      3 This is an editorial for the problems of the today's contest. I tried my best to describe the solutions for the problems as detailed as possible, but if something is not understandable for you, you can write in comments! :)
      4 
      5 [785A - Anton and Polyhedrons](/contest/785/problem/A "Codeforces Round 404 (Div. 2)")
      6 
      7 **Hint**
      8 
      9 404 Not Found
     10 
     11 **Tutorial**
     12 
     13 Tutorial is loading...
     14 
     15 **C++ code**
     16 
     17 ```
     18 #include <iostream>
     19 #include <map>
     20 
     21 using namespace std;
     22 
     23 int main() {
     24 	ios_base::sync_with_stdio(false);
     25 	map<string, int> vals;
     26 	vals["Tetrahedron"]  = 4;
     27 	vals["Cube"]         = 6;
     28 	vals["Octahedron"]   = 8;
     29 	vals["Dodecahedron"] = 12;
     30 	vals["Icosahedron"]  = 20;
     31 	int n; cin >> n;
     32 	int res = 0;
     33 	for (int i = 0; i < n; i++) {
     34 		string s; cin >> s;
     35 		res += vals[s];
     36 	}
     37 	cout << res << endl;
     38 	return 0;
     39 }
     40 ```
     41 
     42 **Java code**
     43 
     44 ```
     45 import java.io.*;
     46 import java.util.*;
     47 
     48 public class PolyhedronSums {
     49 	public static void main(String[] args) throws Exception {
     50 		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
     51 		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
     52 		HashMap<String, Integer> vals = new HashMap<String, Integer>();
     53 		vals.put("Tetrahedron", 4);
     54 		vals.put("Cube", 6);
     55 		vals.put("Octahedron", 8);
     56 		vals.put("Dodecahedron", 12);
     57 		vals.put("Icosahedron", 20);
     58 		int n = Integer.parseInt(reader.readLine());
     59 		int res = 0;
     60 		for (int i = 0; i < n; i++) {
     61 			res += vals.get(reader.readLine());
     62 		}	
     63 		writer.write(Integer.toString(res));
     64 		reader.close();
     65 		writer.close();
     66 	}
     67 }
     68 ```
     69 
     70 **Python code**
     71 
     72 ```
     73 vals = {
     74 	'Tetrahedron': 4,
     75 	'Cube': 6,
     76 	'Octahedron': 8,
     77 	'Dodecahedron': 12,
     78 	'Icosahedron': 20
     79 }
     80 
     81 n = int(input())
     82 ans = 0
     83 for i in range(0, n):
     84 	ans += vals[input()]
     85 print(ans)
     86 ```
     87 
     88 [785B - Anton and Classes](/contest/785/problem/B "Codeforces Round 404 (Div. 2)")
     89 
     90 **Hint**
     91 
     92 Think of what periods to take if Anton attends chess classes earlier than programming classes and vice versa.
     93 
     94 **Tutorial**
     95 
     96 Tutorial is loading...
     97 
     98 **C++ code**
     99 
    100 ```
    101 #include <iostream>
    102 #include <algorithm>
    103 
    104 const int infinity = 1234567890;
    105 
    106 using namespace std;
    107 
    108 int main() {
    109 	ios_base::sync_with_stdio(false);
    110 	int n; cin >> n;
    111 	vector<pair<int, int> > a(n);
    112 	for (int i = 0; i < n; i++) {
    113 		cin >> a[i].first >> a[i].second;
    114 	}
    115 	int m; cin >> m;
    116 	vector<pair<int, int> > b(m);
    117 	for (int i = 0; i < m; i++) {
    118 		cin >> b[i].first >> b[i].second;
    119 	}
    120 	int minR1 = infinity, maxL1 = -infinity;
    121 	int minR2 = infinity, maxL2 = -infinity;
    122 	for (int i = 0; i < n; i++) {
    123 		maxL1 = max(maxL1, a[i].first);
    124 		minR1 = min(minR1, a[i].second);	
    125 	}
    126 	for (int i = 0; i < m; i++) {
    127 		maxL2 = max(maxL2, b[i].first);
    128 		minR2 = min(minR2, b[i].second);	
    129 	}
    130 	int res = max(maxL2 - minR1, maxL1 - minR2);
    131 	cout << max(res, 0) << endl;
    132 	return 0;
    133 }
    134 ```
    135 
    136 **Java code**
    137 
    138 ```
    139 import java.io.*;
    140 import java.util.*;
    141 
    142 public class TwoSegments {
    143 	public static final int infinity = 1234567890;
    144 	
    145 	public static class Segment {
    146 		public int l;
    147 		public int r;
    148 
    149 		public Segment(int aL, int aR) {
    150 			l = aL;
    151 			r = aR;
    152 		} 
    153 	}
    154 	
    155 	private static Segment[] readList(BufferedReader reader) throws Exception {
    156 		int n = Integer.parseInt(reader.readLine());
    157 		Segment[] res = new Segment[n];
    158 		for (int i = 0; i < n; i++) {
    159 			StringTokenizer tokenizer = new StringTokenizer(reader.readLine());		
    160 			int l = Integer.parseInt(tokenizer.nextToken());
    161 			int r = Integer.parseInt(tokenizer.nextToken());
    162 			res[i] = new Segment(l, r);
    163 		}
    164 		return res;
    165 	}
    166 	
    167 	public static void main(String[] args) throws Exception {
    168 		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    169 		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    170 		Segment[] a = readList(reader);
    171 		Segment[] b = readList(reader);
    172 		int minR1 = infinity, maxL1 = -infinity;
    173 		int minR2 = infinity, maxL2 = -infinity;
    174 		for (int i = 0; i < a.length; i++) {
    175 			maxL1 = Math.max(maxL1, a[i].l);
    176 			minR1 = Math.min(minR1, a[i].r);	
    177 		}
    178 		for (int i = 0; i < b.length; i++) {
    179 			maxL2 = Math.max(maxL2, b[i].l);
    180 			minR2 = Math.min(minR2, b[i].r);	
    181 		}
    182 		int res = Math.max(maxL2 - minR1, maxL1 - minR2);
    183 		writer.write(Integer.toString(Math.max(res, 0)));
    184 		reader.close();
    185 		writer.close();
    186 	}
    187 }
    188 ```
    189 
    190 **Python code**
    191 
    192 ```
    193 infinity = 1234567890
    194 minR1 = minR2 = infinity
    195 maxL1 = maxL2 = -infinity
    196 n = int(input())
    197 for i in range(0, n):
    198 	(l, r) = map(int, input().split())
    199 	maxL1 = max(maxL1, l)
    200 	minR1 = min(minR1, r)
    201 m = int(input())
    202 for i in range(0, m):
    203 	(l, r) = map(int, input().split())
    204 	maxL2 = max(maxL2, l)
    205 	minR2 = min(minR2, r)
    206 res = max(maxL2 - minR1, maxL1 - minR2);
    207 print(max(res, 0))
    208 ```
    209 
    210 [785C - Anton and Fairy Tale](/contest/785/problem/C "Codeforces Round 404 (Div. 2)")
    211 
    212 This problem had weak pretests. It was made intentionally to cause more hacks. And I have warned you about it in the announcement :)
    213 
    214 **Hint**
    215 
    216 Model the process to determine how the number of corns in the barn changes.
    217 
    218 **Tutorial**
    219 
    220 Tutorial is loading...
    221 
    222 **C++ code**
    223 
    224 ```
    225 #include <iostream>
    226 #include <cstdint>
    227 
    228 using namespace std;
    229 
    230 int main() {
    231 	ios_base::sync_with_stdio(false);
    232 	int64_t n, m;
    233 	cin >> n >> m;
    234 	if (n <= m) {
    235 		cout << n << endl;
    236 	} else {
    237 		n -= m;
    238 		int64_t l = 0, r = 2e9;
    239 		while (l < r) {
    240 			int64_t m = (l + r) / 2;
    241 			int64_t val = m * (m+1) / 2;
    242 			if (val >= n) {
    243 				r = m;
    244 			} else {
    245 				l = m+1;
    246 			}
    247 		}
    248 		cout << l + m << endl;
    249 	}
    250 	return 0;
    251 }
    252 ```
    253 
    254 **Java code**
    255 
    256 ```
    257 import java.io.*;
    258 import java.util.*;
    259 
    260 public class SparrowsJava {
    261 	public static void main(String[] args) throws Exception {
    262 		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    263 		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    264 		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    265 		long n = Long.parseLong(tokenizer.nextToken());
    266 		long m = Long.parseLong(tokenizer.nextToken());	
    267 		if (n <= m) {
    268 			writer.write(Long.toString(n));
    269 		} else {
    270 			n -= m;
    271 			long l = 0, r = (long)2e9;
    272 			while (l < r) {
    273 				long med = (l + r) / 2;
    274 				long val = med * (med+1) / 2;
    275 				if (val >= n) {
    276 					r = med;
    277 				} else {
    278 					l = med+1;
    279 				}
    280 			}
    281 			writer.write(Long.toString(l + m));
    282 		}
    283 		reader.close();
    284 		writer.close();
    285 	}
    286 }
    287 ```
    288 
    289 **Python code**
    290 
    291 ```
    292 (n, m) = map(int, input().split())
    293 if n <= m:
    294 	print(n)
    295 else:
    296 	aM = m
    297 	n -= m
    298 	(l, r) = (0, int(2e9))
    299 	while l < r:
    300 		m = (l + r) // 2;
    301 		val = m * (m+1) // 2;
    302 		if val >= n:
    303 			r = m
    304 		else:
    305 			l = m+1
    306 	print(l + aM)
    307 ```
    308 
    309 [785D - Anton and School - 2](/contest/785/problem/D "Codeforces Round 404 (Div. 2)")
    310 
    311 **Hint**
    312 
    313 Solve a simplified version of the problem. Let our sequence first contains *x* opening brackets and then contains *y* closing brackets, and the last opening bracket must necessarily appear in our RSBS. Use a naive solution to see how the answer looks. Think what to do next.
    314 
    315 **Tutorial**
    316 
    317 Tutorial is loading...
    318 
    319 **C++ code**
    320 
    321 ```
    322 #include <iostream>
    323 #include <vector>
    324 #include <cstdint>
    325 
    326 using namespace std;
    327 
    328 int mod = (int)1e9 + 7;
    329 
    330 int64_t extGcd(int64_t a, int64_t b, int64_t& x, int64_t& y) { 
    331 	if (!a) {
    332 		x = 0;
    333 		y = 1;
    334 		return b;
    335 	}
    336 	int64_t x1, y1;
    337 	int64_t d = extGcd(b % a, a, x1, y1);
    338 	x = y1 - (b / a) * x1;
    339 	y = x1;
    340 	return d;
    341 }
    342 
    343 inline int addMod(int a, int b, int m = mod) {
    344 	return ((int64_t)a + b) % m;
    345 }
    346 
    347 inline int mulMod(int a, int b, int m = mod) {
    348 	return ((int64_t)a * b) % m;
    349 }
    350 
    351 inline int divMod(int a, int b, int m = mod) {
    352 	int64_t x, y;
    353 	int64_t g = extGcd(b, m, x, y);
    354 	if (g != 1) {
    355 		cerr << "Bad gcd!" << endl;
    356 		for (;;);
    357 	}
    358 	x = (x % m + m) % m;
    359 	return mulMod(a, x, m);
    360 }
    361 
    362 const int factRange = 1000000;
    363 int fact[factRange];
    364 
    365 inline void precalcFactorials() {
    366 	fact[0] = 1;
    367 	for (int i = 1; i < factRange; i++) {
    368 		fact[i] = mulMod(fact[i-1], i);
    369 	}
    370 }
    371 
    372 inline int F(int n) {
    373 	return (n < 0) ? 0 : fact[n];
    374 }
    375 
    376 inline int C(int k, int n) {
    377 	return divMod(F(n), mulMod(F(n-k), F(k)));
    378 }
    379 
    380 int main() {
    381 	ios_base::sync_with_stdio(false);
    382 	string s; 
    383 	cin >> s;
    384 	int len = s.size();
    385 	precalcFactorials();
    386 	vector<int> opnLeft(len), clsRight(len);
    387 	opnLeft[0] = (s[0] == '(') ? 1 : 0;
    388 	for (int i = 1; i < len; i++) {
    389 		opnLeft[i] = opnLeft[i-1] + ((s[i] == '(') ? 1 : 0);
    390 	}
    391 	clsRight[len-1] = (s[len-1] == ')') ? 1 : 0;
    392 	for (int i = len-2; i >= 0; i--) {
    393 		clsRight[i] = clsRight[i+1] + ((s[i] == ')') ? 1 : 0);
    394 	}
    395 	int res = 0;
    396 	for (int i = 0; i < len; i++) {
    397 		if (s[i] != '(' || clsRight[i] == 0) {
    398 			continue;
    399 		}
    400 		int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1);
    401 		res = addMod(res, add);
    402 	}
    403 	cout << res << endl;
    404 	return 0;
    405 }
    406 ```
    407 
    408 **Java code**
    409 
    410 ```
    411 import java.io.*;
    412 import java.util.*;
    413 
    414 public class BracketsJava {
    415 	public static int mod = (int)1e9 + 7;
    416 	
    417 	public static class ExtGcdResult {
    418 		long x;
    419 		long y;
    420 	}
    421 	
    422 	public static long extGcd(long a, long b, ExtGcdResult res) { 
    423 		if (a == 0) {
    424 			res.x = 0L;
    425 			res.y = 1L;
    426 			return b;
    427 		}
    428 		ExtGcdResult newRes = new ExtGcdResult();
    429 		long d = extGcd(b % a, a, newRes); 
    430 		res.x = newRes.y - (b / a) * newRes.x;
    431 		res.y = newRes.x;
    432 		return d; 
    433 	}
    434 	
    435 	public static final int addMod(int a, int b) { 
    436 		return (int)(((long)a + b) % mod); 
    437 	}
    438 
    439 	public static final int mulMod(int a, int b) { 
    440 		return (int)(((long)a * b) % mod); 
    441 	}
    442 	
    443 	public static final int divMod(int a, int b) { 
    444 		ExtGcdResult res = new ExtGcdResult();
    445 		long g = extGcd(b, mod, res); 
    446 		if (g != 1) {
    447 			System.out.println("Bad gcd!");
    448 			for (;;);
    449 		}
    450 		int q = (int)((res.x % mod + mod) % mod); 
    451 		return mulMod(a, q); 
    452 	}
    453 	
    454 	public static final int[] precalcFactorials() {
    455 		int[] fact = new int[factRange];
    456 		fact[0] = 1;
    457 		for (int i = 1; i < factRange; i++) {
    458 			fact[i] = mulMod(fact[i-1], i);
    459 		}
    460 		return fact;
    461 	}
    462 
    463 	public static final int factRange = 1000000;
    464 	public static final int[] fact = precalcFactorials();
    465 	
    466 	public static final int F(int n) {
    467 		return (n < 0) ? 0 : fact[n];
    468 	}
    469 	
    470 	public static final int C(int k, int n) {
    471 		int res = divMod(F(n), mulMod(F(n-k), F(k)));
    472 		return divMod(F(n), mulMod(F(n-k), F(k)));
    473 	} 
    474 	
    475 	public static void main(String[] args) throws Exception {
    476 		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    477 		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    478 		String s = reader.readLine();
    479 		int len = s.length();
    480 		int[] opnLeft = new int[len], clsRight = new int[len];
    481 		opnLeft[0] = (s.charAt(0) == '(') ? 1 : 0;
    482 		for (int i = 1; i < len; i++) {
    483 			opnLeft[i] = opnLeft[i-1] + ((s.charAt(i) == '(') ? 1 : 0);
    484 		}
    485 		clsRight[len-1] = (s.charAt(len-1) == ')') ? 1 : 0;
    486 		for (int i = len-2; i >= 0; i--) {
    487 			clsRight[i] = clsRight[i+1] + ((s.charAt(i) == ')') ? 1 : 0);
    488 		}
    489 		int res = 0;
    490 		for (int i = 0; i < len; i++) {
    491 			if (s.charAt(i) != '(' || clsRight[i] == 0) {
    492 				continue;
    493 			}
    494 			int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1);
    495 			res = addMod(res, add);
    496 		}		
    497 		writer.write(Integer.toString(res));
    498 		reader.close();
    499 		writer.close();		
    500 	}
    501 }
    502 ```
    503 
    504 [785E - Anton and Permutation](/contest/785/problem/E "Codeforces Round 404 (Div. 2)")
    505 
    506 I'm sorry that this problem was not original. I will try my best to prevent this from happening again.
    507 
    508 If you have TL or ML in this problem, don't think that the time/memory limits are too strict. The model solution works in 1.2 seconds and consumes 9 MB memory.
    509 
    510 **Hint**
    511 
    512 Divide all the queries in ![](https://espresso.codeforces.com/cc36dccfe8c0168c9a297666c47c2329cbd10095.png) blocks. Then divide the positions to the mobile (those ones that will change in this block) and immoblile. Think what to do next.
    513 
    514 **Tutorial**
    515 
    516 Tutorial is loading...
    517 
    518 **C++ code**
    519 
    520 ```
    521 // Thanks to netman for the idea for this wonderful solution :)
    522 #include <iostream>
    523 #include <fstream>
    524 #include <vector>
    525 #include <cstdint>
    526 #include <algorithm>
    527 
    528 using namespace std;
    529 
    530 class SQRTDecomposition {
    531 	private:
    532 		int n, sz;
    533 		vector<int> val;
    534 		vector<int> blocks;
    535 	public:
    536 		inline void add(int v, int delta) {
    537 			val[v] += delta;
    538 			blocks[v / sz] += delta;
    539 		}
    540 		
    541 		inline int sum(int l, int r) {	
    542 			if (l < 0) {
    543 				l = 0;
    544 			}
    545 			if (r >= n) {
    546 				r = n;
    547 			}
    548 			r++;
    549 			int res = 0;
    550 			int lBlock = (l + sz - 1) / sz, rBlock = r / sz;
    551 			for (int i = lBlock; i < rBlock; i++) {
    552 				res += blocks[i];
    553 			}
    554 			int lBlockR = lBlock * sz, rBlockR = rBlock * sz;
    555 			if (lBlockR >= rBlockR) {
    556 				for (int i = l; i < r; i++) {
    557 					res += val[i];
    558 				}
    559 			} else {
    560 				for (int i = l; i < lBlockR; i++) {
    561 					res += val[i];
    562 				}
    563 				for (int i = rBlockR; i < r; i++) {
    564 					res += val[i];
    565 				}
    566 			}
    567 			return res;
    568 		}
    569 		
    570 		inline void clear() {
    571 			val.assign(val.size(), 0);
    572 			blocks.assign(blocks.size(), 0);
    573 		}
    574 		
    575 		SQRTDecomposition(int n, int sz)
    576 			: n(n), sz(sz), val(n, 0), blocks((n + sz - 1) / sz, 0) {
    577 		}
    578 };
    579 
    580 struct ToProcess {
    581 	int x, y1, y2, sgn, id;
    582 };
    583 
    584 const int BLOCK_SZ_Q = 256;
    585 const int BLOCK_SZ_N = 512;
    586 const int MAX_N = 200000;
    587 
    588 int n, q;
    589 vector<ToProcess> sortedL[MAX_N], sortedR[MAX_N];
    590 SQRTDecomposition sum(MAX_N, BLOCK_SZ_N);
    591 int64_t ans[MAX_N], preAns[MAX_N];
    592 pair<int, int> queries[MAX_N];
    593 vector<int> goods;
    594 int p[MAX_N];
    595 bool good[MAX_N];
    596 
    597 inline void add(int q, int sgn, int id) {
    598 	if (q-1 >= 0) {
    599 		sortedL[q-1].push_back({q-1, p[q]+1, n-1, sgn, id});
    600 	}
    601 	if (q+1 < n) {
    602 		sortedR[q+1].push_back({q+1, 0, p[q]-1, sgn, id});
    603 	}
    604 }
    605 
    606 int main() {
    607 	ios_base::sync_with_stdio(false);
    608 	cin >> n >> q;
    609 	for (int i = 0; i < n; i++) {
    610 		p[i] = i;
    611 	}
    612 	for (int i = 0; i < q; i++) {
    613 		cin >> queries[i].first >> queries[i].second;
    614 		queries[i].first--; queries[i].second--;
    615 	}
    616 	int64_t cnt = 0;
    617 	for (int i = 0; i < q; i += BLOCK_SZ_Q) {
    618 		int iEnd = min(q, i + BLOCK_SZ_Q);
    619 		for (int j = 0; j < n; j++) {
    620 			good[j] = false;
    621 		}
    622 		for (int j = i; j < iEnd; j++) {
    623 			good[queries[j].first] = true;
    624 			good[queries[j].second] = true;
    625 		}
    626 		goods.clear();
    627 		for (int j = 0; j < n; j++) {
    628 			if (good[j]) {
    629 				goods.push_back(j);
    630 			}
    631 		}
    632 		int64_t goodCnt = 0;
    633 		for (int j = 0; j < n; j++) {
    634 			sortedL[j].clear();
    635 			sortedR[j].clear();
    636 		}
    637 		for (int j = i; j < iEnd; j++) {
    638 			int a = queries[j].first, b = queries[j].second;
    639 			if (a == b) {
    640 				ans[j] += goodCnt;
    641 				continue;
    642 			}
    643 			for (int k = 0; k < (int)goods.size(); k++) {
    644 				int q = goods[k];
    645 				if (q == a || q == b) {
    646 					continue;
    647 				}
    648 				if ((p[q] < p[a] && q > a) ||
    649 				    (p[q] > p[a] && q < a)) {
    650 					goodCnt--;
    651 				}
    652 				if ((p[q] < p[b] && q > b) ||
    653 				    (p[q] > p[b] && q < b)) {
    654 					goodCnt--;
    655 				}
    656 				if ((p[q] < p[b] && q > a) ||
    657 				    (p[q] > p[b] && q < a)) {
    658 					goodCnt++;
    659 				}
    660 				if ((p[q] < p[a] && q > b) ||
    661 				    (p[q] > p[a] && q < b)) {
    662 					goodCnt++;
    663 				}
    664 			}
    665 			if ((a < b && p[a] > p[b]) ||
    666 				(a > b && p[a] < p[b])) {
    667 				goodCnt--;
    668 			} else {
    669 				goodCnt++;
    670 			}
    671 			ans[j] += goodCnt;
    672 			add(a, -1, j);
    673 			add(b, -1, j);
    674 			swap(p[a], p[b]);
    675 			add(a, +1, j);
    676 			add(b, +1, j);
    677 		}
    678 		sum.clear();
    679 		for (int j = 0; j < n; j++) {
    680 			if (!good[j]) {
    681 				sum.add(p[j], 1);
    682 			}
    683 			for (int k = 0; k < (int)sortedL[j].size(); k++) {
    684 				ToProcess &cur = sortedL[j][k];
    685 				int64_t res = sum.sum(cur.y1, cur.y2);
    686 				res *= cur.sgn;
    687 				preAns[cur.id] += res;
    688 			}
    689 		}
    690 		sum.clear();
    691 		for (int j = n-1; j >= 0; j--) {
    692 			if (!good[j]) {
    693 				sum.add(p[j], 1);
    694 			}
    695 			for (int k = 0; k < (int)sortedR[j].size(); k++) {
    696 				ToProcess &cur = sortedR[j][k];
    697 				int64_t res = sum.sum(cur.y1, cur.y2);
    698 				res *= cur.sgn;
    699 				preAns[cur.id] += res;
    700 			}
    701 		}
    702 		for (int j = i; j < iEnd; j++) {
    703 			if (j != i) {
    704 				preAns[j] += preAns[j-1];	
    705 			}
    706 			ans[j] += cnt + preAns[j];
    707 		}
    708 		cnt = ans[iEnd - 1];
    709 	}
    710 	for (int i = 0; i < q; i++) {
    711 		cout << ans[i] << "\n";
    712 	}
    713 	return 0;
    714 }
    715 ```
    716 
    717 **Java code**
    718 
    719 ```
    720 import java.io.*;
    721 import java.util.*;
    722 
    723 public class InversionNSqrtNNoVectors {
    724 	private static final int BLOCK_SZ_Q = 256;
    725 	private static final int BLOCK_SZ_N = 512;
    726 	
    727 	public static class ToProcess {
    728 		public int x, y1, y2, sgn, id;
    729 		
    730 		public void set(int pX, int pY1, int pY2, int pSgn, int pId) {
    731 			x = pX;
    732 			y1 = pY1;
    733 			y2 = pY2;
    734 			sgn = pSgn;
    735 			id = pId;
    736 		}
    737 		
    738 		public ToProcess() {
    739 		}
    740 	}
    741 	
    742 	public static class ToProcessCompareAsc implements Comparator<ToProcess> {
    743 		@Override
    744 		public int compare(ToProcess o1, ToProcess o2) {
    745 			return o1.x - o2.x;
    746 		}
    747 	}
    748 	
    749 	public static class ToProcessCompareDesc implements Comparator<ToProcess> {
    750 		@Override
    751 		public int compare(ToProcess o1, ToProcess o2) {
    752 			return o2.x - o1.x;
    753 		}
    754 	}
    755 	
    756 	static int n, q;
    757 	static int[] p;
    758 	static ToProcess[] queryL, queryR;
    759 	static int queryLCnt, queryRCnt;
    760 	static SQRTDecomposition sum;
    761 	static ToProcessCompareAsc ascCmp = new ToProcessCompareAsc();
    762 	static ToProcessCompareDesc descCmp = new ToProcessCompareDesc();
    763 	
    764 	public static final void add(int q, int sgn, int id) {
    765 		if (q-1 >= 0) {
    766 			queryL[queryLCnt++].set(q-1, p[q]+1, n-1, sgn, id);
    767 		}
    768 		if (q+1 < n) {
    769 			queryR[queryRCnt++].set(q+1, 0, p[q]-1, sgn, id);
    770 		}
    771 	}
    772 	
    773 	public static void main(String[] args) throws Exception {
    774 		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    775 		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    776 		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    777 		n = Integer.parseInt(tokenizer.nextToken());
    778 		q = Integer.parseInt(tokenizer.nextToken());
    779 		int[] qL = new int[q], qR = new int[q];
    780 		long[] ans = new long[q], preAns = new long[q];
    781 		p = new int[n];
    782 		for (int i = 0; i < n; i++) {
    783 			p[i] = i;
    784 		}
    785 		for (int i = 0; i < q; i++) {
    786 			tokenizer = new StringTokenizer(reader.readLine());
    787 			qL[i] = Integer.parseInt(tokenizer.nextToken()) - 1;
    788 			qR[i] = Integer.parseInt(tokenizer.nextToken()) - 1;
    789 		}
    790 		long cnt = 0;
    791 		boolean[] good = new boolean[n];
    792 		int[] goods = new int[n];
    793 		int goodsSize = 0;
    794 		queryL = new ToProcess[4 * BLOCK_SZ_Q]; queryR = new ToProcess[4 * BLOCK_SZ_Q];
    795 		for (int j = 0; j < 4 * BLOCK_SZ_Q; j++) {
    796 			queryL[j] = new ToProcess();
    797 			queryR[j] = new ToProcess();
    798 		}
    799 		SQRTDecomposition sum = new SQRTDecomposition(n, BLOCK_SZ_N);
    800 		for (int i = 0; i < q; i += BLOCK_SZ_Q) {
    801 			int iEnd = Math.min(q, i + BLOCK_SZ_Q);
    802 			Arrays.fill(good, false);
    803 			for (int j = i; j < iEnd; j++) {
    804 				good[qL[j]] = true;
    805 				good[qR[j]] = true;
    806 			}
    807 			goodsSize = 0;
    808 			for (int j = 0; j < n; j++) {
    809 				if (good[j]) {
    810 					goods[goodsSize++] = j;
    811 				}
    812 			}
    813 			long goodCnt = 0;
    814 			queryLCnt = 0;
    815 			queryRCnt = 0;
    816 			for (int j = i; j < iEnd; j++) {
    817 				int a = qL[j], b = qR[j];
    818 				if (a == b) {
    819 					ans[j] += goodCnt;
    820 					continue;
    821 				}
    822 				for (int k = 0; k < goodsSize; k++) {
    823 					int q = goods[k];
    824 					if (q == a || q == b) {
    825 						continue;
    826 					}
    827 					if ((p[q] < p[a] && q > a) ||
    828 						(p[q] > p[a] && q < a)) {
    829 						goodCnt--;
    830 					}
    831 					if ((p[q] < p[b] && q > b) ||
    832 						(p[q] > p[b] && q < b)) {
    833 						goodCnt--;
    834 					}
    835 					if ((p[q] < p[b] && q > a) ||
    836 						(p[q] > p[b] && q < a)) {
    837 						goodCnt++;
    838 					}
    839 					if ((p[q] < p[a] && q > b) ||
    840 						(p[q] > p[a] && q < b)) {
    841 						goodCnt++;
    842 					}
    843 				}
    844 				if ((a < b && p[a] > p[b]) ||
    845 					(a > b && p[a] < p[b])) {
    846 					goodCnt--;
    847 				} else {
    848 					goodCnt++;
    849 				}
    850 				ans[j] += goodCnt;
    851 				add(a, -1, j);
    852 				add(b, -1, j);
    853 				int tmp = p[a];
    854 				p[a] = p[b];
    855 				p[b] = tmp;
    856 				add(a, +1, j);
    857 				add(b, +1, j);
    858 			}
    859 			sum.clear();
    860 			Arrays.sort(queryL, 0, queryLCnt, ascCmp);
    861 			int curL = 0;
    862 			for (int j = 0; j < n; j++) {
    863 				if (!good[j]) {
    864 					sum.add(p[j], 1);
    865 				}
    866 				for (; curL < queryLCnt; curL++) {
    867 					ToProcess cur = queryL[curL];
    868 					if (cur.x != j) {
    869 						break;
    870 					}
    871 					int res = sum.sum(cur.y1, cur.y2);
    872 					res *= cur.sgn;
    873 					preAns[cur.id] += res;
    874 				}
    875 			}
    876 			sum.clear();
    877 			Arrays.sort(queryR, 0, queryRCnt, descCmp);
    878 			int curR = 0;
    879 			for (int j = n-1; j >= 0; j--) {
    880 				if (!good[j]) {
    881 					sum.add(p[j], 1);
    882 				}
    883 				for (; curR < queryRCnt; curR++) {
    884 					ToProcess cur = queryR[curR];
    885 					if (cur.x != j) {
    886 						break;
    887 					}
    888 					int res = sum.sum(cur.y1, cur.y2);
    889 					res *= cur.sgn;
    890 					preAns[cur.id] += res;
    891 				}
    892 			}
    893 			for (int j = i; j < iEnd; j++) {
    894 				if (j != i) {
    895 					preAns[j] += preAns[j-1];	
    896 				}
    897 				ans[j] += cnt + preAns[j];
    898 			}
    899 			cnt = ans[iEnd - 1];
    900 		}
    901 		for (int i = 0; i < q; i++) {
    902 			writer.write(Long.toString(ans[i]));
    903 			writer.newLine();
    904 		}
    905 		reader.close();
    906 		writer.close();
    907 	}
    908 }
    909 
    910 class SQRTDecomposition {
    911 	private int n;
    912 	private int sz;
    913 	private int[] val;
    914 	private int[] blocks;
    915 	
    916 	public final void add(int v, int delta) {
    917 		val[v] += delta;
    918 		blocks[v / sz] += delta;
    919 	}
    920 		
    921 	public final int sum(int l, int r) {	
    922 		if (l < 0) {
    923 			l = 0;
    924 		}
    925 		if (r >= n) {
    926 			r = n;
    927 		}
    928 		r++;
    929 		int res = 0;
    930 		int lBlock = (l + sz - 1) / sz, rBlock = r / sz;
    931 		for (int i = lBlock; i < rBlock; i++) {
    932 			res += blocks[i];
    933 		}
    934 		int lBlockR = lBlock * sz, rBlockR = rBlock * sz;
    935 		if (lBlockR >= rBlockR) {
    936 			for (int i = l; i < r; i++) {
    937 				res += val[i];
    938 			}
    939 		} else {
    940 			for (int i = l; i < lBlockR; i++) {
    941 				res += val[i];
    942 			}
    943 			for (int i = rBlockR; i < r; i++) {
    944 				res += val[i];
    945 			}
    946 		}
    947 		return res;
    948 	}
    949 	
    950 	public void clear() {
    951 		Arrays.fill(val, 0);
    952 		Arrays.fill(blocks, 0);
    953 	}
    954 		
    955 	SQRTDecomposition(int pN, int pSz) {
    956 		n = pN;
    957 		sz = pSz;
    958 		val = new int[n];
    959 		blocks = new int[(n + sz - 1) / sz];
    960 	}
    961 }
    962 ```
    963 
    964 Alternative solution from [Vladik](/profile/Vladik "Candidate Master Vladik"):
    965 
    966 **C++ code**
    967 
    968 ```
    969 #include <iostream>
    970 #include <cstdio>
    971 #include <algorithm>
    972 #include <cmath>
    973 #include <set>
    974 #include <map>
    975 #include <vector>
    976 #include <iomanip>
    977 
    978 #define sqr(a) (a)*(a)
    979 #define all(a) (a).begin(), (a).end()
    980 using namespace std;
    981 
    982 template <typename T>
    983 T next_int() {
    984     T ans = 0, t = 1;
    985     char ch;
    986     do { ch = getchar(); } while(ch <= ' ') ;
    987     if(ch == '-') {
    988         t = -1;
    989         ch = getchar();
    990     }
    991     while(ch >= '0' && ch <= '9') {
    992         ans = ans * 10 + (ch - '0');
    993         ch = getchar();
    994     }
    995     return ans * t;
    996 }
    997 
    998 string next_token() {
    999     char ch;
   1000     string ans = "";
   1001     do { ch = getchar(); } while(ch <= ' ') ;
   1002     while(ch >= ' ') {
   1003         ans += ch;
   1004         ch = getchar();
   1005     }
   1006     return ans;
   1007 }
   1008 
   1009 const long long INF = (long long)1e18 + 227 + 1;
   1010 const int INFINT = (int)1e9 + 227 + 1;
   1011 const int MAXN = (int)2e5 + 227 + 1;
   1012 const int MOD = (int)1e9 + 7;
   1013 const long double EPS = 1e-9;
   1014 
   1015 long long bin_pow(long long n, long long k) {
   1016     if(!k) return 1;
   1017     long long ans = bin_pow(n, k / 2);
   1018     ans = ans * ans % MOD;
   1019     if(k % 2) ans = ans * n % MOD;
   1020     return ans;
   1021 }
   1022 
   1023 struct tree {
   1024     int size_block;
   1025     int len; 
   1026  
   1027     tree(int len) : len(len) {
   1028         size_block = sqrt(len);
   1029  
   1030         kek.resize(len / size_block + 1, vector<int>(size_block, 0));
   1031  
   1032         pr_block.resize(len / size_block + 1, 0);
   1033     }
   1034  
   1035     vector<int> pr_block;
   1036     vector<vector<int> > kek;
   1037  
   1038     void inc(int pos, int num) {
   1039         int x = pos / size_block;
   1040  
   1041         for(int i = pos % size_block; i < size_block; i++) {
   1042             kek[x][i] += num;
   1043         }
   1044  
   1045         for(int i = 0; i <= len / size_block; i++)
   1046             if(i == 0) {
   1047                 pr_block[i] = kek[i][size_block - 1];
   1048             } else {
   1049                 pr_block[i] = pr_block[i - 1] + kek[i][size_block - 1]; 
   1050             }
   1051     }
   1052  
   1053     int f(int a) {
   1054         return a / size_block;
   1055     }
   1056  
   1057     long long get(vector<int> &a, int l, int r, bool ok = 1) {
   1058         if(ok == 1) {
   1059             l %= size_block;
   1060             r %= size_block;
   1061         }
   1062  
   1063         return a[r] - (l ? a[l - 1] : 0);
   1064     }
   1065  
   1066     int get(int l, int r) {
   1067         if(l > r) return 0;
   1068 
   1069         r = min(r, len);
   1070   
   1071         if(f(l) == f(r))
   1072             return get(kek[f(l)], l, r);
   1073      
   1074         int ans = 0;
   1075  
   1076         if(l % size_block) {
   1077             ans += get(kek[f(l)], l, size_block - 1);
   1078  
   1079             l += size_block - l % size_block;
   1080         }
   1081  
   1082         if(r % size_block != size_block - 1) {
   1083             ans += get(kek[f(r)], 0, r);
   1084  
   1085             r -= r % size_block + 1;
   1086         }
   1087  
   1088         ans += get(pr_block, f(l), f(r), 0);
   1089  
   1090         return ans;
   1091     }
   1092  
   1093     int get_pref(int p) {
   1094         return get(1, p - 1);
   1095     }
   1096 
   1097     int get_suff(int p) {
   1098         return get(p + 1, len);
   1099     }
   1100 } ;
   1101 
   1102 struct mda {
   1103     vector<int> a;
   1104     vector<tree> t;
   1105     int len, sz;
   1106     long long ans;
   1107 
   1108     mda(int len) : len(len) {
   1109         sz = 2000;
   1110         ans = 0;
   1111 
   1112         a.resize(len + 1);
   1113         for(int i = 1; i <= len; i++)
   1114             a[i] = i;
   1115 
   1116         for(int i = 1; i <= len; i += sz) {
   1117             t.push_back(tree(len));
   1118             for(int j = i; j < i + sz && j <= len; j++)
   1119                 add(j, j);
   1120         }
   1121     }
   1122 
   1123     int get_pref(int L, int R, int k) {
   1124         int ans = 0;
   1125 
   1126         for(int l = 1; l <= R; l += sz) {
   1127             int r = l + sz - 1;
   1128 
   1129             if(r < L || l > R) continue;
   1130 
   1131             if(L <= l && r <= R)
   1132                 ans += t[(l - 1) / sz].get_pref(k);
   1133             else
   1134                 for(int i = max(l, L); i <= min(r, R); i++) 
   1135                     ans += (a[i] < k);
   1136         }
   1137 
   1138         return ans;
   1139     }
   1140 
   1141     int get_suff(int L, int R, int k) {
   1142         int ans = 0;
   1143 
   1144         for(int l = 1; l <= R; l += sz) {
   1145             int r = l + sz - 1;
   1146 
   1147             if(r < L || l > R) continue;
   1148 
   1149             if(L <= l && r <= R)
   1150                 ans += t[(l - 1) / sz].get_suff(k);
   1151             else
   1152                 for(int i = max(l, L); i <= min(r, R); i++) 
   1153                     ans += (a[i] > k);
   1154         }
   1155 
   1156         return ans;
   1157     }
   1158 
   1159     void del(int p, int k) {
   1160         p = (p - 1) / sz;
   1161         t[p].inc(k, -1);
   1162     }
   1163 
   1164     void add(int p, int k) {
   1165         p = (p - 1) / sz;
   1166         t[p].inc(k, 1);
   1167     }
   1168 
   1169     void sw(int i, int j) {
   1170         if(i == j) return;
   1171         if(i > j) swap(i, j);
   1172 
   1173         ans -= get_pref(i, j, a[i]);
   1174         ans -= get_suff(i, j, a[j]);
   1175 
   1176         if(a[i] > a[j]) ans++;
   1177 
   1178         del(i, a[i]);
   1179         del(j, a[j]);
   1180         swap(a[i], a[j]);
   1181         add(i, a[i]);
   1182         add(j, a[j]);
   1183 
   1184         ans += get_pref(i, j, a[i]);
   1185         ans += get_suff(i, j, a[j]);
   1186 
   1187         if(a[i] > a[j]) ans--;
   1188     }
   1189 } ;
   1190 
   1191 int main() {
   1192     // freopen(".in", "r", stdin);
   1193 
   1194     int n, m; cin >> n >> m;
   1195 
   1196     mda t(n);
   1197 
   1198     for(int i = 0; i < m; i++) {
   1199         int x, y; cin >> x >> y;
   1200 
   1201         t.sw(x, y);
   1202         
   1203         cout << t.ans << "\n";
   1204     }
   1205 }
   1206 ```
   1207 
   1208 Alternative solution from [netman](/profile/netman "Master netman"):
   1209 
   1210 **Java code**
   1211 
   1212 ```
   1213 import java.io.*;
   1214 import java.util.*;
   1215 
   1216 public class NsqrtNlogNnetman implements Runnable {
   1217     static class InputReader {
   1218         BufferedReader reader;
   1219         StringTokenizer tokenizer;
   1220         InputReader(InputStream in) {
   1221             reader = new BufferedReader(new InputStreamReader(in), 32768);
   1222             tokenizer = null;
   1223         }
   1224         String next() {
   1225             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
   1226                 try {
   1227                     tokenizer = new StringTokenizer(reader.readLine());
   1228                 } catch (IOException e) {
   1229                     e.printStackTrace();
   1230                     throw new RuntimeException(e);
   1231                 }
   1232             }
   1233             return tokenizer.nextToken();
   1234         }
   1235         int nextInt() {
   1236             return Integer.parseInt(next());
   1237         }
   1238         long nextLong() {
   1239             return Long.parseLong(next());
   1240         }
   1241         double nextDouble() {
   1242             return Double.parseDouble(next());
   1243         }
   1244     }
   1245 
   1246     static class Fenwick {
   1247         int[] ft;
   1248         Fenwick(int n) {
   1249             ft = new int[n];
   1250         }
   1251         void add(int r, int val) {
   1252             while (r < ft.length) {
   1253                 ft[r] += val;
   1254                 r |= r + 1;
   1255             }
   1256         }
   1257         int sum(int r) {
   1258             int res = 0;
   1259             while (r >= 0) {
   1260                 res += ft[r];
   1261                 r = (r & (r + 1)) - 1;
   1262             }
   1263             return res;
   1264         }
   1265         void clear() {
   1266             Arrays.fill(ft, 0);
   1267         }
   1268     }
   1269 
   1270     static class Query {
   1271         int x, bound, sign, id;
   1272         Query(int x, int bound, int sign, int id) {
   1273             this.x = x;
   1274             this.bound = bound;
   1275             this.sign = sign;
   1276             this.id = id;
   1277         }
   1278     }
   1279 
   1280     static void getOnPrefSmaller(List<Query> qrs, int r, int y, int id, int sign) {
   1281         qrs.add(new Query(r, y, sign, id));
   1282     }
   1283 
   1284     static void getOnPrefBetween(List<Query> qrs, int r, int x, int y, int id, int sign) {
   1285         getOnPrefSmaller(qrs, r, y, id, sign);
   1286         getOnPrefSmaller(qrs, r, x, id, -sign);
   1287     }
   1288 
   1289     static void getOnSegmentBetween(List<Query> qrs, int l, int r, int x, int y, int id, int sign) {
   1290         if (x > y) return;
   1291         getOnPrefBetween(qrs, r, x, y, id, sign);
   1292         getOnPrefBetween(qrs, l, x, y, id, -sign);
   1293     }
   1294 
   1295     @Override
   1296     public void run() {
   1297 
   1298         InputReader in = new InputReader(System.in);
   1299         PrintWriter out = new PrintWriter(System.out);
   1300 
   1301         int n = in.nextInt();
   1302         int q = in.nextInt();
   1303 
   1304         int[] l = new int[q];
   1305         int[] r = new int[q];
   1306 
   1307         for (int i = 0; i < q; i++) {
   1308             l[i] = in.nextInt() - 1;
   1309             r[i] = in.nextInt() - 1;
   1310         }
   1311 
   1312         int[] perm = new int[n];
   1313 
   1314         for (int i = 0; i < n; i++) {
   1315             perm[i] = n - i - 1;
   1316         }
   1317 
   1318         final int BLOCK = 300;
   1319 
   1320         long inv = 0L;
   1321 
   1322         boolean[] isInteresting = new boolean[n];
   1323 
   1324         long[] add = new long[q];
   1325 
   1326         Fenwick f = new Fenwick(n);
   1327 
   1328         for (int i = 0; i < q; i += BLOCK) {
   1329             int from = i, to = Math.min(i + BLOCK, q) - 1;
   1330             List<Integer> lst = new ArrayList<>();
   1331             for (int j = from; j <= to; j++) {
   1332                 lst.add(l[j]);
   1333                 lst.add(r[j]);
   1334             }
   1335             lst.sort(Integer::compareTo);
   1336             lst = new ArrayList<>(new HashSet<>(lst));
   1337             int[] interestingPositions = lst.stream().mapToInt(x -> x).toArray();
   1338             for (int pos : interestingPositions) {
   1339                 isInteresting[pos] = true;
   1340             }
   1341             List<Query> qrs = new ArrayList<>();
   1342             for (int j = from; j <= to; j++) {
   1343                 if (l[j] == r[j]) continue;
   1344                 if (l[j] > r[j]) {
   1345                     int tmp = l[j];
   1346                     l[j] = r[j];
   1347                     r[j] = tmp;
   1348                 }
   1349                 if (perm[l[j]] < perm[r[j]]) {
   1350                     getOnSegmentBetween(qrs, l[j], r[j], perm[l[j]], perm[r[j]], j,-1);
   1351                     int leftValue = perm[l[j]];
   1352                     int rightValue = perm[r[j]];
   1353                     for (int pos : interestingPositions) {
   1354                         if (pos > l[j] && pos < r[j] && perm[pos] > leftValue && perm[pos] < rightValue) {
   1355                             add[j] -= 2;
   1356                         }
   1357                     }
   1358                     add[j]--;
   1359                 } else {
   1360                     getOnSegmentBetween(qrs, l[j], r[j], perm[r[j]], perm[l[j]], j,1);
   1361                     int leftValue = perm[l[j]];
   1362                     int rightValue = perm[r[j]];
   1363                     for (int pos : interestingPositions) {
   1364                         if (pos > l[j] && pos < r[j] && perm[pos] > rightValue && perm[pos] < leftValue) {
   1365                             add[j] += 2;
   1366                         }
   1367                     }
   1368                     add[j]++;
   1369                 }
   1370                 int tmp = perm[l[j]];
   1371                 perm[l[j]] = perm[r[j]];
   1372                 perm[r[j]] = tmp;
   1373             }
   1374             qrs.sort(Comparator.comparingInt(a -> -a.x));
   1375 
   1376             f.clear();
   1377             for (int pos = 0; pos < n; pos++) {
   1378                 if (!isInteresting[pos]) {
   1379                     f.add(perm[pos], 1);
   1380                 }
   1381                 while (!qrs.isEmpty() && qrs.get(qrs.size() - 1).x == pos) {
   1382                     Query t = qrs.get(qrs.size() - 1);
   1383                     qrs.remove(qrs.size() - 1);
   1384                     add[t.id] += 2 * t.sign * f.sum(t.bound);
   1385                 }
   1386             }
   1387             for (int j = from; j <= to; j++) {
   1388                 inv += add[j];
   1389                 out.println(inv);
   1390             }
   1391             for (int pos : interestingPositions) {
   1392                 isInteresting[pos] = false;
   1393             }
   1394         }
   1395 
   1396         out.close();
   1397     }
   1398 
   1399     public static void main(String[] args) {
   1400         new Thread(null, new NsqrtNlogNnetman(), "1", 1L << 28).run();
   1401     }
   1402 }
   1403 ```