- 2024-11-01整数二分 ——洛谷p9240冶炼金属
#include<bits/stdc++.h>#defineendl'\n'#defineINF0x3f3f3f3f#defineintlonglongusingnamespacestd;constintN=1e4+10;inta[N],b[N];intn;//找左节点boolcheck_min(intmid){ for(inti=0;i<n;i++) { if(b[i]<a[i]/mid) return
- 2024-10-08速通大ds记
通过一些手段,可以将这题转化为CF280D于是在过完样例后,一发入魂AC了,喜#include<bits/stdc++.h>usingnamespacestd;#definei128__int128#definelllonglong#defineullunsignedlonglong#definepiipair<int,int>#definefifirst#definesesecond#definelowb
- 2024-10-08士兵训练 题解
题意link.题解正解会RE几个点,是官方的栈空间太小了。再者网上几篇题解都被我hack了,好不容易找到一组hack却不是我错了,而是STD错了……所以我来写篇题解造福社会。观察到\(\max\{b_i\bmodb_j\}\),则得到的结果一定比最大值小,则最大能取到次大。那就维护一个子树
- 2024-09-29Can you answer these queries III(单点修改线段树)
因为洛谷出现UE在acwing提交,输入格式略有修改#include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefvector<string>VS;typedefvector<int>
- 2024-09-221. 冶炼金属
#include<bits/stdc++.h>usingnamespacestd;#defineendl"\n";#defineintlonglongintconstintN=1e4+10;inta[N],b[N];intn;boolcheckMin(intmid){for(inti=0;i<n;i++){if(a[i]<b[i]/mid){
- 2024-06-23[题解]P2042 [NOI2005] 维护数列 - Splay解法
P2042[NOI2005]维护数列一道思路不难,但实现细节很多的平衡树题,调了一天半终于做出来了w。对于初始序列,我们可以直接构建一条链(毕竟一个一个调用插入函数也可能形成一条链)。题解有递归直接构建成一棵严格平衡的二叉树的,这样也可以,常数可能会小一点。其中区间反转就是裸的文艺
- 2024-02-20山海经
解:一眼看到这题,觉得是道板子题,但是如果直接暴力的话会kuku超时。所以只能智取!!解释都在代码里,自行观看:点击查看代码#include<bits/stdc++.h>#definelsrt<<1#definersrt<<1|1#definemid((tr[rt].l+tr[rt].r)>>1)usingnamespacestd;constintN=4e7+10;intn,m,w
- 2023-12-31CF1827F 题解
不妨先考虑一个弱化版的问题,这个问题和原来的问题仅有一个区别:\(k\)是给定整数。称最后\(n-k\)个数是“特殊的”。那么我们可以注意到,每个特殊的数字的极大段必然递增放置或者递减放置。例如我们有排列\([7,5,8,1,4,2,6,3]\)而且\(k=2\),那么极大段的下标应该是\([1,4],[6,
- 2023-09-01P4344 SHOI2015 脑洞治疗仪
\(P4344\)[\(SHOI2015\)]脑洞治疗仪一、题目描述曾经发明了自动刷题机的发明家\(SHTSC\)又公开了他的新发明:脑洞治疗仪——一种可以治疗他因为发明而日益增大的脑洞的神秘装置。为了简单起见,我们将大脑视作一个\(01\)序列。\(1\)代表这个位置的脑组织正常工作,\(0\)代表
- 2023-06-11permu题解(树上莫队)(非正解)
题目传送门题意给出一个长度为$n$的排列$P(P1,P2,...Pn)$,以及$m$个询问。每次询问某个区间$[l,r]$中,最长的值域连续段长度。思路首先这道题事求连续段的长度,打个莫队先#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;namespaceTestify{ inlineint
- 2023-05-15hdu:LCIS(线段树+区间合并)
ProblemDescriptionGivennintegers.Youhavetwooperations:UAB:replacetheAthnumberbyB.(indexcountingfrom0)QAB:outputthelengthofthelongestconsecutiveincreasingsubsequence(LCIS)in[a,b].InputTinthefirstline,indicatingt
- 2023-05-07【Disrupter】学习小记
Disrupter是什么看官网:https://github.com/LMAX-Exchange/disruptor它号称是一个很快很快的MQ,然后,脑海里面冒出一个问题,既然如此,那为什么还需要其它的MQ?按这个逻辑,什么kafka,rabbitmq,rocketmq,pulsar等这些岂不是没人用了?不对啊。肯定不对。看官网的第一句,其实已经给出
- 2023-04-05单机最快的队列Disruptor解析和使用
前言介绍高性能队列Disruptor原理以及使用例子。Disruptor是什么?Disruptor是外汇和加密货币交易所运营商LMAXgroup建立高性能的金融交易所的结果。用于解决生产者、消费者及其数据存储的设计问题的高性能队列实现。可以对标JDK中的ArrayBlockingQueue。是目前单机且基于内
- 2022-10-20P6492 STEP(线段树维护左右区间pushup)
题目链接题目描述:给定一个长度为\(~\)n\(~\)的字符序列\(~\)a,初始时序列中全部都是字符\(~\)L。有\(~\)q\(~\)次修改,每次给定一个\(~\)x,做出如下变化:\(~~\)1.a\(_
- 2022-10-18P6492 [COCI2010-2011#6] STEP(线段树维护左右区间pushup)
题目链接题目大意:\(~~\)初始给定一个长度为n的字符序列a,初始序列中全是\(~\)L\(~~\)共有q次修改,修改a\(_{x}\)为:L\(\rightarrow\)\(~~\)or\(~~\)R\(\rightarrow\)L\(
- 2022-10-14主说,马要拉车,于是马就学会了拉车。
\(\operatorname{Manacher}\)算法大体来讲并不难,使用它可以在线性时间内求出某字符串中最大回文子串的长度。基础首先我们知道一个回文串的长度可以是奇数(存在回文中心),
- 2022-10-11[CEOI2019]Dynamic Diameter
做题时间:2022.10.10\(【题目描述】\)给定一棵\(n(2\leqn\leq10^5)\)个点的带边权的树,有\(q(q\leq10^5)\)次询问,每次询问将树上的一条边\(d\)的边权修改为\(e(e
- 2022-08-31CF739C Alyona and towers 解题报告
线段树绝世好题。题意:维护区间加,全局最长单峰序列。Solution:维护\(8\)个量。\(lval\):左端点的权值。\(rval\):右端点的权值。\(lmax\):以左端点开始的最长的下降序
- 2022-08-30P4513 小白逛公园
求动态区间最大子段和,并支持单点修改。\(n\leq5\times10^5,m\leq10^5\)。用线段树处理。对于每一个节点维护以下变量:\(ans\)表示区间内最大子段和,\(sum\)表示区间