动态逆序对

#include <set>
#include <cstring>
#include <iostream>
#include <map>
#define lowbit(x) ((x)&-(x))
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
u32 n, T, u, v, a[100005], ans1;
u64 ans, val[100005], sumval[100005], ans2;
#define P 12108863
#define A 4376135492512386ull
#define B 295623ull
u32 pool1[(size_t)(P * 1.2)];
u64 pool2[(size_t)(P * 1.2)];
u64 X[(size_t)(P * 1.2)];
u32 bit1[100005];
u64 bit2[100005];
inline u64 query2(u32 x) {
	u64 ans = 0;
	while (x) {
		ans += bit2[x];
		x ^= lowbit(x);
	}
	return ans;
}
inline void update2(u32 x, u64 k) {
	while (x <= n) {
		bit2[x] += k;
		x += lowbit(x);
	}
}
inline void query(u32 x, u32 y) {
	// i<=x, j<=y
	ans1 = 0;
	ans2 = 0;
	while (x) {
		for (u32 i = y; i; i ^= lowbit(i)) {
			u32 k = (x * A ^ i * B) % P;
			u64 k2 = x ^ u64(i) << 20;
			while (X[k] && (X[k] ^ k2)) {
				k++;
			}
			ans1 += pool1[k];
			ans2 += pool2[k];
		}
		x ^= lowbit(x);
	}
}
inline void update(u32 x, u32 y, u32 K1, u64 K2) {
	// i<=x, j<=y, +=K1, +=K2
	while (x <= n) {
		for (u32 i = y; i <= n; i += lowbit(i)) {
			u32 k = (x * A ^ i * B) % P;
			u64 k2 = x ^ u64(i) << 20;
			while (X[k] && (X[k] ^ k2)) {
				k++;
			}
			X[k] = k2;
			pool1[k] += K1;
			pool2[k] += K2;
		}
		x += lowbit(x);
	}
}
signed main() {
	scanf("%u%u", &n, &T);
	for (u32 i = 1; i <= n; i++) {
		scanf("%u%llu", a + i, val + i);
		sumval[i] = sumval[i - 1] + val[i];
	}
	for (u32 i = 1; i <= n; i++) {
		u32 invcnt = i - 1;
		ans += sumval[i - 1];
		for (u32 j = a[i]; j; j ^= lowbit(j)) {
			invcnt -= bit1[j];
			ans -= bit2[j];
		}
		ans += val[i] * invcnt;
		for (u32 j = a[i]; j <= n; j += lowbit(j)) {
			bit1[j]++;
			bit2[j] += val[i];
		}
		update(i, a[i], 1, val[i]);
	}
	memset(bit2 + 1, 0, sizeof(bit2[0]) * n);
	for (u32 i = 1; i <= n; i++)
	{
		bit2[i] += val[i];
		bit2[i + lowbit(i)] += bit2[i];
	}
	while (T--) {
		scanf("%u%u", &u, &v);
		if (u > v) {
			swap(u, v);
		}
		if (u == v) {
			printf("%llu\n", ans % 1000000007ull);
			continue;
		}
		if (a[u] < a[v]) {
			ans += val[u] + val[v];
		} else {
			ans -= val[u] + val[v];
		}
		if (u + 1 == v) {
			update(u, a[u], -1, -val[u]);
			update(v, a[v], -1, -val[v]);
			update2(u, -val[u]);
			update2(v, -val[v]);
			swap(a[u], a[v]);
			swap(val[u], val[v]);
			update(u, a[u], 1, val[u]);
			update(v, a[v], 1, val[v]);
			update2(u, val[u]);
			update2(v, val[v]);
			printf("%llu\n", ans % 1000000007ull);
			continue;
		}
		u32 tot_cnt = v - u - 1;
		u64 tot_sum = query2(v - 1) - query2(u);
		update(u, a[u], -1, -val[u]);
		update(v, a[v], -1, -val[v]);
		update2(u, -val[u]);
		update2(v, -val[v]);
		query(v, max(a[u], a[v]));
		u32 vmax_cnt = ans1;
		u64 vmax_sum = ans2;
		query(v, min(a[u], a[v]));
		u32 vmin_cnt = ans1;
		u64 vmin_sum = ans2;
		query(u, max(a[u], a[v]));
		u32 umax_cnt = ans1;
		u64 umax_sum = ans2;
		query(u, min(a[u], a[v]));
		u32 umin_cnt = ans1;
		u64 umin_sum = ans2;
		u32 up_cnt = tot_cnt - vmax_cnt + umax_cnt;
		u64 up_sum = tot_sum - vmax_sum + umax_sum;
		u32 down_cnt = vmin_cnt - umin_cnt;
		u64 down_sum = vmin_sum - umin_sum;
		u32 mid_cnt = tot_cnt - up_cnt - down_cnt;
		u64 mid_sum = tot_sum - up_sum - down_sum;
		if (val[u] > val[v]) {
			ans += (val[u] - val[v]) * up_cnt;
			ans -= (val[u] - val[v]) * down_cnt;
		} else {
			ans -= (val[v] - val[u]) * up_cnt;
			ans += (val[v] - val[u]) * down_cnt;
		}
		if (a[u] < a[v]) {
			ans += mid_sum << 1;
			ans += mid_cnt * (val[u] + val[v]);
		} else {
			ans -= mid_sum << 1;
			ans -= mid_cnt * (val[u] + val[v]);
		}
		swap(a[u], a[v]);
		swap(val[u], val[v]);
		update(u, a[u], 1, val[u]);
		update(v, a[v], 1, val[v]);
		update2(u, val[u]);
		update2(v, val[v]);
		printf("%llu\n", ans % 1000000007ull);
	}
	return 0;
}