【BZOJ3711】Druzyny
题面
题解
首先我们有一个(O(n^2))的(dp)：
设(f_i)表示现在已经分好了(1...i)的组，且(i)作为一组的结尾的最大值，那么转移的话就是对于每个
(maxlimits_{k=j}^i c_kleq i-j+1leq minlimits_{k=j}^i d_k)的(f_{j-1})转移一下。
然后这个平方算法减下枝就艹过去了
然后想想怎么优化这个东西。
令(pre_i)表示在仅考虑(d)的限制之下，对于某一右端点(i)可以转移过来的左端点(j-1)的最靠左的位置，那么上文的(j)对应的就是([j+1,i])这个区间，而且(pre)肯定也是单调不降的。
我们考虑在这样子处理(d)限制的基础之上解决(c)限制，对于一个点的转移，肯定只与一段区间内(c)的最大值有关，考虑最大值分治。假设对于一段区间([l,r])，([l+1,r])的(c)所处的最大值位置为(p)(由上文所述，(f_l)是否能转移到(f_r)不取决于(l)的情况)，然后递归处理([l,p))再对于(jin [l,p))，我们要求出(f_j)对于(f_i,iin [p,r])的贡献，最后递归([p,r])。
那么问题的关键在于对于(forall iin [p,r])，(pre_i)不降，在复杂度正确的情况下求出(forall jin [l,p))对其的贡献。
下面分为四种情况解决这个问题：
( ext{Case 1:})
(pre_ileq l,i-p+1< c_p)，此时这种(i)会由([l...x](x< p))这段前缀转移过来，第一次用线段树找到最开始的前缀最大值然后随着(i)增加往后面推可以(O(1))转移。
这种情况只会(O(log n))查一次以及一次(min(p-l,r-p+1))遍历一次，与最大值分治复杂度一致。
( ext{Case 2:})
(pre_ileq l,i-p+1geq c_p)，这时候整个左区间都能转移过来，二分一下(pre_ileq l)最大的(i)然后线段树区间修改即可。
这种情况只会(O(log n))改一次以及(O(log n))二分一次。
( ext{Case 3:})
(pre_i>l)，直接暴力查线段树区间即可。
对于(forall i)，分治时只会出现至多一次这样的情况，总复杂度(O(nlog n))。
( ext{Case 4:})
直接退出即可。
最后这题卡空间只能用线段树求区间最值，复杂度(O(nlog n))在上面已经分析过了。
代码
(O(nlog n))：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int INF = 1e9;
const int Mod = 1e9 + 7;
const int MAX_N = 1e6 + 5;
int N, c[MAX_N], d[MAX_N], pre[MAX_N];
struct Data { int f, g; } F[MAX_N];
Data operator + (const Data &l, const Data &r) {
if (l.f == r.f) return (Data){l.f, (l.g + r.g) % Mod};
else {
if (l.f < r.f) return (Data){r.f, r.g};
else return (Data){l.f, l.g};
}
}
#define lson (o << 1)
#define rson (o << 1 | 1)
namespace SGT1 {
int maxp[MAX_N << 2];
void build(int o, int l, int r) {
if (l == r) return (void)(maxp[o] = l);
int mid = (l + r) >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
maxp[o] = c[maxp[lson]] > c[maxp[rson]] ? maxp[lson] : maxp[rson];
}
int query(int o, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return maxp[o];
int mid = (l + r) >> 1, res = 0;
if (ql <= mid) res = query(lson, l, mid, ql, qr);
if (qr > mid) {
int p = query(rson, mid + 1, r, ql, qr);
res = c[res] > c[p] ? res : p;
}
return res;
}
}
namespace SGT2 {
Data Max[MAX_N << 2], Tag[MAX_N << 2];
void pushup(int o) { Max[o] = Max[lson] + Max[rson]; }
void puttag(int o, Data v) { Tag[o] = Tag[o] + v, Max[o] = Max[o] + v; }
void pushdown(int o) {
puttag(lson, Tag[o]);
puttag(rson, Tag[o]);
Tag[o] = (Data){-INF, 0};
}
void build(int o, int l, int r) {
Max[o] = Tag[o] = (Data){-INF, 0};
if (l == r) return ;
int mid = (l + r) >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
}
void upd(int pos) {
int o = 1, l = 0, r = N;
while (l < r) {
pushdown(o);
int mid = (l + r) >> 1;
if (pos <= mid) o = lson, r = mid;
else o = rson, l = mid + 1;
}
F[pos] = Max[o] = F[pos] + Tag[o];
while (o >>= 1) pushup(o);
}
void modify(int o, int l, int r, int ql, int qr, Data v) {
if (ql <= l && r <= qr) return puttag(o, v);
pushdown(o);
int mid = (l + r) >> 1;
if (ql <= mid) modify(lson, l, mid, ql, qr, v);
if (qr > mid) modify(rson, mid + 1, r, ql, qr, v);
pushup(o);
}
Data query(int o, int l, int r, int ql, int qr) {
if (ql > qr) return (Data){-INF, 0};
if (ql <= l && r <= qr) return Max[o];
pushdown(o);
int mid = (l + r) >> 1;
Data res = (Data){-INF, 0};
if (ql <= mid) res = res + query(lson, l, mid, ql, qr);
if (qr > mid) res = res + query(rson, mid + 1, r, ql, qr);
return res;
}
}
void init() {
SGT1::build(1, 1, N);
SGT2::build(1, 0, N);
static priority_queue<int, vector<int>, greater<int> > q1, q2;
for (int i = 1; i <= N; i++) {
pre[i] = pre[i - 1];
q1.push(d[i]);
while (!q2.empty() && q1.top() == q2.top()) q1.pop(), q2.pop();
while (q1.top() < i - pre[i]) {
q2.push(d[++pre[i]]);
while (!q2.empty() && q1.top() == q2.top()) q1.pop(), q2.pop();
}
}
}
void Div(int l, int r) {
if (l == r) return SGT2::upd(l);
int p = SGT1::query(1, 1, N, l + 1, r);
Div(l, p - 1);
int pos = max(p, l + c[p]);
Data nw = SGT2::query(1, 0, N, l, pos - c[p] - 1);
while (pos <= r && pre[pos] <= l && pos - c[p] < p) {
nw = nw + F[pos - c[p]];
F[pos] = F[pos] + (Data){nw.f + 1, nw.g};
++pos;
}
if (pos <= r && pre[pos] <= l) {
int L = pos, R = r;
while (L < R) {
int M = (L + R + 1) >> 1;
if (pre[M] <= l) L = M;
else R = M - 1;
}
SGT2::modify(1, 0, N, pos, L, (Data){nw.f + 1, nw.g});
pos = L + 1;
}
while (pos <= r && pre[pos] < p) {
nw = SGT2::query(1, 0, N, pre[pos], min(pos - c[p], p - 1));
F[pos] = F[pos] + (Data){nw.f + 1, nw.g};
++pos;
}
Div(p, r);
}
int main () {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
#endif
N = gi();
for (int i = 1; i <= N; i++) c[i] = gi(), d[i] = gi();
for (int i = 1; i <= N; i++) F[i] = (Data){-INF, 0};
F[0] = (Data){0, 1};
init();
Div(0, N);
if (F[N].f <= 0) puts("NIE");
else printf("%d %d
", F[N].f, F[N].g);
return 0;
}