主题

主题

 
   

常数优化与底层优化的小技巧

  • 扯淡

常数优化:

#1

常数优化一直是OI中存在的问题。很多知名选手轻松想出了正解,或者不知名选手(如鄙人)绞尽脑汁终于想出了正解,结果出题人用(Sang)心(xin)良(Bing)苦(Kuang)卡常让本应该得到的分数丢失。

这是一种值(Ying)得(Gai)推(Bei)广(Biao)的行为,考查OIer的综合素质。不过本蒟认为,OI本应该考察的核心应该是算法而不是编程技巧。但是为了对付这样高(Wu)明(Liao)的出题人,我们需要一些小小的卡常技巧。

另一个问题是在,想出了一个稍差的解法,如一个O(nlog^3n)的解法。然而标程是O(nlog^2n)。那么我们就需要使

 
 
 
   

LCT对子树信息的维护

  • 扯淡

以前总是以为LCT只能够维护树链信息。

现在长知识了。

总是有很多神犇,出一些 加边+删边+换根+子树查询 的问题。

那么我们拥有了LCT这种强大的数据结构之后,就可以实现了。


  • 定义

我们定义几种儿子:

  1. x的虚儿子:若在LCT中,Fa[y]=x,且y不为xSplay的儿子,那么我们称y为x的一个虚儿子。

  2. x的实儿子:x的Splay的儿子。众所周知,x的实儿子不一定是x在原树上的儿子。

再定义几种信息:

  1. x的“虚儿子信息”:x的所有的虚儿子的“总信息”。

  2. x的“总信息”:x的“虚儿子信息”+x的实儿子的“...

 
 
 
   

NanoApe Loves Sequence Ⅱ

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5806

Problem Description

NanoApe, the Retired Dog, has returned back to prepare for for the National Higher Education Entrance Examination!

In math class, NanoApe picked up sequences once again. He wrote down a sequence with n numbers and a number m on...

 
 
 
   

Price List Strike Back

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5808

Problem Description

There are n shops numbered with successive integers from 1 to n in Byteland. Every shop sells only one kind of goods, and the price of the i-th shop's goods is vi. The distance between the i-th shop and Byteasar's home is di.

Every...

 
 
 
   

Palace

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5721

Problem Description

The last trial Venus imposes on Psyche is a quest to the underworld. She is to take a box and obtain in it a dose of the beauty of Prosperina, queen of the underworld.

There are n palaces in the underworld, which can be located...

 
 
 
   

4765: 普通计算姬

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=4765

Description

"奋战三星期,造台计算机"。小G响应号召,花了三小时造了台普通计算姬。普通计算姬比普通计算机要厉害一些

。普通计算机能计算数列区间和,而普通计算姬能计算树中子树和。更具体地,小G的计算姬可以解决这么个问题

:给定一棵n个节点的带权树,节点编号为1到n,以root为根,设sum[p]表示以点p为根的这棵子树中所有节点的权

值和。计算姬支持下列两种操作:

1 给定两个整数u,v,修改点u的权值为v。

2 给定两个整数l,...

 
 
 
   

2633. [HZOI 2016]数列操作e

原题:http://cogs.pro/cogs/problem/problem.php?pid=2633

【题目描述】

一个长度为n的序列,一开始序列数的权值都是0,有m次操作

支持两种操作,

1 L R x,给区间[L,R]内,第一个数加x,第二个数加2^2⋅x,第三个数加3^2⋅x...第R-L+1个数加(R−L+1)^2⋅x

2 L R 查询区间[L,R]内的权值和

每次询问的答案对2^64取模

【输入格式】

第一行两个数n,m,表示序列长度和操作次数

接下来m行,每行描述一个操作,有如下两种情况:

1 L R x,给区间[L,R]内,第一个数加x,第二个数加2^2⋅...

 
 
 
   

The sum of gcd

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5381

Problem Description

You have an array A,the length of A is n

Let f(l,r)=∑ri=l∑rj=igcd(ai,ai+1....aj)

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

First...

 
 
 
   

4540: [Hnoi2016]序列

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=4540

Description

  给定长度为n的序列:a1,a2,…,an,记为a[1:n]。类似地,a[l:r](1≤l≤r≤N)是指序列:al,al+1,…,ar-1,ar。

若1≤l≤s≤t≤r≤n,则称a[s:t]是a[l:r]的子序列。

现在有q个询问,每个询问给定两个数l和r,1≤l≤r≤n,求a[l:r]的不同子序列的最小值之和。

例如,给定序列5,2,4,1,3,询问给定的两个数为1和3,那么a[1:3]有6个子序列a[1:1],a[2:2],a[3:3],a[1...

 
 
 
   

[1457] Sona

原题:https://ac.2333.moe/Problem/view.xhtml?id=1457

问题描述

Sona, Maven of the Strings. Of cause, she can play the zither.

Sona can't speak but she can make fancy music. Her music can attack, heal, encourage and enchant.

There're an ancient score(乐谱). But because it's too long, Sona can't play it in...