题面
（为啥这题没有题面……
给出\(N\)个人，和年龄\(age_{i},skill_{i}\)
然后给出\(M\)个询问，就是年龄在\(a\)以下选不超过\(k\)个人
要求选择的人水平排序后不相邻
题解
这个就是如果动态加点，然后从大往小能选的就选
我们把人从大往小排序
设\(g[0/1]\)表示如果左边选了或者没选，那么最右边的点选或没选
\(c[0/1]\)表示如果左边选了或者没选，那么这一段能选多少个
\(q[0/1]\)表示如果左边选了或者没选，这一段的最大价值是多少
我们把询问按年龄排序，然后把人按年龄一个个加进去，就可以直接查询了
加一个人这个人所在的点\(g[0] = 1,c[0] = 1,q[0] = val\)
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,M,id[MAXN];
struct node {
int a,s;
}p[MAXN];
struct qry_node {
int a,k,id;
}qry[MAXN];
struct tr_node {
int l,r;
int c[2],g[2];
int64 q[2];
}tr[MAXN * 4];
int64 ans[MAXN];
void build(int u,int l,int r) {
tr[u].l = l;tr[u].r = r;
if(l == r) return;
int mid = (l + r) >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
}
void update(int u) {
for(int i = 0 ; i < 2 ; ++i) {
tr[u].c[i] = tr[u << 1].c[i] + tr[u << 1 | 1].c[tr[u << 1].g[i]];
tr[u].g[i] = tr[u << 1 | 1].g[tr[u << 1].g[i]];
tr[u].q[i] = tr[u << 1].q[i] + tr[u << 1 | 1].q[tr[u << 1].g[i]];
}
}
void Change(int u,int pos) {
if(tr[u].l == tr[u].r) {
tr[u].g[0] = 1;tr[u].g[1] = 0;
tr[u].c[0] = 1;tr[u].c[1] = 0;
tr[u].q[0] = p[pos].s;tr[u].q[1] = 0;
return;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if(pos <= mid) Change(u << 1,pos);
else Change(u << 1 | 1,pos);
update(u);
}
int64 Query(int u,int k,int r) {
if(tr[u].c[r] <= k) return tr[u].q[r];
if(!k) return 0;
if(tr[u << 1].c[r] > k) {
return Query(u << 1,k,r);
}
else {
int t = tr[u << 1].g[r];
return tr[u << 1].q[r] + Query(u << 1 | 1,k - tr[u << 1].c[r],t);
}
}
bool cmp1(node c,node d) {
return c.s > d.s;
}
bool cmp2(int a,int b) {
return p[a].a < p[b].a;
}
bool cmp3(qry_node s,qry_node t) {
return s.a < t.a;
}
void Solve() {
read(N);
for(int i = 1 ; i <= N ; ++i) {
read(p[i].a);read(p[i].s);
}
sort(p + 1,p + N + 1,cmp1);
for(int i = 1 ; i <= N ; ++i) {
id[i] = i;
}
sort(id + 1,id + N + 1,cmp2);
read(M);
for(int i = 1 ; i <= M ; ++i) {
read(qry[i].a);read(qry[i].k);qry[i].id = i;
}
sort(qry + 1,qry + M + 1,cmp3);
int t = 1;
build(1,1,N);
for(int i = 1 ; i <= M ; ++i) {
while(t <= N && qry[i].a >= p[id[t]].a) {
Change(1,id[t]);
++t;
}
ans[qry[i].id] = Query(1,qry[i].k,0);
}
for(int i = 1 ; i <= M ; ++i) {
out(ans[i]);enter;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}