In this HackerRank Counting On a Tree problem, we have given t and q queries, process each query in order, printing the pair count for each query on a new line.
Problem solution in Java Programming.
import java.io.*;
import java.util.*;
public class Solution {
static int[] nxt;
static int[] succ;
static int[] ptr;
static int index = 1;
static void addEdge(int u, int v) {
nxt[index] = ptr[u];
ptr[u] = index;
succ[index++] = v;
}
static int timer = 0;
static int[] tin;
static int[] tout;
static int[] pr;
static int[][] up;
static int[] w;
static class NodeDfs {
int v;
int lvl;
int p;
boolean start = true;
public NodeDfs(int v, int lvl, int p) {
this.v = v;
this.lvl = lvl;
this.p = p;
}
}
static void dfs() {
Deque<NodeDfs> q = new LinkedList<>();
q.add(new NodeDfs(1, 0, 1));
while (!q.isEmpty()) {
NodeDfs node = q.peekLast();
if (node.start) {
tin[node.v] = timer;
w[node.v] = node.lvl;
up[node.v][0] = node.p;
for (int i = 1; i <= 17; i++) {
up[node.v][i] = up[up[node.v][i - 1]][i - 1];
}
for (int i = ptr[node.v]; i > 0; i = nxt[i]) {
int to = succ[i];
if (to != node.p) {
q.add(new NodeDfs(to, node.lvl + 1, node.v));
pr[to] = node.v;
}
}
node.start = false;
} else {
tout[node.v] = timer++;
q.removeLast();
}
}
}
static boolean upper(int x, int y) {
return tout[x] >= tout[y] && tin[x] <= tin[y];
}
static int lca(int a, int b) {
if (upper(a, b))
return a;
if (upper(b, a))
return b;
for (int i = 17; i >= 0; --i)
if (!upper(up[a][i], b))
a = up[a][i];
return up[a][0];
}
static void normalize(int[] a) {
Map<Integer, Integer> trans = new HashMap<>();
int j = 0;
for (int i = 1; i < a.length; i++) {
if (!trans.containsKey(a[i])) {
trans.put(a[i], j++);
}
}
for (int i = 1; i < a.length; i++) {
a[i] = trans.get(a[i]);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] a = new int[n + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
normalize(a);
nxt = new int[n + 1];
succ = new int[n + 1];
ptr = new int[n + 1];
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
if (u < v) {
addEdge(u, v);
} else {
addEdge(v, u);
}
}
tin = new int[n + 1];
tout = new int[n + 1];
pr = new int[n + 1];
up = new int[n + 1][20];
w = new int[n + 1];
dfs();
int[] d = new int[m];
int[] X1 = new int[m];
int[] Y1 = new int[m];
int[] X2 = new int[m];
int[] Y2 = new int[m];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
X1[i] = x1;
Y1[i] = y1;
X2[i] = x2;
Y2[i] = y2;
int lc1 = lca(x1, y1);
int lc2 = lca(x2, y2);
int ans1 = 0;
if (lc1 == lc2) {
int lc3 = lca(x1, x2);
int lc4 = lca(x1, y2);
int lc5 = lca(y1, x2);
int lc6 = lca(y1, y2);
ans1++;
ans1 += w[lc3] - w[lc1];
ans1 += w[lc4] - w[lc1];
ans1 += w[lc5] - w[lc1];
ans1 += w[lc6] - w[lc1];
} else if (w[lc1] < w[lc2]) {
int lc3 = lca(x1, x2);
int lc4 = lca(x1, y2);
int lc5 = lca(y1, x2);
int lc6 = lca(y1, y2);
if (upper(lc2, x1) && upper(lc1, lc2)) {
ans1 += Math.abs(w[lc3] - w[lc4]) + 1;
}
if (upper(lc2, y1) && upper(lc1, lc2)) {
ans1 += Math.abs(w[lc5] - w[lc6]) + 1;
}
} else if (w[lc1] > w[lc2]) {
int lc3 = lca(x1, x2);
int lc4 = lca(x1, y2);
int lc5 = lca(y1, x2);
int lc6 = lca(y1, y2);
if (upper(lc1, x2) && upper(lc2, lc1)) {
ans1 += Math.abs(w[lc3] - w[lc5]) + 1;
}
if (upper(lc1, y2) && upper(lc2, lc1)) {
ans1 += Math.abs(w[lc4] - w[lc6]) + 1;
}
}
d[i] = ans1;
}
int[] b = new int[n + 1];
for (int i = 0; i < m; i++) {
int x1 = X1[i];
int y1 = Y1[i];
int x2 = X2[i];
int y2 = Y2[i];
int x3 = x1;
int y3 = y1;
while (!upper(x1, y1)) {
++b[a[x1]];
x1 = pr[x1];
}
while (y1 != x1) {
++b[a[y1]];
y1 = pr[y1];
}
b[a[x1]]++;
int ans = 0;
while (!upper(x2, y2)) {
ans += b[a[x2]];
x2 = pr[x2];
}
while (y2 != x2) {
ans += b[a[y2]];
y2 = pr[y2];
}
ans += b[a[x2]];
int tmp = x1;
x1 = x3;
y1 = y3;
while (x1 != tmp) {
b[a[x1]] = 0;
x1 = pr[x1];
}
while (y1 != tmp) {
b[a[y1]] = 0;
y1 = pr[y1];
}
b[a[x1]] = 0;
bw.write((ans - d[i]) + "n");
}
bw.newLine();
bw.close();
br.close();
}
}
Problem solution in C++14 programming.
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define SIZE(x) (int((x).size()))
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define repd(i,r,l) for (int i=(r); i>=(l); i--)
#define rept(i,c) for (__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#ifndef ONLINE_JUDGE
#define debug(x) { cerr<<#x<<" = "<<(x)<<endl; }
#else
#define debug(x) {}
#endif
#define maxn 100010
#define LIM 100
int ta[maxn];
void ta_modify(int x, int y)
{
while (x<maxn) ta[x]+=y, x+=x&-x;
}
int ta_query(int x)
{
int ret=0;
while (x) ret+=ta[x], x-=x&-x;
return ret;
}
void ds_modify(int l, int r, int c)
{
ta_modify(l,c);
ta_modify(r+1,-c);
}
int ds_query(int v)
{
return ta_query(v);
}
int dfsN;
int dfsLeft[maxn], dfsRight[maxn];
int lg2[maxn], p[maxn][17], depth[maxn];
vector<int> e[maxn];
void dfs(int cur, int pre, int dep)
{
dfsN++; dfsLeft[cur]=dfsN;
depth[cur]=dep;
p[cur][0]=pre;
rep(i,1,lg2[dep]) p[cur][i]=p[p[cur][i-1]][i-1];
rept(it,e[cur]) if (*it!=pre) dfs(*it,cur,dep+1);
dfsRight[cur]=dfsN;
}
int movedep(int x, int y)
{
if (y<0) return 0;
while (y) x=p[x][lg2[y&-y]], y-=y&-y;
return x;
}
int lca(int x, int y)
{
if (depth[x]<depth[y]) swap(x,y);
x=movedep(x,depth[x]-depth[y]);
repd(i,16,0)
if (p[x][i]!=p[y][i])
{
x=p[x][i]; y=p[y][i];
}
if (x==y) return x;
return p[x][0];
}
int get_dist(int x, int y)
{
int z=lca(x,y);
return depth[x]+depth[y]-2*depth[z]+1;
}
int all, ti[5][2];
void check_intersect(int p1, int p2, int q1, int q2)
{
if (depth[p2]>depth[q2])
{
swap(p1,q1); swap(p2,q2);
}
if (depth[p1]<depth[q2]) return;
if (lca(p1,q2)!=q2 || lca(q2,p2)!=p2) return;
int z=lca(p1,q1);
rep(i,1,all) if (ti[i][0]==z && ti[i][1]==q2) return;
rep(i,1,all) if (ti[i][1]==z && ti[i][0]==q2) return;
//if (z==q2) rep(i,1,all) if (ti[i][0]==z || ti[i][1]==z) return;
all++; ti[all][0]=z; ti[all][1]=q2;
}
struct tasktype
{
int x, y, c;
tasktype() {}
tasktype(int x, int y, int c): x(x), y(y), c(c) {}
};
vector<tasktype> eventAddList[maxn], eventQueryList[maxn];
void addQueryEvent(int i, int p1, int q1, int c)
{
p1=dfsLeft[p1]; q1=dfsLeft[q1];
eventQueryList[p1].push_back(tasktype(q1,i,c));
}
void addContributionEvent(int p1, int p2, int q1, int q2)
{
eventAddList[p1].push_back(tasktype(q1,q2,1));
eventAddList[p2+1].push_back(tasktype(q1,q2,-1));
}
void add_task(int i, int p1, int p2, int q1, int q2)
{
if (!p1 || !p2 || !q1 || !q2) return;
addQueryEvent(i,p1,q1,1);
if (p[q2][0]) addQueryEvent(i,p1,p[q2][0],-1);
if (p[p2][0]) addQueryEvent(i,p[p2][0],q1,-1);
if (p[p2][0] && p[q2][0]) addQueryEvent(i,p[p2][0],p[q2][0],1);
}
map<int, vector<int> > clist;
int color[maxn];
int q[maxn][6];
int ans[maxn];
void lemon()
{
lg2[1]=0; rep(i,2,maxn-1) lg2[i]=lg2[i>>1]+1;
int n,qa; scanf("%d%d",&n,&qa);
rep(i,1,n)
{
scanf("%d",&color[i]);
clist[color[i]].push_back(i);
}
rep(i,1,n-1)
{
int x,y; scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
rep(i,1,qa)
{
scanf("%d%d%d%d",&q[i][0],&q[i][1],&q[i][2],&q[i][3]);
}
dfsN=0;
dfs(1,0,0);
rep(i,1,qa) ans[i]=0;
rep(i,1,qa)
{
all=0;
int z1=lca(q[i][0],q[i][1]);
int z2=lca(q[i][2],q[i][3]);
q[i][4]=z1; q[i][5]=z2;
check_intersect(q[i][0],z1,q[i][2],z2);
check_intersect(q[i][0],z1,q[i][3],z2);
check_intersect(q[i][1],z1,q[i][2],z2);
check_intersect(q[i][1],z1,q[i][3],z2);
int t1=movedep(q[i][1],depth[q[i][1]]-depth[z1]-1);
int t2=movedep(q[i][3],depth[q[i][3]]-depth[z2]-1);
add_task(i,q[i][0],z1,q[i][2],z2);
add_task(i,q[i][0],z1,q[i][3],t2);
add_task(i,q[i][1],t1,q[i][2],z2);
add_task(i,q[i][1],t1,q[i][3],t2);
if (all>0)
{
rep(k,1,all)
ans[i]-=get_dist(ti[k][0],ti[k][1]);
ans[i]+=all-1;
}
}
rept(it,clist)
{
int cl=it->first;
if (it->second.size()<=LIM)
{
int s=it->second.size();
rep(i,0,s-1)
rep(j,0,s-1)
{
int i1=it->second[i], j1=it->second[j];
addContributionEvent(dfsLeft[i1], dfsRight[i1], dfsLeft[j1], dfsRight[j1]);
}
}
else
{
rept(it2,it->second)
ds_modify(dfsLeft[*it2],dfsRight[*it2],1);
rep(i,1,qa)
{
int x1=ds_query(dfsLeft[q[i][0]])+ds_query(dfsLeft[q[i][1]])-2*ds_query(dfsLeft[q[i][4]]);
if (color[q[i][4]]==cl) x1++;
//printf("%d: %d %d %dn",cl,q[i][0],q[i][1],x1);
int x2=ds_query(dfsLeft[q[i][2]])+ds_query(dfsLeft[q[i][3]])-2*ds_query(dfsLeft[q[i][5]]);
if (color[q[i][5]]==cl) x2++;
//printf("%d: %d %d %dn",cl,q[i][2],q[i][3],x2);
ans[i]+=x1*x2;
}
rept(it2,it->second)
ds_modify(dfsLeft[*it2],dfsRight[*it2],-1);
}
}
rep(i,1,n)
{
rept(it,eventAddList[i]) ds_modify(it->x,it->y,it->c);
rept(it,eventQueryList[i]) ans[it->y]+=it->c*ds_query(it->x);
}
rep(i,1,qa) printf("%dn",ans[i]);
}
int main()
{
ios::sync_with_stdio(true);
#ifndef ONLINE_JUDGE
//freopen("8.in","r",stdin);
#endif
lemon();
return 0;
}
Problem solution in C programming.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define floor_log2_X86(self) (__builtin_clz(self) ^ 31U)
#define floor_log2 floor_log2_X86
void heap_sort(unsigned *self, unsigned *weights, unsigned length) {
unsigned
at = length >> 1,
member,
node;
for (self--; at; self[node >> 1] = member) {
member = self[at];
for (node = at-- << 1; node <= length; node <<= 1) {
node |= (node < length) && (weights[self[node]] < weights[self[node | 1]]);
if (weights[self[node]] < weights[member])
break ;
self[node >> 1] = self[node];
}
}
for (; length > 1; self[at >> 1] = member) {
member = self[length];
self[length--] = self[1];
for (at = 2; at <= length; at <<= 1) {
at |= (at < length) && (weights[self[at]] < weights[self[at | 1]]);
if (weights[self[at]] < weights[member])
break ;
self[at >> 1] = self[at];
}
}
}
void compress(unsigned length, unsigned values[length]) {
unsigned
at,
order[length];
unsigned long sum = 0x0000000100000000UL;
for (at = 0; at < (length >> 1); sum += 0x0000000200000002UL)
((unsigned long *)order)[at++] = sum;
order[length - 1] = length - 1;
heap_sort(order, values, length);
unsigned roots[length], seen = 1, max = 0, others;
for (roots[at = 0] = -1U; at < length; roots[seen++] = at - 1) {
for (others = at; (at < length) && values[order[at]] == values[order[others]]; at++);
if (max < (at - others))
max = (at - others);
}
unsigned
indices[max + 1],
ranks[seen];
memset(indices, 0, sizeof(indices));
for (at = 0; ++at < seen; indices[roots[at] - roots[at - 1]]++);
for (at = max; at--; indices[at] += indices[at + 1]);
for (at = seen; --at; ranks[--indices[roots[at] - roots[at - 1]]] = at);
for (; at < (seen - 1); at++)
for (others = roots[ranks[at] - 1]; ++others <= roots[ranks[at]]; values[order[others]] = at);
}
static inline unsigned nearest_common_ancestor(
unsigned depth,
unsigned base_cnt,
unsigned vertex_cnt,
unsigned base_ids[vertex_cnt],
unsigned bases[base_cnt][depth],
unsigned char depths[base_cnt],
unsigned weights[vertex_cnt],
unsigned lower,
unsigned upper
) {
if (upper < (lower + weights[lower]))
return lower;
if (depths[upper] > depths[lower])
upper = bases[base_ids[upper]][depths[upper] - depths[lower] - 1];
if (upper < lower)
return upper;
unsigned *others = bases[base_ids[upper]];
for (; depth > 1; depth >>= 1)
if (others[depth >> 1] > lower) {
others += depth >> 1;
depth += depth & 1U;
}
return others[others[0] > lower];
}
typedef union {
unsigned long packd;
struct {
int low, high;
};
} range_t;
typedef struct {
unsigned
*members,
*colors,
*indices,
*locations;
} colored_tree_t;
unsigned long query_all(colored_tree_t *self, unsigned at, range_t other) {
unsigned
color = self->colors[at],
length = self->indices[color + 1] - self->indices[color],
*base = &self->members[self->indices[color]];
if (other.high < base[0] || other.low > base[length - 1])
return 0;
if (self->colors[other.low] != color) {
if (at < other.low) {
base += self->locations[at] - self->indices[color];
length = self->indices[color + 1] - self->locations[at];
} else
length = self->locations[at] - self->indices[color]; // at > other.low
for (; length > 1; length >>= 1)
if (base[length >> 1] < other.low) {
base += length >> 1;
length += length & 1;
}
base += (base[0] < other.low);
} else
base += (self->locations[other.low] - self->indices[color]);
if (base[0] > other.high)
return 0;
unsigned *ceil;
if (self->colors[other.high] != color) {
ceil = (at > base[0] && at < other.high) ? &self->members[self->locations[at]] : base;
for (length = self->indices[color + 1] - self->locations[ceil[0]]; length > 1; length >>= 1)
if (ceil[length >> 1] <= other.high) {
ceil += length >> 1;
length += length & 1;
}
ceil -= (ceil[0] > other.high);
} else
ceil = &self->members[self->locations[other.high]];
return ceil - base + 1 - (at >= other.low && at <= other.high);
}
unsigned long count_pairs(
unsigned cnt,
unsigned length,
unsigned long pairs[cnt][cnt],
unsigned *overlapping,
colored_tree_t *tree,
range_t self,
range_t other
) {
unsigned long count = 0;
for (; (self.low % length) && (self.low <= self.high); count += query_all(tree, self.low++, other));
for (; ((self.high + 1) % length) && (self.low <= self.high); count += query_all(tree, self.high--, other));
if (self.low <= self.high) {
for (; (other.low % length) && (other.low <= other.high); count += query_all(tree, other.low++, self));
for (; ((other.high + 1) % length) && (other.low <= other.high); count += query_all(tree, other.high--, self));
if (other.low <= other.high) {
self.low /= length;
self.high /= length;
other.low /= length;
other.high /= length;
if (self.low > other.low) {
self.packd ^= other.packd;
other.packd ^= self.packd;
self.packd ^= other.packd;
}
unsigned high = (self.high < other.low) ? self.high : (other.low - 1);
count +=
pairs[high][other.high]
- pairs[high][other.low - 1UL]
- pairs[self.low - 1UL][other.high]
+ pairs[self.low - 1UL][other.low - 1UL];
self.low = high + 1;
if (self.high > other.high) {
self.packd ^= other.packd;
other.packd ^= self.packd;
self.packd ^= other.packd;
}
if (self.low <= self.high)
count +=
(overlapping[self.high] - overlapping[self.low - 1UL])
+ ((
pairs[self.high][self.high]
- pairs[self.high][self.low - 1UL]
- pairs[self.low - 1UL][self.high]
+ pairs[self.low - 1UL][self.low - 1UL]
) << 1) + (
pairs[self.high][other.high]
- pairs[self.high][self.high]
- pairs[self.low - 1UL][other.high]
+ pairs[self.low - 1UL][self.high]
);
}
}
return count;
}
int main() {
unsigned at, vertex_cnt;
unsigned short query_cnt;
scanf("%u %hu", &vertex_cnt, &query_cnt);
unsigned colors[vertex_cnt + 1];
for (at = 0; at < vertex_cnt; scanf("%u", &colors[at++]));
colors[at] = 0xFFFFFFFFU;
compress(at + 1, colors);
unsigned ancestors[at + 1];
{
unsigned ancestor, descendant;
for (memset(ancestors, 0xFFU, sizeof(ancestors)); --at; ancestors[descendant] = ancestor) {
scanf("%u %u", &ancestor, &descendant);
--ancestor;
if (ancestors[--descendant] != 0xFFFFFFFFU) {
unsigned root = descendant, next;
for (; ancestor != 0xFFFFFFFFU; ancestor = next) {
next = ancestors[ancestor];
ancestors[ancestor] = root;
root = ancestor;
}
for (; ancestors[descendant] != 0xFFFFFFFFU; descendant = next) {
next = ancestors[descendant];
ancestors[descendant] = ancestor;
ancestor = descendant;
}
}
}
for (ancestor = 0xFFFFFFFFU; at != 0xFFFFFFFFU; at = descendant) {
descendant = ancestors[at];
ancestors[at] = ancestor;
ancestor = at;
}
}
unsigned
others,
ids[vertex_cnt + 1],
weights[vertex_cnt],
bases[vertex_cnt + 1],
history[vertex_cnt];
unsigned char
base_depths[vertex_cnt],
dist = 0;
{
unsigned
history[vertex_cnt],
indices[vertex_cnt + 1],
descendants[vertex_cnt];
memset(indices, 0, sizeof(indices));
for (ancestors[vertex_cnt] = (at = vertex_cnt); at; indices[ancestors[at--]]++);
for (; ++at <= vertex_cnt; indices[at] += indices[at - 1]);
for (; --at; descendants[--indices[ancestors[at]]] = at);
history[0] = 0;
memset(weights, 0, sizeof(weights));
for (at = 1; at--; )
if (weights[history[at]])
for (others = indices[history[at]];
others < indices[history[at] + 1];
weights[history[at]] += weights[descendants[others++]]);
else {
weights[history[at]] = 1;
memcpy(
&history[at + 1],
&descendants[indices[history[at]]],
(indices[history[at] + 1] - indices[history[at]]) * sizeof(descendants[0])
);
at += indices[history[at] + 1] - indices[history[at]] + 1;
}
unsigned
orig_ancestors[vertex_cnt + 1],
orig_colors[vertex_cnt + 1],
orig_weights[vertex_cnt];
memcpy(orig_ancestors, ancestors, sizeof(ancestors));
memcpy(orig_weights, weights, sizeof(weights));
memcpy(orig_colors, colors, sizeof(colors));
base_depths[0] = (bases[0] = (ids[0] = 0));
bases[vertex_cnt] = (ids[vertex_cnt] = vertex_cnt);
for (at = 1; at--;) {
unsigned
id = ids[history[at]],
base = bases[id++],
branches = indices[history[at] + 1] - indices[history[at]];
heap_sort(&descendants[indices[history[at]]], orig_weights, branches);
memcpy(&history[at], &descendants[indices[history[at]]], branches * sizeof(descendants[0]));
for (others = (at += branches); branches--; base = id) {
ids[history[--others]] = id;
ancestors[id] = ids[orig_ancestors[history[others]]];
weights[id] = orig_weights[history[others]];
colors[id] = orig_colors[history[others]];
bases[id] = base;
base_depths[id] = base_depths[ancestors[id]] + (base == id);
if (dist < base_depths[id])
dist = base_depths[id];
id += weights[id];
}
}
}
unsigned base_ids[vertex_cnt + 1];
for (base_ids[0] = (others = (at = 0)); others < vertex_cnt; base_ids[others] = base_ids[at] + 1)
for (at = others; bases[at] == bases[others]; base_ids[others++] = base_ids[at]);
unsigned ancestral_bases[base_ids[vertex_cnt]][dist];
for (ancestors[0] = 0; others--; ancestral_bases[base_ids[others]][0] = ancestors[others]);
while ((++others + 1) < dist)
for (at = 0; ++at < base_ids[vertex_cnt];
ancestral_bases[at][others + 1] = ancestors[bases[ancestral_bases[at][others]]]);
unsigned
indexed_colors[colors[vertex_cnt] + 2],
members[vertex_cnt + 1];
memset(indexed_colors, 0, sizeof(indexed_colors));
for (at = vertex_cnt + 1; at--; indexed_colors[colors[at]]++);
for (; ++at < colors[vertex_cnt]; indexed_colors[at + 1] += indexed_colors[at]);
for (at = vertex_cnt + 1; at--; members[--indexed_colors[colors[at]]] = at);
indexed_colors[colors[vertex_cnt] + 1] = indexed_colors[colors[vertex_cnt]];
unsigned
levels = floor_log2(vertex_cnt) + 1,
block_cnt = (vertex_cnt / levels) + 1,
locations[vertex_cnt + 1],
overlapping[block_cnt];
unsigned long (*pairs)[block_cnt][block_cnt] = calloc(
(1 + block_cnt) * (1 + block_cnt),
sizeof(pairs[0][0][0])
);
pairs = (void *)&pairs[0][1][1];
for (at = vertex_cnt + 1; at--; locations[members[at]] = at);
memset(overlapping, 0, sizeof(overlapping));
for (at = 0; (indexed_colors[at + 1] - indexed_colors[at]) > 1; at++) {
others = indexed_colors[at];
unsigned
block_bases[indexed_colors[at + 1] - others + 1],
cnt = 1;
for (block_bases[0] = members[others]; at == colors[members[++others]]; )
if ((members[others] / levels) != (block_bases[cnt - 1] / levels))
block_bases[cnt++] = members[others];
block_bases[cnt] = members[others];
for (others = 0; others < cnt; others++) {
unsigned long density = locations[block_bases[others + 1]] - locations[block_bases[others]];
overlapping[block_bases[others] / levels] += density * (density - 1);
unsigned block = others;
for (; ++block < cnt; pairs[0][block_bases[others] / levels][block_bases[block] / levels]
+= density * (locations[block_bases[block + 1]] - locations[block_bases[block]]));
}
}
for (at = 0; ++at < block_cnt; overlapping[at] += overlapping[at - 1])
pairs[0][0][at] += pairs[0][0][at - 1];
for (at = 0; ++at < block_cnt; )
for (others = 0; ++others < block_cnt; pairs[0][at][others] += pairs[0][at][others - 1]);
for (at = 0; ++at < block_cnt; )
for (others = 0; others < block_cnt; others++)
pairs[0][at][others] += pairs[0][at - 1][others];
colored_tree_t *tree = &(colored_tree_t) {
.members = members,
.colors = colors,
.indices = indexed_colors,
.locations = locations
};
while (query_cnt--) {
range_t left, right;
scanf("%u %u %u %u", &left.low, &left.high, &right.low, &right.high);
left.packd -= 0x0000000100000001UL;
right.packd -= 0x0000000100000001UL;
left.low = ids[left.low];
left.high = ids[left.high];
right.low = ids[right.low];
right.high = ids[right.high];
if (left.high < left.low)
left.packd = (left.packd << 32) | (left.packd >> 32);
if (right.high < right.low)
right.packd = (right.packd << 32) | (right.packd >> 32);
if (right.high < left.low) {
left.packd ^= right.packd;
right.packd ^= left.packd;
left.packd ^= right.packd;
}
struct {
range_t members[32];
unsigned cnt;
}
a = {.cnt = 0},
b = {.cnt = 0};
unsigned common = nearest_common_ancestor(
dist, base_ids[vertex_cnt], vertex_cnt,
base_ids, ancestral_bases,
base_depths, weights,
left.low, left.high
);
for (at = left.low; bases[at] != bases[common]; at = ancestral_bases[base_ids[at]][0])
a.members[a.cnt++].packd = bases[at] | ((unsigned long)at << 32);
for (others = left.high; bases[others] != bases[common]; others = ancestral_bases[base_ids[others]][0])
a.members[a.cnt++].packd = bases[others] | ((unsigned long)others << 32);
a.members[a.cnt++].packd = common | ((unsigned long)((at != common) ? at : others) << 32);
common = nearest_common_ancestor(
dist, base_ids[vertex_cnt], vertex_cnt,
base_ids, ancestral_bases,
base_depths, weights,
right.low, right.high
);
for (at = right.low; bases[at] != bases[common]; at = ancestral_bases[base_ids[at]][0])
b.members[b.cnt++].packd = bases[at] | ((unsigned long)at << 32);
for (others = right.high; bases[others] != bases[common]; others = ancestral_bases[base_ids[others]][0])
b.members[b.cnt++].packd = bases[others] | ((unsigned long)others << 32);
b.members[b.cnt++].packd = common | ((unsigned long)((at != common) ? at : others) << 32);
unsigned long total = 0;
for (at = 0; at < a.cnt; at++)
for (others = 0; others < b.cnt;
total += count_pairs(
block_cnt, levels, pairs[0], overlapping, tree,
a.members[at], b.members[others++]
)
);
printf("%lun", total);
}
return 0;
}