标签 - cdq分治

? 解题记录 ? ? HDU ? ? cdq分治 ? ? FFT|NTT ?    2018-07-27 10:33:39    669    0    0
Problem Description Perhaps the sea‘s definition of a shell is the pearl. However, in my view, a shell necklace with n beautiful shells contains the most sincere feeling for my best lover Arrietty, but even that is not enough.Suppose the shell necklace is a sequence of shells (not a chain end to end
? 解题记录 ? ? 杂OJ ? ? cdq分治 ?    2018-07-13 23:28:09    802    0    0
【题目描述】给定一个有n个元素的序列,元素编号为1~n,每个元素有三个属性a,b,c,求序列中满足i<j且ai<aj且bi<bj且ci<cj的数对(i,j)的个数。 【输入格式】第一行一个整数n,表示序列长度。 第二行n个整数,分别表示a1~an。 第三行n个整数,分别表示b1~bn。 第四行n个整数,分别表示c1~cn。 【输出格式】一个整数,表示答案。 【样例输入】5 1 5 3 4 2 2 5 3 4 1 1 2 5 3 4【样例输出】3【样例解释】满足条件的(i,j)共有以下三对: (1,2) (1,3) (1,4) 【数据范围与约定】对于30%的数据,n<
? 解题记录 ? ? BZOJ ? ? cdq分治 ? ? 分治 ? ? Kruscal ?    2018-05-21 18:44:15    480    0    0
【题目描述】PS国是一个拥有诸多城市的大国,国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路,在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素,城市之间修建道路需要的花费会随着时间而改变,Louis会不断得到某道路的修建代价改变的消息,他希望每得到一条消息后能立即知道使城市连通的最小花费总和, Louis决定求助于你来完成这个任务。 【输入】文件第一行包含三个整数N,M,Q,分别表示城市的数目,可以修建的道路个数,及收到的消息个数。 接下来M行,第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1≤Xi
? 解题记录 ? ? KD tree ? ? BZOJ ? ? cdq分治 ? ? 分治 ?    2017-07-21 10:06:08    781    0    0
Description 有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。Input 第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。 以下N行,每行三个整数si, ci, mi (1 <= si, ci, mi <= K),
? 解题记录 ? ? 洛谷 ? ? cdq分治 ? ? 模板 ? ? 分治 ?    2017-07-18 11:19:52    1227    0    0
题目背景这是一道模版题 可以使用bitset,CDQ分治,K-DTree等方式解决。 题目描述有  个元素,第  个元素有 、、 三个属性,设  表示满足  且  且  的  的数量。 对于 ,求  的数量 输入输出格式输入格式:  第一行两个整数 、,分别表示元素数量和最大属性值。 之后  行,每行三个整数 、、,分别表示三个属性值。   输出格