主席树算贡献l,r中交换位置，算出>=rank(h) 和 <=rank(h) a[l],a[r] 先不统计 a[l]比a[r]大的话交换后ans-1，a[l]比a[r]小的话交换后ans-1，ans+<r的，->r的 ans-<l的，+>l的，区间比k大的数量或者区间第k大等类似的可以用第二类主席树弄
#include <cstdio>
#include <memory>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <cassert>
#include <string>
#include <ctime>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <set>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define req(i,a,b) for(int i=a;i>=b;i--)
#define rp(i,a) for(int i=head[a];i+1;i=edge[i].next)
#define cl(a,b) memset(a,b,sizeof a);
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mod 10007
const int inf = ~0u >> 2;
const ll INF = (1LL << 62) - 1;
double eps = 1e-12;
const int N = 500005 + 5;
const int M = 200005;
int n, m, d;
int a[500005];
int rnk[N];
int root[N];
int croot[N];
int sz = 0, tot = 0;
void insert(int &num, int val, int k, int l, int r);
struct Node {
int sum;
int ch[2];
}T[30500010];
void insert(int &num, int val, int k, int l, int r, int flag) {
if (flag == 0 || num == 0) {
T[++sz] = T[num]; num = sz;
}
T[num].sum += val;
if (l == r) {
return;
}
int m = (l + r) >> 1;
if (k <= m) {
insert(T[num].ch[0], val, k, l, m, flag);
}
else {
insert(T[num].ch[1], val, k, m + 1, r, flag);
}
}
int query(int i, int j, int k, int l, int r) {
if (k > T[j].sum - T[i].sum)
k = T[i].sum - T[i].sum;
if (l == r)
return l;
int m = (l + r) >> 1;
if (k <= T[T[j].ch[0]].sum - T[T[i].ch[0]].sum)
return query(T[i].ch[0], T[j].ch[0], k, l, m);
else
return query(T[i].ch[1], T[j].ch[1], k - (T[T[j].ch[0]].sum - T[T[i].ch[0]].sum), m + 1, r);
}
void add(int x, int num, int d) {
while (x <= tot) {
insert(croot[x], d, num, 1, tot, 1);
x += x&-x;
}
}
struct Pack {
vector<int> v;
Pack() {}
Pack(int x) { v.push_back(x); }
void operator +=(int x) {
v.push_back(x);
}
operator ll()const {//得到左孩子和
ll ret = 0;
for (int i = 0; i<v.size(); i++)
ret += T[T[v[i]].ch[0]].sum;
return ret;
}
void lt() {
for (int i = 0; i < v.size(); i++)
v[i] = T[v[i]].ch[0];
}
void rt() {
for (int i = 0; i < v.size(); i++)
v[i] = T[v[i]].ch[1];
}
};
Pack sum(int x, int k) {
Pack ret;
while (x>0) {
ret += croot[x];
x -= x&-x;
}
return ret;
}
ll binSearch(int l, int r, int k) {
Pack treesl = sum(l,0);
Pack treesr = sum(r,0);
Pack presl = Pack(root[l]);
Pack presr = Pack(root[r]);
int xl = 1, xr = tot;
ll ret = 0;
int rtl = root[l];
int rtr = root[r];
while (xl < xr) {
int mid = (xl + xr) >> 1;
ll t = treesr - treesl + presr - presl;
if (mid <= k) {
ret += t;
treesr.rt(); treesl.rt(); presr.rt(); presl.rt();
//ret += T[T[rtr].ch[0]].sum - T[T[rtl].ch[0]].sum;
xl = mid+1;
if (mid == k) {
ret--;
break;
}
}
else {
treesr.lt(); treesl.lt(); presr.lt(); presl.lt();
xr = mid;
}
}
return ret;
}
struct Seg {
int l, r, h, x;
}q[M];
int val[N];
int cnt = 0;
int Hash(int x) {
return lower_bound(val, val + tot, x) - val + 1;
}
int b[N];
int main() {
//for (int i = 0; i <= sz; i++)T[i] = T[0];
cnt = 0;
sz = 0;
tot = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
a[i] = i;
b[i] = i;
val[cnt++] = a[i];
}
for (int i = 0; i < m; i++) {
int x, y;
scanf("%d%d", &x, &y);
if (x > y)
swap(x, y);
q[i * 4].l = x;
q[i * 4].r = y;
q[i * 4].h = b[y];
q[i * 4].x = -1;
q[i * 4 + 1].l = x;
q[i * 4 + 1].r = y;
q[i * 4 + 1].h = b[x];
q[i * 4 + 1].x = -2;
q[i*4+2].x = x;
q[i*4+2].h = b[y];
//val[cnt++] = b[y];
q[i*4+2].l = -inf;
q[i * 4+3].x = y;
q[i * 4+3].h = b[x];
//val[cnt++] = b[x];
q[i * 4+3].l = -inf;
swap(b[x], b[y]);
/*if (l<1 || r>n || l>r || h<1 || h>r - l + 1)
assert(false);*/
}
sort(val, val + cnt);
rnk[0] = ++tot;
for (int i = 1; i < cnt; i++) {
if (val[i] != val[i - 1])
rnk[i] = ++tot;
else
rnk[i] = tot;
}
for (int i = 0; i <= tot; i++)croot[i] = 0;
unique(val, val + cnt);
root[0] = 0;
for (int i = 1; i <= n; i++) {
root[i] = root[i - 1];
insert(root[i], 1, Hash(a[i]), 1, tot, 0);
}
ll ans = 0;
for (int i = 0; i < 4*m; i++) {
if (q[i].l != -inf) {
if (q[i].x == -1) {
if (q[i].l != q[i].r) {
ll tmp = binSearch(q[i].l - 1, q[i].r, Hash(q[i].h));
if (a[q[i].l] < a[q[i].r])
tmp--;
ans += tmp;
ans -= max(0LL, (q[i].r - q[i].l - tmp - 1));
}
//printf("%d
", val[binSearch(q[i].l - 1, q[i].r, q[i].h) - 1]);
}
if (q[i].x == -2) {
if (q[i].l != q[i].r) {
ll tmp = binSearch(q[i].l - 1, q[i].r, Hash(q[i].h));
if (a[q[i].l] > a[q[i].r])
tmp--;
ans -= tmp;
ans += max(0LL, (q[i].r - q[i].l - tmp - 1));
}
if (a[q[i].l] > a[q[i].r])
ans--;
else if(a[q[i].l]<a[q[i].r])
ans++;
cout << ans << endl;
}
}
else {
add(q[i].x, Hash(a[q[i].x]), -1);
a[q[i].x] = q[i].h;
add(q[i].x, Hash(q[i].h), 1);
}
}
//cout << ans << endl;
/*for (int i = 1; i <= tot; i++)
croot[i] = 0, val[i] = 0, a[i] = 0;*/
return 0;
}