这个题目让我们求每次操作后的最大魔法值，考虑维护一棵权值线段树。
但是，范围这么大？
没事，动态开点。维护一棵大树，即为我们选择了的魔导书的树，以及每种不同$T$值的树。
具体的看代码注释吧，理解后并不难。
#include <bits/stdc++.h> using namespace std; #define N 300010 #define ll long long const ll MAX = 1000000050; /*权值线段树*/ inline ll read(){ ll x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); } return x * s; } int tree[N]; int tree_tot; struct node{ ll num, val; int lson, rson; } t[N * 90]; inline void pushup(int o){ t[o].num = t[t[o].lson].num + t[t[o].rson].num; t[o].val = t[t[o].lson].val + t[t[o].rson].val; return ; } ll root = 0; void update(int& o, int l, int r, int x, int k){ if(l > x || r < x) return ; if(!o) o = ++root; // 新建 if(!x) return ; if(l == x && l == r){ t[o].num += k; // 该权值数量的书 ++ t[o].val = t[o].num * x; // 这个权值的书的权值的总和 = 数量 * 权值 return ; } int mid = l + r >> 1; update(t[o].lson, l, mid, x, k); update(t[o].rson, mid + 1, r, x, k); pushup(o); return ; } ll query(int& o, int l, int r, int in, int end){ // 查询的是一段书的权值的数量，数量，数量！！ if(l > end || r < in) return 0; if(!o) { o = ++root; return 0; } if(l >= in && r <= end){ return t[o].num; // 该类书的数量 } int mid = l + r >> 1; return (ll)(query(t[o].lson, l, mid, in, end) + query(t[o].rson, mid + 1, r, in, end)); } // o 理解为 t的种类 ll get1(int& o, int l, int r, int k){ // 在 t这一类书里面第 k大的权值 if(!o) o = ++root; if(!k) return 0; if(k > t[o].num) return 0; if(l == r) return l; int mid = l + r >> 1; if(k <= t[t[o].rson].num) return get1(t[o].rson, mid + 1, r, k); else return get1(t[o].lson, l, mid, k - t[t[o].rson].num); } ll get2(int& o, int l, int r, int k){ // 前 k的权值和 if(!o) o = ++root; if(!k) return 0; if(k > t[o].num) return t[o].val; if(l == r) return (ll)(k * l) ; // 转换成long long输出 int mid = l + r >> 1; if(k <= t[t[o].rson].num) return get2(t[o].rson, mid + 1, r, k); // 先向右跑 else return get2(t[o].lson, l, mid, k - t[t[o].rson].num) + t[t[o].rson].val; } int main(){ freopen("grimoire.in", "r", stdin); freopen("grimoire.out", "w", stdout); int n = read(), m = read(); char c[10]; while(m--){ scanf("%s", c + 1); int t = read(), w = read(); // 价值 if(c[1] == 'B'){ ll k = query(tree[t], 1, MAX, w, MAX); // 找比这本书大的书的数量 if(k < t){ // 还没满,那么这本书还能往里面塞 update(tree[t], 1, MAX, w, 1); ll pos = get1(tree[t], 1, MAX, t + 1); // 这一类书所有权值的区间内，在 t + 1后的那本书的权值 update(tree_tot, 1, MAX, w, 1); update(tree_tot, 1, MAX, pos, -1); // 这本书被挤出去了 } else update(tree[t], 1, MAX, w, 1); } else { int k = query(tree[t], 1, MAX, w, MAX); // 第t类书里面比这本书大的有多少本 if(k <= t){ update(tree[t], 1, MAX, w, -1); // 把自己删掉 ll pos = get1(tree[t], 1, MAX, t); //找到后面那一本会往前移动的书 update(tree_tot, 1, MAX, w, -1); // 总树删掉 update(tree_tot, 1, MAX, pos, 1); } else update(tree[t], 1, MAX, w, -1); } ll ans = get2(tree_tot, 1, MAX, n); // 求总权值区间中的前n大的和 printf("%lld ", ans); } return 0; }