【题解】[Balkan2012]The Best Teams 线段树 bzoj3022 ——quhengyi11

听说是权限题所以没有传送门

题意大概是说给你 $n$个队员的年龄和水平值，每次询问选 $k$个小于等于年龄 $a$的队员的最大水平值和为多少。要求每次选择队员水平值不能相邻（指它们的水平值的 $rank$不相邻）

首先可以考虑离线降维，我们将年龄从小到大排个序，是队员就加入待选，是询问就在待选队员里选择，那样就可以不管年龄限制了。

然后我们用线段树维护这个待选队员集合

因为有一个限制是队员水平值不能相邻，所以我们先将所有队员的水平值排序并且算出 $rank_i$，用线段树维护 $rank_i$，如果队员进入待选集合，就将她扔到对应的 $rank_i$节点，为了维护相邻 $rank$不能同时选择，我们维护以下节点

$t[u].s[0/1]$表示的是在 $[不选择/选择]$$第 $$r+1$个人的时候区间 $[l,r]$在不限制选择人数的情况下的最大水平和

$t[u].c[0/1]$表示的是在 $[不选择/选择]$$第 $$r+1$个人的时候区间 $[l,r]$能达到 $t[u].s[0/1]$的水平和时选择的人数

$t[u].g[0/1]$表示的是在 $[不选择/选择]$$第 $$r+1$个人的时候区间 $[l,r]$能达到 $t[u].s[0/1]$的水平和时，选不选择第 $l$个数

然后我们就可以合并信息啦～（细节看代码）

询问在线段树上二分就行了。

代码

#include<bits/stdc++.h>
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define Re register
#define pb push_back
#define F first
#define S second
#define ll long long 
#define lowbit(x) (x & -x)
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 1000000007
#define N 300005
#define g(u, tt) t[u].g[tt]
#define s(u, tt) t[u].s[tt]
#define c(u, tt) t[u].c[tt]
struct segt{
    bool g[2];
    int c[2];
    ll s[2];
}t[N << 2];
struct node{
    int a, v, rk;
}d[N], q[N];
int n, m;
ll ans[N];
inline bool cmp1 (node x, node y) {return x.v < y.v;}
inline bool cmp2 (node x, node y) {return x.a < y.a;}
inline void update (int u)
{
    g(u, 0) = g(ls, g(rs, 0)); g(u, 1) = g(ls, g(rs, 1));
    c(u, 0) = c(ls, g(rs, 0)) + c(rs, 0);
    c(u, 1) = c(ls, g(rs, 1)) + c(rs, 1);
    s(u, 0) = s(ls, g(rs, 0)) + s(rs, 0);
    s(u, 1) = s(ls, g(rs, 1)) + s(rs, 1);
}
inline void modify (int u, int L, int R, int pos, int val)
{
    if (L == R)
    {
        g(u, 0) = 1;
        c(u, 0) = 1;
        s(u, 0) = val;
        return;
    }
    int mid = L + R >> 1;
    if (pos <= mid) modify(ls, L, mid, pos, val);
    else modify(rs, mid + 1, R, pos, val);
    update(u);
}
inline ll query (int u, int L, int R, int k, bool fl)
{
    if (L == R) {return s(u, fl);}
    int mid = L + R >> 1;
    if (c(rs, fl) >= k) return query(rs, mid + 1, R, k, fl);
    else return s(rs, fl) + query(ls, L, mid, k - c(rs, fl), g(rs, fl));
}
int main ()
{
    scanf("%d", &n);
    fo (i, 1, n)
        scanf("%d %d", &d[i].a, &d[i].v);
    scanf("%d", &m);
    fo (i, 1, m)
    {
        scanf("%d %d", &q[i].a, &q[i].v);
        q[i].rk = i;
    }
    std::sort(d + 1, d + n + 1, cmp1);
    fo (i, 1, n) d[i].rk = i;
    std::sort(d + 1, d + n + 1, cmp2);
    std::sort(q + 1, q + m + 1, cmp2);
    int j = 1;
    fo (i, 1, m)
    {
        while (j <= n && d[j].a <= q[i].a) {modify(1, 1, n, d[j].rk, d[j].v); ++j;}
        ans[q[i].rk] = query(1, 1, n, q[i].v, 0);
    }
    fo (i, 1, m) printf("%lld\n", ans[i]);
}

总结：对于这种有限制关系的操作 (比如此题的相邻数不能选)，我们可以通过维护边界选择情况来进行合并。