自动搬运

查看原文

来自洛谷，原作者为

	Rorschachindark 无数死了的人中的一个而已，没什么可说的。

搬运于2025-08-24 22:04:32，当前版本为作者最后更新于2021-02-06 11:24:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

Description

对于一个序列 A ，我们定义 $f(A,k)$ 表示在模 $k$ 意义下 A 序列对于一段连续区间 $+1$ 或 $-1$ 使得 A 序列所有元素皆为 $0$ 的最少操作步数。

现在给出一个长度为 $n$ 的 $a_{1,2,...,n}$ 序列，有 $m$ 次查询，每次给出 $l,r,k$，表示需要查询 $f([l,r],k)$。

$n\le 2\times 10^5,m\le 10^5,\max\{a_1,a_2,...,a_n\}<k\le 2^{30}$

Solution

出题人：唯一一道数据结构题，所以思路不是那么难。只要你会50分，就可以轻松优化到100分。

我表示我™想不到 $50$ 分做法，看了题解之后才恍然大悟。

这篇题解又跟官方题解有所不同，但是整体思路差不多，代码实现要简单一些。

我们首先考虑一个序列的情况。我们先在首尾加 $0$。假如没有模 $k$ 的条件的话，我们设 $b_i=a_i-a_{i-1}$，那么问题就相当于 $\sum b_i=0$，每次可以对于 $b_i\to b_i+1,b_j\to b_j-1(i<j)$，问最小步数使得所有 $b_i$ 皆为 $0$ 。

不难看出，因为 $\sum b_i=0$，所以如果现在还没有满足条件，那么，一定有 $b_i>0$ 且 $b_j<0$，所以可以想到，答案就是 $(\sum|b_i|)/2$ 。

考虑有模 $k$ 的条件，那么，我们可以看成是一开始序列某些值 $+k$ 或 $-k$。可以看出，$\sum b_i$ 仍需等于 $0$，所以你一个数 $+k$，那么必有另外一个数 $-k$。另外可以看出的是，对于 $-a$，如果你加 $k$，那么贡献就会减少 $2a-k$，对于 $a$，如果你减 $k$ ，那么贡献也会减少 $2a-k$。这个时候我们就可以做到 $50$ 分了，就是直接每次直接把 $2a-k$ 提出来排个序求前缀和，然后求个最大值即可。

考虑优化，不难看出，我们可以使用主席树维护一个区间 $|2a|$ 的前 $s$ 大的和。也就是说，如果我们知道我们要加多少次 $s$ ，我们就可以计算出贡献。

我们可以看出的另一个性质是，这个贡献随 $s$ 的变化实际上是一个凸函数，所以我们二分顶点，证明的话应该可以感性理解一下。

时间复杂度 $\Theta(n\log w+m\log n\log w)$，其中 $w$ 是值域，$\log w=30$。

Code for 50 pts

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define int long long
#define MAXN 200005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,m,A[MAXN],pre1[MAXN],pre2[MAXN];

#define abs(x) ((x)<0?-(x):(x))
int Count (int L,int R,int K){
	int ans = abs (A[L]) + abs (A[R]);
	for (Int i = L + 1;i <= R;++ i) ans += abs (A[i] - A[i - 1]);
	int tot1 = 0,tot2 = 0;
	if (A[L] < 0) pre1[++ tot1] = 2 * abs(A[L]) - K;else pre2[++ tot2] = 2 * abs(A[L]) - K;
	if (A[R] > 0) pre1[++ tot1] = 2 * abs(A[R]) - K;else pre2[++ tot2] = 2 * abs(A[R]) - K;
	for (Int i = L + 1;i <= R;++ i) 
		if (A[i] - A[i - 1] < 0) pre1[++ tot1] = 2 * abs(A[i] - A[i - 1]) - K;
		else pre2[++ tot2] = 2 * abs (A[i] - A[i - 1]) - K; 
	sort (pre1 + 1,pre1 + tot1 + 1,[](int a,int b){return a > b;}),
	sort (pre2 + 1,pre2 + tot2 + 1,[](int a,int b){return a > b;});
	for (Int i = 1;i <= tot1;++ i) pre1[i] += pre1[i - 1];
	for (Int i = 1;i <= tot2;++ i) pre2[i] += pre2[i - 1];
	int res = ans;
	for (Int i = 1;i <= tot1 && i <= tot2;++ i) res = min (res,ans - pre1[i] - pre2[i]);
	return res >> 1;
}

