当前位置: 首页 > news >正文

P10068 [CCO 2023] Line Town

考察符号的变化,如果是一正一负那么不会变,否则是两位一起奇偶翻转。把奇数位的符号翻转后,每个数可以认为是一个绝对值和符号的二元组。

对于序列最终的形态,其一定是一段负然后一些 \(0\) 再一段正,翻转后就是一段前缀 \(+-+-\cdots\),一段后缀 \(+-+-\cdots +(-)\),最后一位的正负号已知。同时前缀的绝对值递减,后缀的绝对值递增。注意前缀和后缀可以为空。

考虑按绝对值从大往小插数,同时记录 \(f_{0/1,0/1}\) 为当前序列左右分别要求的符号。

转移枚举分别有多少个数放在左右。贡献可以拆成距离和,同侧贡献和异侧贡献。变化量可以用 \(O(1)\) 次二分计算,写起来较为复杂。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int> ;const int kN = 5e5 + 5;
int n;
pii a[kN];
int ord[kN];
ll f[2][2];struct BIT {int tr[kN];void Clear() {fill_n(tr, n + 3, 0);}void Update(int x, int v) {for(; x <= n; x += (x & -x)) tr[x] += v;}int Query(int x) {int ans = 0;for(; x; x &= (x - 1)) ans += tr[x];return ans;}
}bit;void DP(int N, int l, int r) {vector<int> v[2];int dif = 0;for(int i = l; i <= r; i++) {int x = ord[i];bool f = a[x].second;v[f].push_back(bit.Query(x));f ? dif++ : dif--;}auto Calc = [&](int fs, int ft, int ns, int nt) -> ll {deque<int> p[2], q[2];int c[2][2];c[0][0] = v[0].size();c[0][1] = 0;c[1][0] = v[1].size();c[1][1] = 0;auto P = [&](bool f, int c) -> int {return f ? N - (2 * c - 1) + ft : N - 2 * (c - 1) - ft;};auto S = [&](bool f, int i, bool g) -> int {return g ? v[f][i + c[f][0]] : v[f][i]; };auto T = [&](bool f, int i, bool g) -> int {return g ? q[f][i] : p[f][i];};for(int i = 0; i < c[0][0]; i++) {p[0].push_back(fs + 1 + 2 * i);}for(int i = 0; i < c[1][0]; i++) {p[1].push_back(2 - fs + 2 * i);}if(ft != nt) {c[ft][0]--, c[ft][1]++;p[ft].pop_back();q[ft].push_front(P(ft, c[ft][1]));}ll ans = 1e18;ll cost = 0;for(int i : {0, 1}) {for(int j = 0; j < c[i][0]; j++) {cost += v[i][j] - p[i][j];}for(int j = 0; j < c[i][1]; j++) {cost += q[i][j] - v[i][j + c[i][0]];}}for(int f : {0, 1}) for(int g : {0, 1}) for(int h : {0, 1}) {for(int i = 0; i < c[g][f]; i++) {int si = S(g, i, f), ti = T(g, i, f);int l = -1, r = c[!g][h], p = r;while(l + 1 < r) {int mid = (l + r) >> 1;(S(!g, mid, h) >= si) ? (p = r = mid) : (l = mid);}l = -1, r = c[!g][h];while(l + 1 < r) {int mid = (l + r) >> 1;(T(!g, mid, h) <= ti) ? (l = mid) : (r = mid);}int cnt = max(l - p + 1, 0);(f == h) ? (cost += cnt) : (cost -= cnt);}}while(1) {ans = min(ans, cost);if(!c[0][0] || !c[1][0]) break;{int i = c[0][0] - 1;int j = c[1][0] - 1;int si = S(0, i, 0), ti = T(0, i, 0);int sj = S(1, j, 0), tj = T(1, j, 0);cost += ((si <= sj) && (ti >= tj));cost += ((si >= sj) && (ti <= tj));}for(int f : {0, 1}) for(int g : {0, 1}) {int i = c[f][0] - 1;int si = S(f, i, 0), ti = T(f, i, 0);int l = -1, r = c[!f][g];while(l + 1 < r) {int mid = (l + r) >> 1;(S(!f, mid, g) >= si) ? (r = mid) : (l = mid);}int pl = l, pr = r;l = -1, r = c[!f][g];while(l + 1 < r) {int mid = (l + r) >> 1;(T(!f, mid, g) <= ti) ? (l = mid) : (r = mid);}int v = max(l - pr + 1, 0) + max(pl - r + 1, 0);g ? cost += v : cost -= v;}for(int t : {0, 1}) {cost -= v[t][c[t][0] - 1] - p[t][c[t][0] - 1];c[t][0]--, c[t][1]++;p[t].pop_back();q[t].push_front(P(t, c[t][1]));cost += q[t][0] - v[t][c[t][0]];}{int i = 0;int j = 0;int si = S(0, i, 1), ti = T(0, i, 1);int sj = S(1, j, 1), tj = T(1, j, 1);cost -= ((si <= sj) && (ti >= tj));cost -= ((si >= sj) && (ti <= tj));}for(int f : {0, 1}) for(int g : {0, 1}) {int i = 0;int si = S(f, i, 1), ti = T(f, i, 1);int l = -1, r = c[!f][g];while(l + 1 < r) {int mid = (l + r) >> 1;(S(!f, mid, g) >= si) ? (r = mid) : (l = mid);}int pl = l, pr = r;l = -1, r = c[!f][g];while(l + 1 < r) {int mid = (l + r) >> 1;(T(!f, mid, g) <= ti) ? (l = mid) : (r = mid);}int v = max(l - pr + 1, 0) + max(pl - r + 1, 0);g ? cost += v : cost -= v;}}return ans;};ll tf[2][2];memcpy(tf, f, sizeof(tf));memset(f, 0x3f, sizeof(f));for(int fs : {0, 1}) for(int ft : {0, 1}) {if(tf[fs][ft] > 1e16) continue;for(int ns : {0, 1}) for(int nt : {0, 1}) {int nd[2] = {0, 0};if(fs != ns) nd[fs]++;if(ft != nt) nd[ft]++;if(nd[1] - nd[0] != dif) continue;f[ns][nt] = min(f[ns][nt], tf[fs][ft] + Calc(fs, ft, ns, nt));}}for(int i = l; i <= r; i++) bit.Update(ord[i], -1);
}int main() {
//  freopen("1.in", "r", stdin);
//  freopen("1.out", "w", stdout);ios::sync_with_stdio(0), cin.tie(0);cin >> n;for(int i = 1; i <= n; i++) {int x;cin >> x;a[i] = pii {abs(x), (x > 0) ^ (i & 1)};}iota(ord + 1, ord + n + 1, 1);stable_sort(ord + 1, ord + n + 1,[&](int x, int y) { return a[x] > a[y]; });for(int i = 1; i <= n; i++) bit.Update(i, 1);memset(f, 0x3f, sizeof(f));f[1][(n & 1) ^ 1] = 0;for(int rem = n, l = 1, r; l <= n; l = r + 1) {pii val = a[ord[l]];if(!val.first) break;for(r = l; r < n; r++) {pii nxt = a[ord[r + 1]];if(val.first != nxt.first) break;}DP(rem, l, r);rem -= (r - l + 1);}ll ans = 1e18;for(int i : {0, 1}) {for(int j : {0, 1}) ans = min(ans, f[i][j]); }cout << ((ans > 1e16) ? -1 : ans) << "\n";return 0;
}
http://www.hskmm.com/?act=detail&tid=26795

