题意：给n个数，m个询问。每个询问是一个区间，求区间内差的绝对值为1的数对数。
题解：先离散化，然后莫队算法。莫队是离线算法，先按按询问左端点排序，在按右端点排序。
ps：第一次写莫队，表示挺简单的，不过这题之前乱搞一气一直TLE，莫队还是很强大的。
代码：
#include <algorithm> #include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; typedef long long ll; struct Node { int val; int pos; bool operator < (const Node x) const { return val < x.val; } } a[10005]; int b[10005], c[10005]; int tmp[30000]; ll so[100005]; struct query { int l, r, id; bool operator < (const query x) const { if (l == x.l) return r < x.r; return l < x.l; } } q[100005]; int update(int x, int d) { int ans = d * ((tmp[x+1] + tmp[x-1])); if (d < 0) tmp[x]--; else tmp[x]++; return ans; } // 我好菜啊 int main() { //freopen("in.txt", "r", stdin); int n, m; while (~scanf("%d%d", &n, &m)) { for (int i = 1; i <= n; ++i) { scanf("%d", &a[i].val); a[i].pos = i; } sort(a+1, a+1+n); b[1] = 1;for (int i = 2; i <= n; ++i) { if (a[i].val == a[i-1].val) b[i] = b[i-1]; else if (a[i].val == a[i-1].val + 1) b[i] = b[i-1]+1; else b[i] = b[i-1] + 2; } for (int i = 1; i <= n; ++i) { c[ a[i].pos ] = b[i]; } memset(tmp, 0, sizeof tmp); for (int i = 0; i < m; ++i) { scanf("%d%d", &q[i].l,&q[i].r); q[i].id = i; } sort(q, q+m); int pl = 1, pr = 0; ll ans = 0; for (int i = 0; i < m; ++i) { int id = q[i].id; int l = q[i].l; int r = q[i].r; if (pr < r) for (int i = pr+1; i <= r; ++i) ans += update(c[i], 1); else for (int i = pr; i > r; --i) ans += update(c[i], -1); if (pl < l) for (int i = pl; i < l; ++i) ans += update(c[i], -1); pr = r, pl = l; so[id] = ans; } for (int i = 0; i < m; ++i) printf("%lld ", so[i]); } return 0; }