题意
题目链接
sol
线段树合并为什么我会在这个时候学这种东西
就是暴力合并两棵线段树(必须动态开节点),遇到空节点就返回
可以证明,对于(m)个仅有一个元素,权值范围在([1, n])的线段树合并的复杂度为(mlogn)
对于此题来说,显然子树内与子树外互不影响,因此暴力判断一下翻转之后会不会变优就行了
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e7 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, val[maxn], ls[maxn], rs[maxn], tot; ll ans, c1, c2; int newtree(int l, int r, int x) { val[++tot] = 1; if(l == r) return tot; int mid = l + r >> 1, now = tot; if(x <= mid) ls[now] = newtree(l, mid, x); else rs[now] = newtree(mid + 1, r, x); return now; } int merge(int l, int r, int x, int y) { if(!x || !y) return x + y; if(l == r) {val[++tot] = val[x] + val[y]; return tot;} c1 += 1ll * val[rs[x]] * val[ls[y]], c2 += 1ll * val[ls[x]] * val[rs[y]]; int mid = l + r >> 1, now = ++tot; ls[now] = merge(l, mid, ls[x], ls[y]); rs[now] = merge(mid + 1, r, rs[x], rs[y]); val[now] = val[x] + val[y]; return now; } int dfs() { int v = read(); if(v) return newtree(1, n, v); int now = merge(1, n, dfs(), dfs()); ans += min(c1, c2); c1 = c2 = 0; return now; } int main() { n = read(); dfs(); cout << ans; return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606598.html