Original link: https://www.shuizilong.com/house/archives/luogu-p2048-noi2010-%E8%B6%85%E7%BA%A7%E9%92%A2%E7%90%B4/
You can first write a violent RMQ to solve the 10-point code of K=1, to ensure that you have not read the wrong question and understood it as a string problem.
Then top K can use a method similar to the ugly number Humble Numbers in [USACO3.1] to open a pile, and every time a number is found, it will be split and stuffed back.
The amount of data in this question is large enough, the subscript of the query array starts from 0, and the position of rmq is also asked, which is very suitable for us to use our newly learned O(n)-O(1) RMQ to show our talents! . . .
#include <lastweapon/bitwise>
using namespace lastweapon;
const int N = int(5e5) + 9;
int s[N];
int n, K, L, R;
template<typename T> struct rmq {
vector<T> v; int n;
static const int b = 30; // block size
vector<int> mask, t; // mask and sparse table
int op(int x, int y) {
return v[x] < v[y] ? x : y;
}
// least significant set bit
int lsb(int x) {
return x & -x;
}
// index of the most significant set bit
int msb_index(int x) {
return __builtin_clz(1)-__builtin_clz(x);
}
// answer query of v[r-size+1..r] using the masks, given size <= b
int small(int r, int size = b) {
// get only 'size' least significant bits of the mask
// and then get the index of the msb of that
int dist_from_r = msb_index(mask[r] & ((1<<size)-1));
return r - dist_from_r;
}
rmq(){}
rmq(const vector<T>& v_) : v(v_), n(v. size()), mask(n), t(n) {
int curr_mask = 0;
for (int i = 0; i < n; i++) {
// shift mask by 1, keeping only the 'b' least significant bits
curr_mask = (curr_mask<<1) & ((1<<b)-1);
while (curr_mask > 0 and op(i, i - msb_index(lsb(curr_mask))) == i) {
// current value is smaller than the value represented by the
// last 1 in curr_mask, so we need to turn off that bit
curr_mask ^= lsb(curr_mask);
}
// append extra 1 to the mask
curr_mask |= 1;
mask[i] = curr_mask;
}
// build sparse table over the n/b blocks
// the sparse table is linearized, so what would be at
// table[j][i] is stored in table[(n/b)*j + i]
for (int i = 0; i < n/b; i++) t[i] = small(b*i+b-1);
for (int j = 1; (1<<j) <= n/b; j++) for (int i = 0; i+(1<<j) <= n/b; i++)
t[n/b*j+i] = op(t[n/b*(j-1)+i], t[n/b*(j-1)+i+(1<<(j-1) )]);
}
// query(l, r) returns the actual minimum of v[l..r]
// to get the index, just change the first and last lines of the function
T query(int l, int r) {
// query too small
//if (r-l+1 <= b) return v[small(r, r-l+1)];
if (r-l+1 <= b) return small(r, r-l+1);
// get the minimum of the endpoints
// (there is no problem if the ranges overlap with the sparse table query)
int ans = op(small(l+b-1), small(r));
// 'x' and 'y' are the blocks we need to query over
int x = l/b+1, y = r/b-1;
if (x <= y) {
int j = msb_index(y-x+1);
ans = op(ans, op(t[n/b*j+x], t[n/b*j+y-(1<<j)+1]));
}
//return v[ans];
return ans;
}
};
rmq<int> T;
struct rec {
int i, l, r, m, f;
rec(int i, int l, int r) : i(i), l(l), r(r), m(T. query(l, r)) {
f = s[i] - s[m];
}
bool operator < (const rec& r) const {
return f < rf;
}
};
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n, K, L, R);
VI a; a.PB(0);
REP_1(i, n) RD(s[i]) += s[i-1], a.PB(s[i]); a.pop_back();
T = rmq<int>(a);
priority_queue<rec> Q;
FOR_1(i, L, n) {
Q.push(rec(i, max(0, iR), iL));
}
LL z = 0; DO(K) {
auto u = Q.top(); Q.pop(); z += uf;
if (um != ul) Q. push(rec(ui, ul, um-1));
if (um != ur) Q.push(rec(ui, u.m+1, ur));
}
cout << z << endl;
}
This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p2048-noi2010-%E8%B6%85%E7%BA%A7%E9%92%A2%E7%90%B4/
This site is only for collection, and the copyright belongs to the original author.