The main idea of the title
There are two lengths
n
n
sequence of n
a
,
b
a,b
a, b, these two sequences are monotonic.
you can
a
a
a proceeds no more than
m
m
m operations, you can choose one for each operation
i
i
i satisfy
1
≤
i
≤
n
1\leq i\leq n
1≤i≤n, then choose an integer (can be negative)
x
x
x, will
a
i
a_i
ai? plus
x
x
x, this operation costs
x
2
x^2
The cost of x2.
During operation, you need to ensure
a
a
a is always monotonous.
Finally, you need to
a
a
a sequence becomes
b
b
b sequence, that is, for any
i
i
i satisfy
1
≤
i
≤
n
1\leq i\leq n
1≤i≤n, both
a
i
=
b
i
a_i=b_i
ai?=bi?.
Find the minimum total cost required. Output answer model
998244353
998244353
The value after 998244353. if it is impossible to let
a
a
a sequence becomes
b
b
b sequence, then output
?
1
-1
?1.
1
≤
n
,
m
≤
1
0
5
,
0
≤
a
i
,
b
i
≤
1
0
9
1\leq n,m\leq 10^5,0\leq a_i,b_i\leq 10^9
1≤n,m≤105,0≤ai?,bi?≤109
Solution
First, we can have every value not equal to
b
i
b_i
bi?
a
i
a_i
ai?Add them all
b
i
?
a
i
b_i-a_i
biai?. We found that for two adjacent positions, we can specify a modification sequence so that when modifying, the two positions always maintain the previous position.
a
a
The value of a does not exceed the last position
a
a
a value. Well, because there will be no cycles in these sequences, this can guarantee
a
a
a is always monotonous.
We operate according to the above method. If the number of operations is not enough, output
?
1
-1
?1.
If there are some operations left, we can use these operations to reduce the cost.
According to the basic inequality, we will
+
x
+x
+ x is divided into multiple additions as evenly as possible to minimize the cost. Then, for each position, add
x
x
x, we record how many copies it is currently split into, assuming it is split into
k
k
k parts, we find out how to split it into
k
+
1
k+1
k + 1 copies compared to
k
k
How much can K shares reduce the cost. At the beginning, each operation can be regarded as being split into one. We use the reduced cost as the key to put these operations in the big root heap. Each time we take out the top of the heap and reduce the cost by the corresponding amount, and then update the operation. Divided into numbers
k
k
k, even if
k
=
k
+
1
k=k+1
k=k + 1, and then continue to calculate and split it into
k
+
1
k+1
k + 1 copies compared to
k
k
How much can k copies reduce the cost and put it into the heap, so that the remaining operations are used up to get the answer.
The time complexity is
O
(
(
n
+
m
)
log
?
n
)
O((n + m)\log n)
O((n + m)logn).
code
#include<bits/stdc + + .h>
using namespace std;
const int N=100000;
const long long mod=998244353;
int n,m;
long long ans=0,a[N + 5],b[N + 5];
struct node{<!-- -->
long long x,k,v;
bool operator<(const node ax)const{<!-- -->
return v<ax.v;
}
};
priority_queue<node>q;
long long dv(long long x,long long k){<!-- -->
return (x/k)*(x/k)*(k-x%k) + (x/k + 1)*(x/k + 1)*(x%k);
}
long long gt(long long x,long long k){<!-- -->
return dv(x,k)-dv(x,k + 1);
}
int main()
{<!-- -->
// freopen("attend.in","r",stdin);
// freopen("attend.out","w",stdout);
scanf("%d%d", & amp;n, & amp;m);
for(int i=1;i<=n;i + + ) scanf("%lld", & amp;a[i]);
for(int i=1;i<=n;i + + ) scanf("%lld", & amp;b[i]);
for(int i=1;i<=n;i + + ){<!-- -->
if(a[i]!=b[i]){<!-- -->
--m;
ans=(ans + (a[i]-b[i])*(a[i]-b[i])%mod)%mod;
q.push((node){<!-- -->abs(a[i]-b[i]),1,gt(abs(a[i]-b[i]),1)});
}
}
if(m<0){<!-- -->
printf("-1");
return 0;
}
if(q.empty()){<!-- -->
printf("%lld",ans);
return 0;
}
while(m--){<!-- -->
node t=q.top();q.pop();
ans=(ans-t.v%mod + mod)%mod;
q.push((node){<!-- -->t.x,t.k + 1,gt(t.x,t.k + 1)});
}
printf("%lld",ans);
return 0;
}