Codeforces 597C Subsequences 数据结构维护DP

http://codeforces.com/contest/597/problem/C

C. Subsequences
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

For the given sequence with n different elements find the number of increasing subsequences with k + 1 elements. It is guaranteed that the answer is not greater than 8·1018.
Input

First line contain two integer values n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — the length of sequence and the number of elements in increasing subsequences.

Next n lines contains one integer ai (1 ≤ ai ≤ n) each — elements of sequence. All values ai are different.

Output

Print one integer — the answer to the problem.

Sample test(s)
Input

Output

给定一个长度为n(n<1e5)的排列和一个正整数k(k<10),问能选出多少个长度为k+1的递增子序列。答案小于8e18

思路:用dp[j][i]表示以第i个数结尾,长度为j的方案数,那么dp[j][i]=sigma(dp[j-1][1~(i-1)]且该位置的数小于a[i]。用树状数组按值建树,建立k个树状数组,求出第j-1个树状数组小于a[i]的sigma。得到dp[j][i]后,将其加入第j个树状数组的a[i]位置即可。

代码:

 

 

Codeforces 597B Restaurant 排序 DP

http://codeforces.com/contest/597/problem/B

B. Restaurant
time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A restaurant received n orders for the rental. Each rental order reserve the restaurant for a continuous period of time, the i-th order is characterized by two time values — the start time li and the finish time ri (li ≤ ri).

Restaurant management can accept and reject orders. What is the maximal number of orders the restaurant can accept?

No two accepted orders can intersect, i.e. they can't share even a moment of time. If one order ends in the moment other starts, they can't be accepted both.

Input

The first line contains integer number n (1 ≤ n ≤ 5·105) — number of orders. The following n lines contain integer values li and ri each (1 ≤ li ≤ ri ≤ 109).

Output

Print the maximal number of orders that can be accepted.

Sample test(s)
Input

Output

Input

Output

Input

Output

题意:给定n(n<5e5)个区间(1<=l<=r<=1e9),从中选取一些,使其互不相交,问能取到的最大数目。

思路:先将区间进行离散化,按照r值排序。从左往右枚举每个离散的点,如果该点不是某个区间的结尾,那么该点的dp值和上一个点的dp值相同,否则可以由某个区间的起点的上一个点的dp+1转移了,取最大值即可。

代码:

 

 

Codeforce 597A Divisibility 简单数学

http://codeforces.com/contest/597/problem/A

A. Divisibility
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Find the number of k-divisible numbers on the segment [a, b]. In other words you need to find the number of such integer values x that a ≤ x ≤ b and x is divisible by k.

Input

The only line contains three space-separated integers k, a and b (1 ≤ k ≤ 1018; - 1018 ≤ a ≤ b ≤ 1018).

Output

Print the required number.

Sample test(s)
Input

Output

Input

Output

题意:问区间[a,b]内有多少个数可以被k整除, 1 ≤ k ≤ 1018; - 1018 ≤ a ≤ b ≤ 1018

思路:由于有负数的存在,将整个区间右移一个k的倍数,使a移动后大于0。然后求出小于a的k的倍数的个数,为(a-1)/k,和小于等于b的倍数的个数,为b/k,两个相减就是区间内的k的倍数的个数。
代码:

 

快速傅里叶变换(FFT)的简单理解和简单应用

一个离散信号x[n]的傅里叶变换X(k)可以写为

    图片

从上述的表达式可以看出,如果暴力计算x[k],时间复杂度为O(N^2) 。当N很大的时候,暴力算法的运行效率很低。所以,我们需要一个高效的算法。

上述的WN 为蝶形因子,利用其对称性和周期性,可减少运算次数。FFT一般分为时间抽取和频率抽取,现在以时间抽取为例。如图为时间抽取为例的过程。

 

    时间抽取FFT是将输入序列x[n]按照奇数项和偶数项分解为奇序列和偶序列。则奇序列为x[1],x[3],x[5]……x[N-1],偶序列为x[0],x[2],x[3]……x[N-2]。这样,可以将X(k)写为

 图片

    因为

 图片

    所以 

图片


可以写成

图片

    由于Y(k)和Z(k)都是以N/2为周期的,并且利用WN 本地图片,请重新上传的对称性和周期性,得到:

 图片

    所以

    图片

    然后分别对Y(k)和Z(k)继续以同样的方式分解下去,最终就使N 点的DFT(离散傅里叶变换)用一组两点的DFT来计算。 所以,总共有log(N)级运算,每一级有N/2个两点点对进行FFT蝶形运算。
单个蝶形运算如下图

    图片

    从上面的时间抽取FFT的示例可以看出,输入序列是按bit反转的顺序排列的,比如110反转为011,第三个输入值和第六个输入值发生了交换。

对于以上交换,可以用下面的代码实现:


 

     以P数组为输入源,反转后存到_P数组,n为数组长度,初始值m=1,curr=cnr=0;

    以上计算,都在复数域进行的,而且,C++自带的复数库比较慢,所以我们自己写一个复数类:


 

 由于算法本身的原因,要求N必须为一个2的整数次方,所以我们需要将输入以高位补零的形式,补充到一定的长度,长度用以下算法得出:


 

处理好这些问题后,我们的FFT算法就可正常地运行了。对于每一级,我们处理的长度为2的i次方。
代码如下:


 

其中,P为需要进行DFT的数组,n为长度,op=1是为正变换,op=-1时,为逆变换。下面给出一个FFT的运用实例:高精度乘法。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1402

将两个乘数都写成多项式的形式,用a[n]和b[n]来表示,和容易知道相乘之后的c[n]=a[n]*b[n]。(卷积)。直接暴力的复杂度是O(N^2) 。设A[k]=DFT(a[n]),B[k]=DFT(b[n])。则C[k]应该满足C[k]=A[k]×B[k]。结果c[n]=IDFT(b[n])。时间复杂度降低为O(nlogn)
示例代码如下:


 

Codeforces 295A Greg and Array 线段树区间累加,单点询问

http://codeforces.com/contest/295/problem/A

A. Greg and Array
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Greg has an array a = a1, a2, ..., an and m operations. Each operation looks as: li, ri, di, (1 ≤ li ≤ ri ≤ n). To apply operation i to the array means to increase all array elements with numbers li, li + 1, ..., ri by value di.

Greg wrote down k queries on a piece of paper. Each query has the following form: xi, yi, (1 ≤ xi ≤ yi ≤ m). That means that one should apply operations with numbers xi, xi + 1, ..., yi to the array.

Now Greg is wondering, what the array a will be after all the queries are executed. Help Greg.

Input

The first line contains integers n, m, k (1 ≤ n, m, k ≤ 105). The second line contains n integers: a1, a2, ..., an (0 ≤ ai ≤ 105) — the initial array.

Next m lines contain operations, the operation number i is written as three integers: li, ri, di, (1 ≤ li ≤ ri ≤ n), (0 ≤ di ≤ 105).

Next k lines contain the queries, the query number i is written as two integers: xi, yi, (1 ≤ xi ≤ yi ≤ m).

The numbers in the lines are separated by single spaces.

Output

On a single line print n integers a1, a2, ..., an — the array after executing all the queries. Separate the printed numbers by spaces.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams of the %I64d specifier.

Sample test(s)
Input

Output

Input

Output

Input

Output

题意:给出一个数列,长度为n,m个操作,k个对操作的执行。对于每一个操作,将数列的区间[Li,Ri]都加上Di。对于每一个执行,对操作[Xi,Yi]都执行一次。最后输出所有执行之后,这个数列的每一个元素的值。

思路:计算出每一个操作执行的次数,也就是每一个操作总共会累加多少值,在对数列进行区间累加即可。要算出每个操作执行了多少次,可以用线段树对操作的下标进行建树,对于每一个执行,对这个线段树进行区间累加1的操作。这样就能算出每个操作执行了多少次,也就可以算出,每个操作最后累加了多少。最后再用另一个线段树维护数列即可

代码:

Codeforces 276C Little Girl and Maximum Sum 线段树区间累加

http://codeforces.com/contest/276/problem/C

C. Little Girl and Maximum Sum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The little girl loves the problems on array queries very much.

One day she came across a rather well-known problem: you've got an array of n elements (the elements of the array are indexed starting from 1); also, there are q queries, each one is defined by a pair of integers li, ri (1 ≤ li ≤ ri ≤ n). You need to find for each query the sum of elements of the array with indexes from li to ri, inclusive.

The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.

Input

The first line contains two space-separated integers n (1 ≤ n ≤ 2·105) and q (1 ≤ q ≤ 2·105) — the number of elements in the array and the number of queries, correspondingly.

The next line contains n space-separated integers ai (1 ≤ ai ≤ 2·105) — the array elements.

Each of the following q lines contains two space-separated integers li and ri (1 ≤ li ≤ ri ≤ n) — the i-th query.

Output

In a single line print a single integer — the maximum sum of query replies after the array elements are reordered.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Sample test(s)
Input

Output

Input

Output

题意:给一个数列长度为n,和m次询问,对于每一次询问,记Qi=sum(a[Li]~a[Ri])。让你重新调整数列a[i]的顺序,使Sigm(Qi)最大。输出这个Sigm

思路:对于每一个位置,求出在Sigm(Qi)中,这个位置的数被加了多少次。对于累加次数最多的位置,我们给他填最大的数,依此贪心,得到的Sigm就是最大的。

对于每一个询问,我们可以看作是在区间[Li,Ri]上的所有位置的累加次数都要+1。这就是个线段树的区间累加,单点询问的操作。得到每个位置被累计的次数后,我们就可以按照上面的方法就行贪心求解。

代码:

 

Codeforces 368B Sereja and Suffixes 线段树按值建树

http://codeforces.com/problemset/problem/368/B

B. Sereja and Suffixes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sereja has an array a, consisting of n integers a1, a2, ..., an. The boy cannot sit and do nothing, he decided to study an array. Sereja took a piece of paper and wrote out m integers l1, l2, ..., lm (1 ≤ li ≤ n). For each number li he wants to know how many distinct numbers are staying on the positions li, li + 1, ..., n. Formally, he want to find the number of distinct numbers among ali, ali + 1, ..., an.?

Sereja wrote out the necessary array elements but the array was so large and the boy was so pressed for time. Help him, find the answer for the described question for each li.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 105). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105) — the array elements.

Next m lines contain integers l1, l2, ..., lm. The i-th line contains integer li (1 ≤ li ≤ n).

Output

Print m lines — on the i-th line print the answer to the number li.

Sample test(s)
Input

Output

题意:给出一个数列长度为n,m次询问,每次输入一个l,要求输出区间[l,n]中有多少个不同的数。

思路:用线段数进行预处理,处理出每个位置到n的这个区间内不同数的个数。将线段树按值建树,从数列的尾部往前面扫描,对于数列的每一个数a[i],在线段树中,如果a[i]处为0的话,把它改成1,否则不变,然后再对整个线段树的区间求和,就是第i个位置的答案。

代码: