20200725T2 【NOIP2015模拟10.27】魔道研究

魔道研究

“我希望能使用更多的魔法。不对，是预定能使用啦。最终我要被大家称呼为大魔法使。为此我决定不惜一切努力。”
——《The Grimoire of Marisa》雾雨魔理沙
魔理沙一如既往地去帕秋莉的大图书馆去借魔导书(Grimoire) 来学习魔道。
最开始的时候，魔理沙只是一本一本地进行研究。然而在符卡战中，魔理沙还是战不过帕秋莉。
好在魔理沙对自己的借还和研究结果进行了记录，从而发现了那些魔导书的精妙之处。
帕秋莉的那些魔导书，每本都有一个类别编号ti 和威力大小pi。而想要获得最有威力的魔法，就必须同时研究一些魔导书。而研究的这些魔导书就必须要满足，类别编号为T 的书的本数小于等于T，并且总共的本数小于等于一个给定的数N。而研究这些魔导书之后习得的魔法的威力就是被研究的魔导书的威力之和。
为了击败帕秋莉，魔理沙想要利用自己发现的规律来获得最有威力的魔法。
她列出了计划中之后M 次的借还事件，并想要知道每个事件之后自己所能获得的魔法的最大威力。可她忙于魔法材料——蘑菇的收集，于是这个问题就交给你来解决了。

输入文件grimoire.in。
第1 行2 个整数N,M，分别表示魔理沙能研究的魔导书本数的上限和她的借还事件数。
之后M 行，每行的形式为“op t p”（不含引号）。Op 为“BORROW” 或“RETURN”，分别表示借书和还书。T 为一个整数，表示这本书的类别编号。P为一个整数，表示这本书的威力大小。注意，还书时如果有多本书满足类别编号为t，威力大小为p，这表明这些书都是相同的，魔理沙会任选其中一本书还回去。如果你问我为何会有相同的书，多半因为这是魔导书吧。

输出文件grimoire.out。
一共M 行，每行一个整数，即每个事件之后的最大威力。

5 10
BORROW 1 5811
BORROW 3 5032
RETURN 3 5032
BORROW 3 5550
BORROW 5 3486
RETURN 1 5811
RETURN 3 5550
BORROW 4 5116
BORROW 3 9563
BORROW 5 94

5811
10843
5811
11361
14847
9036
3486
8602
18165
18259

对于5% 的数据，1 <= t,N,M <= 50。
对于10% 的数据，1 <= t,N,M <= 100。
对于30% 的数据，1 <= t,N,M<= 10 000。
另有30% 的数据，1 <= p <= 1 000。
对于100% 的数据，1 <= t,N,M <= 300 000,1<= p<= 1 000 000 000。
另外，总共有30% 的数据，满足没有“RETURN” 操作。这部分数据均匀分布。

solution

做法

前置芝士

线段树动态开点

权值线段树

线段树上二分

浅析

code

Talk is cheap, show you code

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<queue>
  7 #include<vector>
  8 #include<stack>
  9 #include<set>
 10 #include<deque>
 11 #include<map>
 12 using namespace std;
 13 
 14 template <typename T> void read(T &x) {
 15     x = 0; int f = 1; char c;
 16     for (c = getchar(); c < '0' || c > '9'; c = getchar()) if (c == '-') f = -f;
 17     for (; c >= '0' && c <= '9'; c = getchar()) x = 10 * x + c - '0' ;
 18     x *= f;
 19 }
 20 template <typename T> void write(T x){
 21     if (x < 0) putchar('-'), x = -x;
 22     if (x > 9) write(x / 10);
 23     putchar(x % 10 + '0');
 24 }
 25 template <typename T> void writeln(T x) { write(x); putchar('
'); }
 26 template <typename T> void writesn(T x) { write(x); putchar(' '); }
 27 
 28 #define ll long long
 29 #define inf 1000000000
 30 #define next net
 31 #define P 2147483647
 32 #define N 30000010
 33 #define mid ((l+r)>>1)
 34 #define lson (o<<1)
 35 #define rson (o<<1|1)
 36 #define R register
 37 #define debug puts("zxt")
 38 
 39 int n, m , x, y, z;
 40 ll ans;
 41 char opt[10];
 42 int tot;
 43 int root[300010 ];
 44 struct node{
 45     int l, r, num;
 46     ll sum ;
 47 }tree[N ];
 48 inline void add(int &rt, int l, int r, int val, int k)
 49 {
 50     if(!rt) rt = ++tot;
 51     tree[rt].num += k;
 52     tree[rt].sum += 1ll * k * val;
 53     if(l == r) return;
 54     if(val <= mid) add(tree[rt].l, l, mid, val, k);
 55     else add(tree[rt].r, mid + 1, r, val, k);
 56     return;
 57 }
 58 inline int ask(int rt, int l, int r, int k)
 59 {
 60     if(l == r)
 61     {
 62         ans += 1ll * l * min(tree[rt].num , k);
 63         return l;
 64     }
 65     if(k <= tree[tree[rt].r].num ) return ask(tree[rt].r, mid + 1, r, k);
 66     else 
 67     {
 68         ans += 1ll * tree[tree[rt].r].sum ;
 69         return ask(tree[rt].l, l, mid, k - tree[tree[rt].r].num );
 70     }
 71 }
 72 signed main()
 73 {
 74     //freopen("grimoire.in","r",stdin);
 75     //freopen("grimoire.out","w",stdout);
 76     read(n); read(m );
 77     while(m --)
 78     {
 79         scanf("%s",opt);
 80         read(x); read(y);
 81         if(opt[0] == 'B')
 82         {
 83             z = ask(root[x], 0, inf, x);
 84             add(root[x], 0, inf, y, 1);
 85             if(y > z)
 86             {
 87                 add(root[0], 0, inf, y, 1);
 88                 add(root[0], 0, inf, z, -1);
 89             }
 90         }
 91         else
 92         {
 93             z = ask(root[x], 0, inf, x + 1);
 94             add(root[x], 0, inf, y, -1);
 95             if(y > z)
 96             {
 97                 add(root[0], 0, inf, y, -1);
 98                 add(root[0], 0, inf, z, 1);
 99             }
100         }
101         ans = 0;
102         ask(root[0], 0, inf, n);
103         writeln(ans);
104     }
105     return 0;
106 }