Misaka16172's Blog

题意 有一排花，共 nnn 个，第 iii 个的高度是 hih_ihi​​ ，权值是 aia_iai​ ，保证高度互不相同。现在拿走一些花，使剩下的花高度单调递增，问剩下的花权值之和最大是多少。 数据范围与约定： 1≤n≤2×105，1≤hi≤n，1≤ai≤109，h1,h2,⋅⋅⋅,hN1 \leq n \leq 2 \times10^5，1\leq h_i \leq n，1\leq a_i\leq 10^9，h_1,h_2,···,h_N1≤n≤2×105，1≤hi​≤n，1≤ai​≤109，h1​,h2​,⋅⋅⋅,hN​的值均不相等。 前置知识 前置知识：线段树、动态规划 思路 看到这题我们能想到一个很显然的dp做法：设f[i]f[i]f[i]为取前iii朵花中的一些花，且第iii朵最高时能取得的最大权值，则f[i]=max{f[j],j<i,h[j]<h[i]}+a[i]f[i]=max\{f[j],j<i,h[j]<h[i]\}+a[i]f[i]=max{f[j],j<i,h[j]<h[i]}+a[i]，在每次取到iii时再遍历一次f[1 ...

题目大意 给定一棵具有nnn个节点的树，以111号点为根节点，且每个点的权值都为111或000。现在要求进行mmm次操作，get x代表询问节点xxx的子树中有多少个点的权值是111，pow x代表将节点xxx的子树中的所有节点取反。要求对于每个get指令给出答案。 思路 对一棵树进行维护显然十分不方便，我们考虑将树的每个节点转换为一个区间，每个叶子节点转化成一个值，对区间的值使用线段树进行操作。用线段树进行区间维护需要满足的前提是区间的可加性，而一棵树所有子节点的和的确满足这个特征。那么如何将一棵树转化成一个线性序列以方便使用线段树维护呢？我们可以利用求解树的dfs序来建立树上的节点与序列下标之间的映射。映射完之后我们就可以把这题当作一道板子来写了。 (1) 求解树的dfs序 关于树的dfs序在这篇炒冷饭的题解里就不详细解释了~~（其实是因为其他大佬讲得比我详细得多）~~，用简单的一句话来说就是在从根节点对一棵树进行dfs时每个节点被遍历到的顺序。以下图所示的一棵树举例： 这棵树的dfs序是0->1->2->6->4->5->7->8-&g ...

Day -INF J组初赛前一天。 看了看锣鼓上的模拟卷，觉得自己应该能考上50分，于是摆烂睡觉。讲个笑话，本蒟蒻的第一次CSP-J竟然是在高一，CSP-S甚至怕水平不够没敢报，实在是太菜了。 Day -INF+1 初赛是在bsz考的，主场作战，场上rp大爆发，蒙对了四道选择，估分80pts。 可是出分之后不知道哪挂了2.5pts，最后77.5进了复赛，突然感觉自己又行了。 Day -1 J组复赛前一天。 上锣鼓写了几道往年J组的t1 t2，把之前一直没写过的直播获奖a掉了。很难想象这个时候在一个小时内切掉橙题就能让我觉得自己很牛批。 可是写着写着被CSP-J 2019的公交换乘卡住了，交了两发都零分，大大挫伤了自己的信心，为明天的逆天表现埋下了伏笔。 Day 0 J组复赛去了ssf，看见身边都是比我小还比我强的小朋友倍感难受。谁让我耽误了最珍贵的青春呢。 上机之后发现键盘是机械键盘，好评，但是旁边小朋友打字真的很吵。 先看t1，甚至一开始真的开了个1e9的bool数组，险些爆零，发现暴力时间复杂读太烂 （其实真实原因是我当时码力太烂连暴力 ...

学oi这么多月了第一次场切黄题（尽管不会哈希做法用的是侥幸没被出题人卡掉的umap），所以打算写篇题解，顺带着测试一下自己blog的可用性（反正也没有人看）（连LaTeX都不支持可用个鬼啊） 根据题面，假设两个点在第ttt秒相遇，则编号为iii的AAA类点在第ttt秒时的坐标为(i,ai⋅t)(i,a_i\cdot t)(i,ai​⋅t)，编号为jjj的BBB类点在第ttt秒时的坐标则为(bj⋅t,j)(b_j\cdot t,j)(bj​⋅t,j)。显然，当同时满足i=bj⋅ti=b_j\cdot ti=bj​⋅t且j=ai⋅tj=a_i\cdot tj=ai​⋅t时，两点能在第ttt秒相遇。可以把上式变形为t=ibj=jait=\frac {i} {b_j}=\frac {j} {a_i}t=bj​i​=ai​j​。 到这里就是第一个坑点了，t不一定是一个整数，所以不能直接计算ibj\frac {i} {b_j}bj​i​和jai\frac {j} {a_i}ai​j​的值，c++中除法的自动取整会把两个互不相等的ttt取成同一个整数。于是可以想到把等式两边同时乘以bj⋅aib_j ...