The 2011 ACM-ICPC ACRC]G.GRE Words(三)
}
*ptr = i, belong[end[i] = ptr - st] = 0;
len[i] = ptr - st - j;
scanf("%d\n", w + i);
}
L = ptr - st;
}
namespace rmq
{
array mini[19];
void prepare()
{
int i, j;
int *p = mini[0], *q;
FOR(i, 1, L) p[i] = height[i];
FOR(i, 1, 18) {
q = p, p = mini[i];
FOR(j, 1, L) p[j] = min(q[j], q[j + (1 << (i - 1))]);
}
}
}
namespace tree
{
struct node
{
node *s, *t, *f;
int l, r, v;
};
node ns[maxn*2], *nt = ns, *root, *back[maxn];
int L, R, ans;
void build(node *&p, int l, int r)
{
p = ++nt, p->l = l, p->r = r, p->v = 0;
if (l == r) {back[l] = p; return;}
build(p->s, l, (l + r) >> 1);
build(p->t, ((l + r) >> 1) + 1, r);
p->s->f = p->t->f = p;
}
void init(int r) {nt = ns; build(root, 1, r);}
void insert(int pos, int k)
{
node *p = back[pos]; p->v = k;
for (p = p->f; p; p = p->f) p->v = max(p->s->v, p->t->v);
void query(node *p)
{
if (L <= p->l && p->r <= R) {ans = p->v; return;}
if (L <= p->s->r && p->s->v > ans) query(p->s);
if (p->t->l <= R && p->t->v > ans) query(p->t);
}
int query(int l, int r) {return ans = 0, L = l, R = r, query(root), ans;}
}
void work(int n)
{
int i, j, k, l, x, y; ans = 0;
rmq::prepare(), tree::init(L);
ROF(i, n, 1) {
int pos = rank[begin[i]], ll, rr;
l = len[i], ll = rr = pos, ++rr;
ROF(j, 19, 0) if ((x = rr + (1 << j) - 1) < L)
if (rmq::mini[j][rr] >= l) rr = x;
ROF(j, 19, 0) if ((x = ll - (1 << j) + 1) > 0)
if (rmq::mini[j][x] >= l) ll = x;
maxim(ans, k = tree::query(ll, rr) + w[i]);
x = begin[i], y = end[i];
for (j = x; j < y; ++j) tree::insert(rank[j], k);
}
printf("%d\n", ans);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("p3.in", "r", stdin);
freopen("p3.out", "w", stdout);
#endif www.2cto.com
int T, n, m;
for (scanf("%d", &T); T--; ) {
init(n, m);
build(L, m);
work(n);
}
return 0;
}