Codeforces Round #404. Editorial.
Разница между en1 и en2, 33,905 символ(ов) изменены
Error 404↵
----------↵

Editorial not found.↵

It will appear here very soon.
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! :)↵

[problem:785A]↵

<spoiler summary="Hint">↵
404 Not Found↵
</spoiler>↵

<spoiler summary="Tutorial">↵
[tutorial:785A]↵
</spoiler>↵

<spoiler summary="C++ code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="Java code">↵
~~~~~↵
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();↵
}↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="Python code">↵
~~~~~↵
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)↵
~~~~~↵
</spoiler>↵

[problem:785B]↵

<spoiler summary="Hint">↵
Think of what periods to take if Anton attends chess classes earlier than programming classes and vice versa.↵
</spoiler>↵

<spoiler summary="Tutorial">↵
[tutorial:785B]↵
</spoiler>↵

<spoiler summary="C++ code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="Java code">↵
~~~~~↵
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();↵
}↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="Python code">↵
~~~~~↵
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))↵
~~~~~↵
</spoiler>↵

[problem:785C]↵

This problem had weak pretests. It was made intentionally to cause more hacks. And I have warned you about it in the announcement :)↵

<spoiler summary="Hint">↵
Model the process to determine how the number of corns in the barn changes.↵
</spoiler>↵

<spoiler summary="Tutorial">↵
[tutorial:785C]↵
</spoiler>↵

<spoiler summary="C++ code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="Java code">↵
~~~~~↵
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();↵
}↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="Python code">↵
~~~~~↵
(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)↵
~~~~~↵
</spoiler>↵

[problem:785D]↵

<spoiler summary="Hint">↵
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.↵
</spoiler>↵

<spoiler summary="Tutorial">↵
[tutorial:785D]↵
</spoiler>↵

<spoiler summary="C++ code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="Java code">↵
~~~~~↵
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(); ↵
}↵
}↵
~~~~~↵
</spoiler>↵

[problem:785E]↵

I'm sorry that this problem was not original. I will try my best to prevent this from happening again.↵


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.↵

<spoiler summary="Hint">↵
Divide all the queries in $\sqrt{q}$ blocks. Then divide the positions to the mobile (those ones that will change in this block) and immoblile. Think what to do next.↵
</spoiler>↵

<spoiler summary="Tutorial">↵
[tutorial:785E]↵
</spoiler>↵

<spoiler summary="C++ code">↵
~~~~~↵
// 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;↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="Java code">↵
~~~~~↵
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];↵
}↵
}↵
~~~~~↵
</spoiler>↵

Alternative solution from [user:Vladik,2017-03-15]:↵

<spoiler summary="C++ code">↵
~~~~~↵
#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";↵
    }↵
}↵
~~~~~↵
</spoiler>↵


Alternative solution from [user:netman,2017-03-15]:↵

<spoiler summary="Java code">↵
~~~~~↵
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();↵
    }↵
}↵
~~~~~↵
</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский gepardo 2017-03-15 21:53:33 33905
ru3 Русский gepardo 2017-03-15 21:37:48 33919
en1 Английский gepardo 2017-03-15 20:44:17 112 Initial revision for English translation (published)
ru2 Русский gepardo 2017-03-15 20:43:09 30 Мелкая правка: 'ибка 404\n==================\nРазбор н' -> 'ибка 404\n----------\n\nРазбор н'
ru1 Русский gepardo 2017-03-15 20:41:48 113 Первая редакция (сохранено в черновиках)