#include <assert.h> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <stdint.h> #define N 200000 #define M (20*N) #define INLINE inline __attribute__((always_inline)) unsigned seed = 0x86868686; INLINE unsigned rand_(void) { return (seed << 3) & 0x3119475; } int n, id, a[N+1], b[N+1], c[N+1]; int A[M], B[M], L[M], R[M], S[M], alloc; int read(void) { int v = ++id; scanf("%d", a+v); if (a[v]) return v; b[v] = read(); c[v] = read(); return v; } INLINE int treap0(int k) { A[++alloc] = k; B[alloc] = rand_(); S[alloc] = 1; return alloc; } INLINE void pull(int v) { S[v] = 1 + S[L[v]] + S[R[v]]; } void split(int v, int *l, int *r, int val) { if (!v) { *l=*r=0; return; } if (A[v] <= val) { split(R[v], &R[v], r, val); *l = v; } else { split(L[v], l, &L[v], val); *r = v; } pull(v); } long long inv, ans; void merge(int *v, int l, int r) { if (!l || !r) { *v = l^r; return; } if (B[l] < B[r]) { int y1, y2; split(l, &y1, &y2, A[r]); inv += 1ll * S[y2] * (1+S[L[r]]); merge(R+r, R[r], y2); merge(L+r, L[r], y1); *v = r; } else { int y1, y2; split(r, &y1, &y2, A[l]); inv += 1ll * S[y1] * (1+S[R[l]]); merge(R+l, R[l], y2); merge(L+l, L[l], y1); *v = l; } pull(*v); } int dfs(int u) { if (a[u]) { return treap0(a[u]); } else { int lt = dfs(b[u]); int rt = dfs(c[u]); int v; long long c2 = S[lt] * S[rt]; inv = 0; merge(&v, lt, rt); ans += (inv > c2 - inv) ? c2 - inv : inv; return v; } } int main() { scanf("%d", &n); int root = read(); dfs(root); printf("%lld", ans); return 0; }

rot.cpp: In function 'int read()':
rot.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d", a+v);
      |     ~~~~~^~~~~~~~~~~
rot.cpp: In function 'int main()':
rot.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~