2038: [2009国家集训队]小Z的袜子(hose) 莫队算法

题目链接：点击打开链接

先把询问处理成曼哈顿最小生成树。

然后在树上暴力跑即可。

能使用莫队的情况应该是对于询问[l,r] -> [l’, r’] 花费必须是 abs(l-l’) + abs(r-r’)

#include <stdio.h>#include <iostream>#include <algorithm>#include <sstream>#include <stdlib.h>#include <string.h>#include <limits.h>#include <vector>#include <string>#include <time.h>#include <math.h>#include <iomanip>#include <queue>#include <stack>#include <set>#include <map>const int inf = 1e9;const double eps = 1e-8;const double pi = acos(-1.0);template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) { putchar('-'); x = -x; }if (x>9) pt(x / 10);putchar(x % 10 + '0');}using namespace std;const int N = 1e5 + 10;typedef long long ll;ll gcd(ll x, ll y){if (x > y)swap(x, y);while (x)y %= x, swap(x, y);return y;}vector<int>G[N];class MST{struct Edge{int from, to, dis;Edge(int _from = 0, int _to = 0, int _dis = 0) :from(_from), to(_to), dis(_dis){}bool operator < (const Edge &x) const{return dis < x.dis;}}edge[N << 3];int f[N], tot;int find(int x){ return x == f[x] ? x : f[x] = find(f[x]); }bool Union(int x, int y){x = find(x); y = find(y);if (x == y)return false;if (x > y)swap(x, y);f[x] = y;return true;}public:void init(int n){for (int i = 0; i <= n; i++)f[i] = i;tot = 0;}void add(int u, int v, int dis){edge[tot++] = Edge(u, v, dis);}ll work(){//计算最小生成树，，返回花费sort(edge, edge + tot);ll cost = 0;for (int i = 0; i < tot; i++)if (Union(edge[i].from, edge[i].to)){cost += edge[i].dis;G[edge[i].from].push_back(edge[i].to);G[edge[i].to].push_back(edge[i].from);}return cost;}}mst;struct Point{//二维平面的点int x, y, id;bool operator < (const Point&a) const{return x == a.x ? y < a.y : x < a.x;}}p[N];bool cmp_id(const Point&a, const Point&b){return a.id < b.id;}class BIT{//树状数组int c[N], id[N], maxn;int lowbit(int x){ return x&-x; }public:void init(int n){maxn = n + 10;fill(c, c + maxn + 1, inf);fill(id, id + maxn + 1, -1);}void updata(int x, int val, int _id){while (x){if (val < c[x]){ c[x] = val; id[x] = _id; }x -= lowbit(x);}}int query(int x){int val = inf, _id = -1;while (x <= maxn){if (val > c[x]){ val = c[x]; _id = id[x]; }x += lowbit(x);}return _id;}}tree;inline bool cmp(int *x, int *y){ return *x < *y; }class Manhattan_MST{int A[N], B[N];public:ll work(int l, int r){mst.init(r);for (int dir = 1; dir <= 4; dir++){if (dir%2==0)for (int i = l; i <= r; i++)swap(p[i].x, p[i].y);else if (dir == 3)for (int i = l; i <= r; i++)p[i].y = -p[i].y;sort(p + l, p + r + 1);for (int i = l; i <= r; i++) A[i] = B[i] = p[i].y – p[i].x; //离散化sort(B + 1, B + N + 1);int sz = unique(B + 1, B + N + 1) – B – 1;//初始化反树状数组tree.init(sz);for (int i = r; i >= l; i–){int pos = lower_bound(B + 1, B + sz + 1, A[i]) – B;int id = tree.query(pos);if (id != -1)mst.add(p[i].id, p[id].id, abs(p[i].x – p[id].x) + abs(p[i].y – p[id].y));tree.updata(pos, p[i].x + p[i].y, i);}}for (int i = l; i <= r; i++)p[i].y = -p[i].y;return mst.work();}}m_mst;ll up[N], now;int l[N], r[N];int n, query, col[N], siz[N];void add(int x, int y){for (int i = x; i <= y; i++){now += siz[col[i]];siz[col[i]]++;}}void del(int x, int y){for (int i = x; i <= y; i++){now -= siz[col[i]] – 1;siz[col[i]]–;}}void dfs(int u, int fa){if (fa == -1)add(l[u], r[u]);else{if (l[u] < l[fa]) add(l[u], l[fa] – 1);if (r[u] > r[fa]) add(r[fa] + 1, r[u]);if (l[u] > l[fa]) del(l[fa], l[u] – 1);if (r[u] < r[fa]) del(r[u] + 1, r[fa]);}up[u] = now;for (int i = 0; i < G[u].size(); i++)if (G[u][i] != fa)dfs(G[u][i], u);if (fa != -1){if (l[u] < l[fa]) del(l[u], l[fa] – 1);if (r[u] > r[fa]) del(r[fa] + 1, r[u]);if (l[u] > l[fa]) add(l[fa], l[u] – 1);if (r[u] < r[fa]) add(r[u] + 1, r[fa]);}}int main(){while (cin >> n >> query){for (int i = 1; i <= n; i++)rd(col[i]);for (int i = 1; i <= query; i++){rd(l[i]), rd(r[i]);p[i].x = l[i]; p[i].y = r[i]; p[i].id = i;}for (int i = 1; i <= query; i++)G[i].clear();m_mst.work(1, query);now = 0;memset(siz, 0, sizeof siz);dfs(1, -1);for (int i = 1; i <= query; i++){ll down = (ll)(r[i] – l[i] + 1)*(r[i] – l[i]) / 2;ll g = gcd(up[i], down);pt(up[i] / g); putchar('/'); pt(down / g); putchar('\n');}}return 0;}

若不给自己设限，则人生中就没有限制你发挥的藩篱。