fork download
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6. public static void main(String[] args) {
  7. InputReader in = new InputReader(System.in);
  8. OutputWriter out = new OutputWriter(System.out);
  9. TaskD solver = new TaskD(in, out);
  10. solver.solve();
  11. out.close();
  12. }
  13.  
  14. static class TaskD {
  15. static private final int[] dx = {1, -1, 0, 0};
  16. static private final int[] dy = {0, 0, 1, -1};
  17.  
  18. static int n, m;
  19. static int total;
  20.  
  21. static int[][] f;
  22. static int[] posX;
  23. static int[] posY;
  24. static int[] leftBound;
  25.  
  26. List<Integer>[] edges;
  27. LinkCutTree lct;
  28. InputReader in;
  29. OutputWriter out;
  30.  
  31. TaskD(InputReader in, OutputWriter out) {
  32. this.in = in;
  33. this.out = out;
  34. }
  35.  
  36. private void solve() {
  37. n = in.readInt();
  38. m = in.readInt();
  39. total = n * m;
  40. f = new int[n][m];
  41. posX = new int[total];
  42. posY = new int[total];
  43. for(int i = 0; i < n; ++i) {
  44. for(int j = 0; j < m; ++j) {
  45. f[i][j] = in.readInt() - 1;
  46. posX[f[i][j]] = i;
  47. posY[f[i][j]] = j;
  48. }
  49. }
  50. edges = new ArrayList[total];
  51. leftBound = new int[total];
  52. lct = new LinkCutTree(total);
  53. for(int i = 0; i < total; ++i) {
  54. edges[i] = new ArrayList<>();
  55. }
  56. for(int l = 0, r = 0; r < total; ++r) {
  57. l = addCell(l, r);
  58. leftBound[r] = l;
  59. }
  60. long ans = 0;
  61. SegmentTree t = new SegmentTree(total + 4);
  62. for(int r = 0; r < total; ++r) {
  63. int x = posX[r];
  64. int y = posY[r];
  65. List<Integer> seg = new ArrayList<>();
  66. for(int i = 0; i < 4; ++i) {
  67. int px = x + dx[i];
  68. int py = y + dy[i];
  69. if (px < 0 || px >= n) continue;
  70. if (py < 0 || py >= m) continue;
  71. int to = f[px][py];
  72. if (to > r) continue;
  73. seg.add(to);
  74. }
  75. seg.add(-1);
  76. seg.add(r);
  77. Collections.sort(seg);
  78. for(int i = seg.size() - 1, comp = 1; i > 0; --i) {
  79. if (seg.get(i - 1) + 1 > seg.get(i)) {
  80. --comp;
  81. continue;
  82. }
  83. t.inc(seg.get(i - 1) + 1, seg.get(i) + 1, comp);
  84. --comp;
  85. }
  86. ans += t.query(leftBound[r], r + 1);
  87. }
  88. out.print(ans);
  89. }
  90.  
  91. private int addCell(int l, int r) {
  92. int x = posX[r];
  93. int y = posY[r];
  94. for(int i = 0; i < 4; ++i) {
  95. int px = x + dx[i];
  96. int py = y + dy[i];
  97. if (px < 0 || px >= n) continue;
  98. if (py < 0 || py >= m) continue;
  99. int to = f[px][py];
  100. while (l <= to && to <= r) {
  101. if (lct.link(to, r)) {
  102. edges[to].add(r);
  103. break;
  104. }
  105. removeCell(l);
  106. ++l;
  107. }
  108. }
  109. return l;
  110. }
  111.  
  112. private void removeCell(int c) {
  113. for(int to : edges[c]) {
  114. lct.cut(c, to);
  115. }
  116. edges[c].clear();
  117. }
  118. }
  119.  
  120. static class SegmentTree {
  121. int size;
  122. int height;
  123. int[] t;
  124. int[] cnt;
  125. int[] push;
  126.  
  127. SegmentTree(int n) {
  128. this.size = n;
  129. this.height = 0;
  130. int temp = n;
  131. while (temp > 0) {
  132. temp >>= 1;
  133. ++this.height;
  134. }
  135. t = new int[n << 1];
  136. cnt = new int[n << 1];
  137. push = new int[n];
  138. for(int i = 0; i < n; ++i) {
  139. cnt[i + n] = 1;
  140. }
  141. for(int i = n - 1; i >= 0; --i) {
  142. cnt[i] = cnt[i << 1] + cnt[i << 1 | 1];
  143. }
  144. }
  145.  
  146. private void apply(int p, int value) {
  147. t[p] += value;
  148. if (p < size) push[p] += value;
  149. }
  150.  
  151. private void recalc(int p) {
  152. while (p > 1) {
  153. p >>= 1;
  154. t[p] = Math.min(t[p << 1], t[p << 1 | 1]) + push[p];
  155. cnt[p] = (t[p] == t[p << 1] + push[p] ? cnt[p << 1] : 0)
  156. + (t[p] == t[p << 1 | 1] + push[p] ? cnt[p << 1 | 1] : 0);
  157. }
  158. }
  159.  
  160. private void push(int p) {
  161. for (int s = height; s > 0; s--) {
  162. int i = p >> s;
  163. if (push[i] != 0) {
  164. apply(i << 1, push[i]);
  165. apply(i << 1 | 1, push[i]);
  166. push[i] = 0;
  167. }
  168. }
  169. }
  170.  
  171. private void inc(int l, int r, int value) {
  172. l += size;
  173. r += size;
  174. int l0 = l;
  175. int r0 = r;
  176. for (; l < r; l >>= 1, r >>= 1) {
  177. if ((l & 1) != 0) apply(l++, value);
  178. if ((r & 1) != 0) apply(--r, value);
  179. }
  180. recalc(l0);
  181. recalc(r0 - 1);
  182. }
  183.  
  184. private int query(int l, int r) {
  185. l += size;
  186. r += size;
  187. push(l);
  188. push(r - 1);
  189. int min = Integer.MAX_VALUE;
  190. int minCount = 0;
  191. for (; l < r; l >>= 1, r >>= 1) {
  192. if ((l & 1) != 0) {
  193. if (min > t[l]) {
  194. min = t[l];
  195. minCount = cnt[l];
  196. } else if (min == t[l]) {
  197. minCount += cnt[l];
  198. }
  199. ++l;
  200. }
  201. if ((r & 1) != 0) {
  202. --r;
  203. if (min > t[r]) {
  204. min = t[r];
  205. minCount = cnt[r];
  206. } else if (min == t[r]) {
  207. minCount += cnt[r];
  208. }
  209. }
  210. }
  211. return minCount;
  212. }
  213. }
  214.  
  215. static class LinkCutTree {
  216.  
  217. private static class Node {
  218. Node left;
  219. Node right;
  220. Node parent;
  221. boolean revert;
  222.  
  223. boolean isRoot() {
  224. return parent == null || (parent.left != this && parent.right != this);
  225. }
  226.  
  227. void push() {
  228. if (revert) {
  229. revert = false;
  230. Node t = left;
  231. left = right;
  232. right = t;
  233. if (left != null) left.revert = !left.revert;
  234. if (right != null) right.revert = !right.revert;
  235. }
  236. }
  237. }
  238.  
  239. static int size;
  240. Node[] nodes;
  241.  
  242. LinkCutTree(int n) {
  243. LinkCutTree.size = n;
  244. nodes = new Node[n];
  245. for(int i = 0; i < n; ++i) {
  246. nodes[i] = new Node();
  247. }
  248. }
  249.  
  250. private boolean link(int x, int y) {
  251. return link(nodes[x], nodes[y]);
  252. }
  253.  
  254. private void cut(int x, int y) {
  255. cut(nodes[x], nodes[y]);
  256. }
  257.  
  258. private static boolean link(Node x, Node y) {
  259. if (connected(x, y))
  260. return false;
  261. makeRoot(x);
  262. x.parent = y;
  263. return true;
  264. }
  265.  
  266. private static void cut(Node x, Node y) {
  267. makeRoot(x);
  268. expose(y);
  269. if (y.right != x || x.left != null || x.right != null) {
  270. throw new RuntimeException("error: no edge (x,y)");
  271. }
  272. y.right.parent = null;
  273. y.right = null;
  274. }
  275.  
  276. static void connect(Node ch, Node p, Boolean isLeftChild) {
  277. if (ch != null)
  278. ch.parent = p;
  279. if (isLeftChild != null) {
  280. if (isLeftChild)
  281. p.left = ch;
  282. else
  283. p.right = ch;
  284. }
  285. }
  286.  
  287. static void rotate(Node x) {
  288. Node p = x.parent;
  289. Node g = p.parent;
  290. boolean isRootP = p.isRoot();
  291. boolean leftChildX = (x == p.left);
  292. connect(leftChildX ? x.right : x.left, p, leftChildX);
  293. connect(p, x, !leftChildX);
  294. connect(x, g, !isRootP ? p == g.left : null);
  295. }
  296.  
  297. static void splay(Node x) {
  298. while (!x.isRoot()) {
  299. Node p = x.parent;
  300. Node g = p.parent;
  301. if (!p.isRoot())
  302. g.push();
  303. p.push();
  304. x.push();
  305. if (!p.isRoot())
  306. rotate((x == p.left) == (p == g.left) ? p/*zig-zig*/ : x/*zig-zag*/);
  307. rotate(x);
  308. }
  309. x.push();
  310. }
  311.  
  312. // makes node x the root of the virtual tree, and also x becomes the leftmost node in its splay tree
  313. static Node expose(Node x) {
  314. Node last = null;
  315. for (Node y = x; y != null; y = y.parent) {
  316. splay(y);
  317. y.left = last;
  318. last = y;
  319. }
  320. splay(x);
  321. return last;
  322. }
  323.  
  324. private static void makeRoot(Node x) {
  325. expose(x);
  326. x.revert = !x.revert;
  327. }
  328.  
  329. private static boolean connected(Node x, Node y) {
  330. if (x == y)
  331. return true;
  332. expose(x);
  333. expose(y);
  334. return x.parent != null;
  335. }
  336. }
  337.  
  338. static class OutputWriter {
  339. private final PrintWriter writer;
  340.  
  341. public OutputWriter(OutputStream outputStream) {
  342. writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  343. }
  344.  
  345. public OutputWriter(Writer writer) {
  346. this.writer = new PrintWriter(writer);
  347. }
  348.  
  349. public void print(Object... objects) {
  350. for (int i = 0; i < objects.length; i++) {
  351. if (i != 0) {
  352. writer.print(' ');
  353. }
  354. writer.print(objects[i]);
  355. }
  356. writer.println();
  357. }
  358.  
  359. public void close() {
  360. writer.close();
  361. }
  362.  
  363. }
  364.  
  365. static class InputReader {
  366. private InputStream stream;
  367. private byte[] buf = new byte[1024];
  368. private int curChar;
  369. private int numChars;
  370. private InputReader.SpaceCharFilter filter;
  371.  
  372. public InputReader(InputStream stream) {
  373. this.stream = stream;
  374. }
  375.  
  376. public int read() {
  377. if (numChars == -1) {
  378. throw new InputMismatchException();
  379. }
  380. if (curChar >= numChars) {
  381. curChar = 0;
  382. try {
  383. numChars = stream.read(buf);
  384. } catch (IOException e) {
  385. throw new InputMismatchException();
  386. }
  387. if (numChars <= 0) {
  388. return -1;
  389. }
  390. }
  391. return buf[curChar++];
  392. }
  393.  
  394. public int readInt() {
  395. int c = read();
  396. while (isSpaceChar(c)) {
  397. c = read();
  398. }
  399. int sgn = 1;
  400. if (c == '-') {
  401. sgn = -1;
  402. c = read();
  403. }
  404. int res = 0;
  405. do {
  406. if (c < '0' || c > '9') {
  407. throw new InputMismatchException();
  408. }
  409. res *= 10;
  410. res += c - '0';
  411. c = read();
  412. } while (!isSpaceChar(c));
  413. return res * sgn;
  414. }
  415.  
  416. public boolean isSpaceChar(int c) {
  417. if (filter != null) {
  418. return filter.isSpaceChar(c);
  419. }
  420. return isWhitespace(c);
  421. }
  422.  
  423. public static boolean isWhitespace(int c) {
  424. return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  425. }
  426.  
  427. public double readDouble() {
  428. int c = read();
  429. while (isSpaceChar(c)) {
  430. c = read();
  431. }
  432. int sgn = 1;
  433. if (c == '-') {
  434. sgn = -1;
  435. c = read();
  436. }
  437. double res = 0;
  438. while (!isSpaceChar(c) && c != '.') {
  439. if (c == 'e' || c == 'E') {
  440. return res * Math.pow(10, readInt());
  441. }
  442. if (c < '0' || c > '9') {
  443. throw new InputMismatchException();
  444. }
  445. res *= 10;
  446. res += c - '0';
  447. c = read();
  448. }
  449. if (c == '.') {
  450. c = read();
  451. double m = 1;
  452. while (!isSpaceChar(c)) {
  453. if (c == 'e' || c == 'E') {
  454. return res * Math.pow(10, readInt());
  455. }
  456. if (c < '0' || c > '9') {
  457. throw new InputMismatchException();
  458. }
  459. m /= 10;
  460. res += (c - '0') * m;
  461. c = read();
  462. }
  463. }
  464. return res * sgn;
  465. }
  466.  
  467. public interface SpaceCharFilter {
  468. public boolean isSpaceChar(int ch);
  469. }
  470.  
  471. }
  472. }
Runtime error #stdin #stdout #stderr 0.05s 2184192KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
Exception in thread "main" java.util.InputMismatchException
	at Main$InputReader.read(Main.java:378)
	at Main$InputReader.readInt(Main.java:397)
	at Main$TaskD.solve(Main.java:37)
	at Main$TaskD.access$000(Main.java:14)
	at Main.main(Main.java:10)