传送门
#include <iostream> #include <bits/stdc++.h> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <set> #include <queue> #include <map> #include <deque> #include <cstdlib> #define lowbit(x) ((x) & -(x)) #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 const int maxn = 2e6 + 7; const int INF = 0x3f3f3f3f; typedef long long ll; using namespace std; const ll mod = 1e9 + 7; const double pi = acos(-1.0); inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if (ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = (x<<1) + (x<<3) + (ch^48); ch = getchar(); } return x * f; } struct node{ int l, r, id; }Q[maxn]; int block[maxn]; int a[maxn]; bool cmp(node a, node b){ if (block[a.l] != block[b.l]) return a.r < b.r; return a.l < b.l; } int main(){ ios::sync_with_stdio(false); // freopen("text.txt","r",stdin); // freopen("out1.txt","w",stdout); int t, n, q; cin >> t; while(t --){ cin >> n >> q; int sz = sqrt(n); for (int i = 1; i <= n; i ++) block[i] = (i - 1) / sz + 1; for (int i = 0; i < q; i ++){ cin >> Q[i].l >> Q[i].r; Q[i].id = i; } for (int i = 0; i < q; i ++) a[i] = i; int temp = INF; do{ int ans = 0; int l = Q[a[0]].l, r = Q[a[0]].r; for (int i = 1; i < q; i ++){ while(l > Q[a[i]].l) --l, ans ++; while(r < Q[a[i]].r) ++r, ans ++; while(l < Q[a[i]].l) l ++, ans ++; while(r > Q[a[i]].r) r --, ans ++; } temp = min(ans,temp); }while(next_permutation(a,a+q)); cout << temp << endl; } return 0; }题目以莫队算法为背景，但如果直接是莫队的话，会错误。鉴于q较小，直接全排列加莫队即可。
