题解 P4846 【LJJ爱数书】

· · 题解

题目传送门

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;
}