首页 > 其他分享 >(淼)大家快来改T2,只用两个for循环(雾)

(淼)大家快来改T2,只用两个for循环(雾)

时间:2023-01-10 19:56:09浏览次数:46  
标签:begin lret 快来 int rret T2 poly merge 只用

今天T2只用两个for循环就能切,怎么没人来改(雾)

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
using ll = long long;
using poly = vector<ll>;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll a[N];
poly merge(const poly& a, const poly& b, bool zero){
	poly c(a.size() + b.size() - 1);
	c[0] = a[0] + b[0];
	merge(a.begin() + 1, a.end(), b.begin() + 1, b.end(), c.begin() + 1, greater<ll>());
	if(zero) c.insert(c.begin(), 0);
	return c;
}
poly max(poly a, poly b){
	poly c(max(a.size(), b.size()), -INF);
	partial_sum(a.begin(), a.end(), a.begin());
	partial_sum(b.begin(), b.end(), b.begin());
	for(int i = 0; i < c.size(); ++i){
		if(i < a.size()) c[i] = max(c[i], a[i]);
		if(i < b.size()) c[i] = max(c[i], b[i]);
	}
	adjacent_difference(c.begin(), c.end(), c.begin());
	return c;
}
array<poly, 4> solve(int l, int r){
	if(l == r) return {poly{a[l]}, poly{-a[l]}, poly{0}, poly{0}};
	int mid = (l + r) >> 1;
	array<poly, 4> lret = solve(l, mid), rret = solve(mid + 1, r), ret;
	ret[0] = max(merge(lret[0], rret[3], 0), merge(lret[2], rret[0], 0));
	ret[1] = max(merge(lret[1], rret[2], 0), merge(lret[3], rret[1], 0));
	ret[2] = max(merge(lret[2], rret[2], 0), merge(lret[0], rret[1], 1));
	ret[3] = max(merge(lret[3], rret[3], 0), merge(lret[1], rret[0], 1));
	return ret;
}
// ret  :  +O, -O , +E, -E
int n;
int main(){
    freopen("jia.in", "r", stdin);
    freopen("jia.out", "w", stdout);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for_each(a + 1, a + 1 + n,[&](auto& x){cin >> x;});
	auto ans = solve(1, n);
	partial_sum(ans[0].begin(), ans[0].end(), ans[0].begin());
	partial_sum(ans[2].begin(), ans[2].end(), ans[2].begin());
	for(int i = 1; i <= n; ++i) cout << ans[i & 1 ? 0 : 2][i / 2] <<" ";
	return 0;
}

标签:begin,lret,快来,int,rret,T2,poly,merge,只用
From: https://www.cnblogs.com/cdsidi/p/17041244.html

相关文章

  • mormot2ORM
    mormot2ORMunitmormot.orm.core;///rootclassfordefiningandmappingdatabaserecords//-inheritsaclassfromTOrm,andaddpublishedpropertiesto......
  • Spring Boot 3.0横空出世,快来看看是不是该升级了
    目录简介对JAVA17和JAVA19的支持recordTextBlocksSwitchExpressionsinstanceof模式匹配SealedClassesandInterfaces迁移到JakartaEEGraalVMNativeImageSupport对M......
  • NoneBot2聊天机器人自定义聊天内容
    1、按照上一篇文章所介绍的方法新建一个机器人,进入所对应的文件夹,会发现里面有一个和自己所创建的机器人名称一样的文件夹   2、进入该文件夹,会发现一个名叫plugins......
  • 不懂任务调度系统,快来看这篇
    摘要:本文讲解如何实现一个任务调度系统的核心逻辑。本文分享自华为云社区《实现一个任务调度系统,看这篇文章就够了》,作者:勇哥java实战分享。1QuartzQuartz是一款Java......
  • 搭建MyCat2双主双从的MySQL读写分离
    一、MySQL双主双从一个主机m1用于处理所有写请求,它的从机s1和另一台主机m2还有它的从机s2负责所有读请求。当m1主机宕机后,m2主机负责写请求,m1、m2互为备机。......
  • 计蒜客 - T2144 拼数
    计蒜客-T2144拼数题解:把所有数字看成字符串,但是难道直接降序排就结束了嘛,不是的,我们来看一个反例:31312虽然312>31但是明显31312>31231,所以我们不能简单的排序,我......
  • Mycat2
    一、MyCat概述Mycat是数据库中间件,连接java应用程序和数据库。Java程序与数据库紧密关联耦合严重,高访问量高并发对数据库的压力巨大,因此可以引入数据库中间件MyCat解......
  • sc stream-rabbit20230116
        一、Exchanges:testRabbit     二、MQ生产者  1、pom.xml<properties><java.version>1.8</java.version>......
  • NoneBot2搭建QQ聊天机器人
    1、下载python,版本不低于3.8官网:https://www.python.org/downloads/2、构建python虚拟环境(强烈推荐,当然也可以跳过此步骤)#cmd命令行pipinstallvirtualenvwap......
  • Servlet2
    1 Servlet 简介Servlet是什么?JavaServlet是运行在Web服务器或应用服务器上的程序,它是作为来自Web浏览器或其他HTTP客户端的请求和HTTP服务器上的数据库或......