signed main(){
	read (n,m);
	for (Int i = 1;i <= n;++ i) read (A[i]);
	for (Int i = 1,l,r,k;i <= m;++ i) read (l,r,k),write (Count (l,r,k)),putchar ('\n');
	return 0;
}

Code for 100 pts

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define int long long
#define MAXN 200005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,m,inf,A[MAXN],pre[MAXN];

#define abs(x) ((x)<0?-(x):(x))

struct Segment{
#define LOGN 105
	int tot,rt[MAXN],siz[MAXN * LOGN],sum[MAXN * LOGN],son[MAXN * LOGN][2];
	void modify (int &x,int y,int l,int r,int pos){
		x = ++ tot,siz[x] = siz[y] + 1,sum[x] = sum[y] + pos,son[x][0] = son[y][0],son[x][1] = son[y][1];
		if (l == r) return ;
		int mid = (l + r) >> 1;
		if (pos <= mid) modify (son[x][0],son[y][0],l,mid,pos);
		else modify (son[x][1],son[y][1],mid + 1,r,pos);
	}
	int query (int x,int y,int l,int r,int k,int pos){
		if (!k) return 0;
		if (l == r) return k * l;
		int mid = (l + r) >> 1,alls = siz[son[y][1]] - siz[son[x][1]] + (mid < pos && pos <= r);
		if (alls <= k) return query (son[x][0],son[y][0],l,mid,k - alls,pos) + sum[son[y][1]] - sum[son[x][1]] + (mid < pos && pos <= r) * pos;
		else return query (son[x][1],son[y][1],mid + 1,r,k,pos);
	}
}Tree[2];

int Count (int l,int r,int k,int S){
	int ans = (pre[r] - pre[l] + A[l] + A[r]) / 2;
	return S * k + ans - Tree[0].query (Tree[0].rt[l],Tree[0].rt[r],0,inf,S,A[r]) - Tree[1].query (Tree[1].rt[l],Tree[1].rt[r],0,inf,S,A[l]); 
}

int Work (int l,int r,int K){
	int tot1 = Tree[0].siz[Tree[0].rt[r]] - Tree[0].siz[Tree[0].rt[l]] + 1,tot2 = Tree[1].siz[Tree[1].rt[r]] - Tree[1].siz[Tree[1].rt[l]] + 1;
	int L = 0,R = min (tot1,tot2),ans = 0;
	while (L <= R){
 		int mid = (L + R) >> 1;
		if (mid == 0 || Count (l,r,K,mid - 1) >= Count (l,r,K,mid)) ans = mid,L = mid + 1;
		else R = mid - 1;
	}
	return Count (l,r,K,ans);
}

signed main(){
//	freopen ("data.in","r",stdin);
//	freopen ("WA.out","w",stdout);
	read (n,m),inf = 1 << 30;
	for (Int i = 1;i <= n;++ i) read (A[i]);
	for (Int i = 2,val;i <= n;++ i){
		val = abs (A[i] - A[i - 1]),pre[i] = pre[i - 1] + abs (A[i] - A[i - 1]);
		if (A[i] >= A[i - 1]) Tree[0].rt[i] = Tree[0].rt[i - 1],Tree[1].modify (Tree[1].rt[i],Tree[1].rt[i - 1],0,inf,val);
		else Tree[1].rt[i] = Tree[1].rt[i - 1],Tree[0].modify (Tree[0].rt[i],Tree[0].rt[i - 1],0,inf,val); 
	}
	for (Int i = 1,l,r,k;i <= m;++ i) read (l,r,k),write (Work (l,r,k)),putchar ('\n');
	return 0;
}