相关文章:

  • AI元人文:共识锚定与智慧剪枝——构建人机共生认知经济体的完善理论体系与实践路径
  • 出题系统
  • io控制方式
  • Java课后作业
  • 我 是 人 机
  • 28定律及其扩展衍生
  • 3516cv610在sample_aiisp上多创一路编码流,方法 - 详解
  • 2025氧化石墨烯、羧基化石墨烯、巯基化石墨烯、羟基化石墨烯、氨基化石墨烯、氮掺杂氧化石墨烯、氮掺杂石墨烯最新推荐、全面剖析优质厂商实力与选购要点
  • 2025-10-8模拟测验
  • QBXT2025S刷题 Day7
  • 【Python】调用C++
  • 方法作业
  • [100ask_imx6ullpro] buildroot构建emmc镜像并烧录
  • 2025 汽车改装公司最新推荐榜:一站式服务生态企业盘点,含奔驰宝马新能源改装及新锐品牌权威测评重庆宝马汽车改装/重庆新能源汽车改装/重庆汽车改装贴膜/重庆汽车改装轮毂刹车公司推荐
  • 2025 布袋包装厂家最新推荐榜:自贸区实力厂商领衔,含手提袋、帆布袋等全品类,年销 500 万级生产商精选无纺布袋/布袋生产/云南布袋包装/茶叶布袋厂家推荐
  • 2025 年成型机厂家最新推荐排行榜:冷弯 / 光伏支架 / 门业 / 建材等领域设备企业精度与耐用性实测点评魔方方管/门框角码/导槽/底樑/光伏支架/C型钢成型机厂家推荐
  • 2025 年平板机厂家最新推荐榜单:聚焦技术实力与市场口碑,5 大优质品牌实测点评
  • 语音识别与合成的融合技术解析
  • 2025 年阳光导入源头厂家最新推荐榜:领军企业技术实力、案例与直销模式深度解析及选择指南工厂/学校/医院/地下车库/隧道阳光导入系统厂家推荐
  • 从Node.js到React/Vue3:流式输出实用的技术的全栈实现指南
  • 用低成本FPGA实现FSMC接口的多串口(UART)控制器
  • 2025 火烧板源头厂家最新推荐榜单:自有矿山保障品质,高硬度耐磨产品全覆盖,五莲花 / 芝麻白 / 防滑芝麻黑采购优选指南
  • 2025 年太阳能路灯厂商最新推荐榜:聚焦优质企业,从技术实力到合作案例全方位解析太阳能道路灯/景观灯/警示灯/庭院灯/草坪灯/杀虫灯厂家推荐
  • 2025 年最新软件开发机构推荐排行榜:涵盖 CRM / 物联网 / 运维管理等系统定制的权威甄选指南成都软件开发/软件定制开发/crm系统定制软件开发机构推荐
  • Luogu P11660 我终将成为你的倒影 题解 [ 紫 ] [ 分块 ] [ 分类讨论 }
  • 2025 年最新推荐!小程序开发机构排行榜:覆盖定制开发 / 电商 / 预订 / 配送多场景优质服务商成都小程序开发/小程序定制开发/电商小程序开发/预订服务小程序开发公司推荐
  • CF280D k-Maximum Subsequence Sum 题解(线段树+反悔贪心维护k段最大子段和)
  • 2025 西安新房住宅最新推荐榜权威发布:多维度测评 + 选房指南,助你精准置业品质/高端/优质/品牌/刚需新房推荐
  • C# async await 测试一
  • 2025 年快速卷帘门厂家最新推荐排行榜:聚焦智能定制与高效供货,精选实力厂家助您精准选购