#include <cstdio> #include <vector> #include <cmath> #include <algorithm> using std::vector; inline int read() { int x = 0; short f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return x * f; } typedef unsigned int ll; const int N = 5e5 + 10, B = 18; int n, m, Q, k, p[N]; ll ans[N]; vector<int> e[N]; struct edg { int u, v; } g[N]; struct qry { int l, r, idx; } q[N]; namespace SUB1 { ll c[N]; struct zzn { int y, idx; bool op; }; vector<zzn> v[N]; inline void add(int x) { for (; x <= n; x += x & -x) c[x] = -~c[x]; } inline ll ask(int x) { ll s = 0; for (; x; x -= x & -x) s += c[x]; return s; } inline void Main() { for (int i = 1; i <= Q; i = -~i) { v[q[i].r].push_back({ q[i].r, i, 1 }); v[q[i].r].push_back({ q[i].l - 1, i, 0 }); v[q[i].l - 1].push_back({ q[i].r, i, 0 }); v[q[i].l - 1].push_back({ q[i].l - 1, i, 1 }); } for (int i = 1; i <= n; i = -~i) { for (int &j : e[i]) add(j); for (auto &[y, idx, op] : v[i]) { // printf("ask(%d,%d)=%d\n",i,y,ask(y)); if (op) ans[idx] += ask(y); else ans[idx] -= ask(y); } } } } // namespace SUB1 int l[N], r[N], a[N], tot, len; bool cmpp(const qry &x, const qry &y) { if (x.l / len != y.l / len) return x.l < y.l; return (x.l / len & 1) ? x.r < y.r : x.r > y.r; } namespace SUB2 { int cnt[N]; ll now; inline void insert(int x) { now += cnt[x] + (++cnt[x]); } inline void erase(int x) { now -= cnt[x] + (--cnt[x]); } inline void Main() { for (int i = 1, l = q[1].l, r = q[1].l - 1; i <= Q; i = -~i) { // printf("solve(%d,%d,%d)\n",q[i].l,q[i].r,q[i].idx); while (r < q[i].r) insert(a[++r]); while (l > q[i].l) insert(a[--l]); while (r > q[i].r) erase(a[r--]); while (l < q[i].l) erase(a[l++]); // printf("now=%d\n",now); ans[q[i].idx] = now; } } } // namespace SUB2 namespace SUB3 { vector<int> v[N]; int w[N], _w[N]; ll f[N], res[N], now; vector<qry> s[N]; inline void Main() { for (int i = 1; i <= n; i = -~i) for (int j : e[i]) if (e[j].size() > B) v[i].push_back(j); for (int i = 1, l = q[1].l, r = q[1].l - 1, tot = 0; i <= Q; i = -~i) { if (r < q[i].r) s[l - 1].push_back({ r + 1, q[i].r, tot = -~tot }), r = q[i].r; if (l > q[i].l) s[r].push_back({ q[i].l, l - 1, tot = -~tot }), l = q[i].l; if (r > q[i].r) s[l - 1].push_back({ q[i].r + 1, r, tot = -~tot }), r = q[i].r; if (l < q[i].l) s[r].push_back({ l, q[i].l - 1, tot = -~tot }), l = q[i].l; } for (int i = 1; i <= tot; i = -~i) { if (e[a[i]].size() <= B) for (int j : e[a[i]]) f[i] += w[j]; else f[i] = _w[a[i]]; //邻域加，单点查，考虑根号分治 w[a[i]] = -~w[a[i]]; //小于 B 的打标记，查的时候暴力扫邻域 for (int j : v[a[i]]) _w[j] = -~_w[j]; //大于 B 的更新的时候暴力更新 // printf("f[%d] = %d\n",i,f[i]); for (auto &[l, r, idx] : s[i]) { for (int j = l; j <= r; j = -~j) { if (e[a[j]].size() <= B) for (int k : e[a[j]]) res[idx] += w[k]; else res[idx] += _w[a[j]]; } // printf("res[(%d,%d,%d)]=%u\n",l,r,idx,res[idx]); } } for (int i = 1; i <= tot; i = -~i) f[i] += f[i - 1]; for (int i = 1, l = q[1].l, r = q[1].l - 1, tot = 0; i <= Q; i = -~i) { // printf("solve(%d,%d,%d)\n",q[i].l,q[i].r,q[i].idx); if (r < q[i].r) // printf("r: %d -> %d, now+= //%d\n",r,q[i].r,f[q[i].r]-f[r]-res[tot=-~tot]), now += f[q[i].r] - f[r] - res[tot = -~tot], r = q[i].r; if (l > q[i].l) now += res[tot = -~tot] - f[l - 1] + f[q[i].l - 1], l = q[i].l; if (r > q[i].r) now -= f[r] - f[q[i].r] - res[tot = -~tot], r = q[i].r; if (l < q[i].l) now -= res[tot = -~tot] - f[q[i].l - 1] + f[l - 1], l = q[i].l; ans[q[i].idx] = now << 1; } } } // namespace SUB3 signed main() { //freopen("path.in","r",stdin); //freopen("path.out","w",stdout); n = read(); m = read(); Q = read(); k = read(); for (int i = 1; i <= m; i = -~i) g[i] = { read(), read() }; for (int i = 1; i <= n; i = -~i) p[read()] = i; for (int i = 1; i <= m; i = -~i) e[p[g[i].u]].push_back(p[g[i].v]), e[p[g[i].v]].push_back(p[g[i].u]); for (int i = 1; i <= Q; i = -~i) q[i] = { read(), read(), i }; if (k == 2) SUB1::Main(); // k=2，数点，扫描线特殊处理 else //否则转化为邻域序列上的DS问题 { for (int i = 1; i <= n; i = -~i) { l[i] = r[i - 1] + 1; r[i] = r[i - 1] + e[i].size(); for (int j : e[i]) a[tot = -~tot] = j; } // for(int i=1;i<=tot;i=-~i) printf("%d ",a[i]);putchar('\n'); for (int i = 1; i <= Q; i = -~i) q[i] = { l[q[i].l], r[q[i].r], i }; // for(int i=1;i<=Q;i=-~i) printf("%d %d\n",q[i].l,q[i].r); len = tot / sqrt(Q * 1.0) + 1; std::sort(q + 1, q + Q + 1, cmpp); } if (k == 3) SUB2::Main(); if (k == 4) SUB3::Main(); for (int i = 1; i <= Q; i = -~i) printf("%u\n", ans[i]); return 0; } /* 4 5 3 4 1 3 2 1 3 4 1 4 3 2 2 1 4 3 2 4 1 3 1 2 */