2014
11-30

# Evaluating Functions

A teleport machine – a special kind of machine capable of moving objects from one place to another instantaneously, without passing through the intervening space – has just been invented. Out of curiosity, you went to the laboratory and asked if you could have a try. Although even the engineers who have designed this machine can’t control where the object entering the machine will end up, they have told you the way the teleport machine operates:

In the interior of the teleport machine you may find a special structure (as illustrated above). There are N cylinders of possibly different integer heights, and a special (yet unknown to you) value had been assigned to each of them in the following way:

Suppose the heights of the cylinders are recorded in the array H[] , the values assigned to them are recorded in the array value[] , and we are currently calculating the value for cylinder X (i.e., valuex . Before this process is executed, valuex will be set to zero, and we initialized a pointer, P , which should be pointing to X at the beginning)

0.
Let P = P – 1 . (i.e., modifies the pointer P so that it now points to the cylinder on the left side of the current cylinder P ). If there’s none (P = = NULL) , or Hp > Hx , then let P = X , and go to step 2; otherwise, proceed to the next step.
1.
Find the highest cylinder on the left side of the cylinder P , and let its height be H’ . If such cylinder exists, increase valuex by max{min{H’, Hx} – Hp, 0} , and go to step 0.
2.
Let P = P + 1 . (i.e., modifies the pointer P so that it now points to the cylinder on the right side of the current cylinder P ). If there’s none (P = = NULL) , or Hp > Hx , then terminate the process; otherwise, proceed to the next step.
3.
Find the highest cylinder on the right side of the current cylinder P , and let its height be H’ . If such cylinder exists, increase valuex by max{min{H’, Hx} – Hp, 0} , and go to step 2.

You have to enter two integers, the distance which you want to move the object, K , and the K -th largest value T among all N cylinders’ values. A serious malfunction will occur unless the numbers K and T are entered correctly. (It is easy to see that if we follow the process described above strictly, it takes O(N3) time to calculate all values; that is why the engineers can only use short-distance teleportation so far; however you wonder whether there exists a way to evaluate the function effectively so as to use the long-range transfer ability of this machine.)

Now you have to figure out what the value of T is, given the heights of all cylinders of the teleport machine and the distance you need to move the object. For example you find the machine has 5 cylinders, and the distance you want to move the object is 2. Their heights are 2 1 2 1 3 so your calculations (value ) are 2 0 2 0 2. After that the T which you should enter the second largest value is 2.

There are multiple test cases in the input file. Each test case starts with two integers N and K (1<=N<=2×105, 1<=K<=N) , the number of cylinders on the teleport machine, and the distance you want to move the object, respectively. Each of the following N lines contains one integer P (1<=P<=10^6) , the integer on the i -th line representing the height of the i -th cylinder. There is a blank line after each test case. A single line with N = 0 , K = 0 indicates the end of input file.

There are multiple test cases in the input file. Each test case starts with two integers N and K (1<=N<=2×105, 1<=K<=N) , the number of cylinders on the teleport machine, and the distance you want to move the object, respectively. Each of the following N lines contains one integer P (1<=P<=10^6) , the integer on the i -th line representing the height of the i -th cylinder. There is a blank line after each test case. A single line with N = 0 , K = 0 indicates the end of input file.

5 2
2
1
2
1
3

5 1
4
5
1
1
7

0 0

Case 1: 2
Case 2: 8

#include<stdio.h>
#include<algorithm>

#define N 200009
typedef long long LL;

using namespace std;

int n,m,a[N],b[N],c[N],L[N],R[N];
LL d[N],s1[N],s2[N],sum[N];

LL max(LL aa, LL bb)
{
if(aa > bb)return aa;
return bb;
}

void make()
{
int i,j,k,l;
for(i=1;i<=n;i++)
{
k = i-1;
while(k > 0 && a[k] <= a[i])k = b[k];
b[i] = k;
}

for(i=n;i>0;i--)
{
k = i+1;
while(k <= n && a[k] <= a[i])k = c[k];
c[i] = k;
}
}

int main()
{
int i,j,k,l,cas=0;
while(scanf("%d %d",&n,&m) != EOF)
{
if(n == 0 && m == 0)break;
sum[0] = 0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i] = sum[i-1] + a[i];
}
make();

L[1] = a[1]; for(i=2;i<=n;i++) { L[i] = a[i]; if(L[i] < L[i-1])L[i] = L[i-1]; }
R[n] = a[n]; for(i=n-1;i>0;i--) { R[i] = a[i]; if(R[i] < R[i+1])R[i] = R[i+1]; }

s1[1] = 0;
for(i=2;i<=n;i++)
{
s1[i] = s1[i-1] + max(L[i-1] - a[i], 0);
}
s2[n] = 0;
for(i=n-1;i>0;i--)
{
s2[i] = s2[i+1] + max(R[i+1] - a[i], 0);
}

for(i=1;i<=n;i++)
{
d[i] = 0;
k = b[i];
if(k < 1)d[i] += s1[i];
else
{
l = i-k-1; d[i] += (LL)l*a[i] - (sum[i-1]-sum[k]);
}
//	printf("%d ",d[i]);
k = c[i];
if(k > n)d[i] += s2[i];
else
{//printf("%d %d %d\n",k,l*a[i], (sum[k-1]-sum[i]));
l = k-i-1; d[i] += (LL)l*a[i] - (sum[k-1]-sum[i]);
}
//	printf("%d\n",d[i]);
}
sort(d+1, d+1+n);
printf("Case %d: %I64d\n",++cas,d[n-m+1]);
}
return 0;
}

1. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。