题面

这是2019四川省赛的C题。这里放上CodeForces的链接：C. Cycle Function - Codeforces

Fish is learning functions! He has a linear function \(f(x)=Ax+B\) and \(N\) numbers \(x_1,x_2,⋯,x_N\). Now he is curious about for each function \(g(x)\) in

\[ \left\{ \begin{matrix} g_1(x)=c_1x+d_1\\ g_2(x)=c_2x+d_2\\ \vdots\\ g_M(x)=c_Mx+d_M \end{matrix} \right\} \]

how to calculate the difference between \(f(g(x))\) and \(g(f(x))\).

As smart as Fish is, he soon comes up with a function \(D(x)=|f(g(x))−x|+|g(f(x))−x|\) and uses the sum over \(x_1,x_2,⋯,x_N\) as the difference.

Can you tell him all the differences immediately?

Input
The first line of input contains an integer \(T\), representing the number of test cases.

Then for each test case:

The first line contains two integers \(N, M\) as mentioned above and then two real numbers \(A, B\) indicating the given function \(f(x)=Ax+B\).

The second line contains \(N\) real numbers \(x_1,x_2,⋯,x_N\).

Then \(M\) lines follow, each line containing two real numbers \(c_i, d_i\) indicating a function \(g_i(x)=c_ix+d_i\) mentioned above.

All numbers in the same line are separated by one space.

Output
For each test case, you should output Case x: in the first line, where \(x\) indicates the case number starting from \(1\).

Then \(M\) lines follow, the \(i\)-th line of which contains a real number representing the difference for given function \(g_i(x)\).

Your answers will be considered correct if its absolute error does not exceed \(10^{−6}\).

Limits

time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Note

\(1≤T≤100\)
\(1≤N,M≤10^5\)
\(−100≤A,B,x_i,c_i,d_i≤100\)
For \(90\%\) test cases: \(max(N,M)≤1000\)

Example Input

2
3 2 2.0 3.0
1.0 2.0 3.0
0.4 -2.0
0.6 -5.0
3 2 2.5 2.0
1.0 2.0 3.0
0.4 -2.0
0.6 -5.0

Example Output

Case 1:
7.800000
28.200000
Case 2:
12.600000
36.900000

大意

给定一个线性函数\(f(x)=Ax+B\)和一个线性函数组\(g_i(x)=c_ix+d_i\)，定义函数\(D(x)=|f(g(x))−x|+|g(f(x))−x|\)，对于给定的一组数\(x_i,\enspace i=i,2,\dots,n\)，求关于线性函数组里的每个函数，$ \sum_{i=1}^{n} D(x_i)$的值。

题解

我们对这两个绝对值符号里面的内容做一下数学变换，记\(Ac-1=a,Ad+B=p,Bc+d=q\)：

式子变得简单了不少。但是绝对值仍然是一个让人非常讨厌的东西，需要对正数与负数进行分类讨论。而且，本题有至多1e5个变量和 1e5个函数，虽然时间限制是5秒，但是平方复杂度的暴力解法必定会超时。我们考虑到，对于线性函数\(F(x)=kx+b\)，当\(k=0\)时值永远为\(b\)，否则其零点为\(x_0=-\frac{b}{k}\)，因此我们只需要特判系数\(a\)是否为0，然后考虑大于\(x_0\)的数以及不大于\(x_0\)的数，分别计算即可，一连串数据的求和可以使用前缀和来维护，分界点排序后使用二分查找函数lower_bound即可。这题知道思路了就很简单，但是确实蛮难想的……

排序复杂度为\(O(NlogN)\)，对每个函数二分查找总复杂度为\(O(MlogN)\)，综合复杂度为\(O((M+N)logN)\)，可以接受。

另：本题卡输入输出，要使用C风格的输入输出或者手搓快读快写。Java或者Python选手还是放弃吧o(￣▽￣)ブ笔者使用关闭流同步的cin\cout超时，改scanf\printf只用了2000ms……

下面是代码：

#include <bits/stdc++.h>
#define GRP int T;cin>>T;rep(C,1,T)
#define FAST ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define elif else if
#define mem(arr,val) memset(arr,val,sizeof(arr))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const double EPS = 1e-8;
int n, m;
double a, b;
double xs[100010], x[100010], c, d;
double ans;

int main() {
	xs[0] = 0;
	GRP {
		scanf("%d %d %lf %lf", &n, &m, &a, &b);
		printf("Case %d:\n", C);
		//读入并排序，求前缀和
		rep(i, 1, n) {
			scanf("%lf", x + i);
		}
		sort(x + 1, x + 1 + n);
		rep(i, 1, n) {
			xs[i] = xs[i - 1] + x[i];
		}
		//处理每个g(x)
		rep(i, 1, m) {
			scanf("%lf %lf", &c, &d);
			ans = 0;
			double a1 = a * c - 1, p = a * d + b, q = b * c + d;	//计算系数
			if (abs(a1) < EPS) {					//浮点数为0应判断其绝对值小于一个极小值
				ans = (abs(p) + abs(q)) * n;
			} else {
				//寻找分界点
				int i1 = lower_bound(x + 1, x + 1 + n, -p / a1) - x - 1;
				int i2 = lower_bound(x + 1, x + 1 + n, -q / a1) - x - 1;
				//分别求值并且累加
				ans += abs(a1 * (xs[i1] - xs[0]) + p * (i1));
				ans += abs(a1 * (xs[n] - xs[i1]) + p * (n - i1));
				ans += abs(a1 * (xs[i2] - xs[0]) + q * (i2));
				ans += abs(a1 * (xs[n] - xs[i2]) + q * (n - i2));
			}
			printf("%.7lf\n", ans);
		}
	}
	return 0;
}

/*
          _           _    _            _
    /\   | |         | |  | |          (_)
   /  \  | | _____  _| |__| | ___  _ __ _ _ __   __ _
  / /\ \ | |/ _ \ \/ /  __  |/ _ \| '__| | '_ \ / _` |
 / ____ \| |  __/>  <| |  | | (_) | |  | | | | | (_| |
/_/    \_\_|\___/_/\_\_|  |_|\___/|_|  |_|_| |_|\__, |
                                                 __/ |
                                                |___/
*/