| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P177PROJ - ROUND 7J - Cặp số nghịch thế |
Tèo được cho một dãy số đặc biệt gồm n phần tử, các phần tử này là các số nguyên từ 1 đến n đôi một khác nhau. Ban đầu, n phần tử này được sắp xếp tăng dần từ 1 đến n.
Tèo nhận được q truy vấn từ Tí. Với mỗi truy vấn, Tèo sẽ phải đổi chỗ 2 phần tử ở 2 vị trí x1 và x2. Câu hỏi Tèo cần là lời là sau khi đổi chỗ, trong dãy số hiện tại có bao nhiêu cặp số nghịch thế.
Một cặp số nghịch thế (ai, aj) là cặp số mà có i < j và ai > aj.
Input
Dòng đầu gồm 2 số nguyên n và q (1 <= n <= 200000, 1<= q <= 50000) là số lượng phần tử của dãy số và số lượng truy vấn.
q dòng tiếp theo, trên mỗi dòng gồm 2 số x1, x2 (1 <= x1, x2 <= n) là vị trí của 2 phần tử sẽ được đổi chỗ trong truy vấn.
Output
Gồm q dòng. Trên mỗi dòng in ra một số nguyên là số cặp số nghịch thế của dãy số hiện tại.
Example
Input:
5 4
4 5
2 4
2 5
2 2
Output:
1
4
3
3
| Được gửi lên bởi: | adm |
| Ngày: | 2017-03-31 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
