Description
“我希望能使用更多的魔法。不對，是預定能使用啦。最終我要被大家稱呼為大魔法使。為此我決定不惜一切努力。”
——《The Grimoire of Marisa》霧雨魔理沙
魔理沙一如既往地去帕秋莉的大圖書館去借魔導書(Grimoire) 來學習魔道。
最開始的時候，魔理沙只是一本一本地進行研究。然而在符卡戰中，魔理沙還是戰不過帕秋莉。
好在魔理沙對自己的借還和研究結果進行了記錄，從而發現了那些魔導書的精妙之處。
帕秋莉的那些魔導書，每本都有一個類別編號ti 和威力大小pi。而想要獲得最有威力的魔法，就必須同時研究一些魔導書。而研究的這些魔導書就必須要滿足，類別編號為T 的書的本數小于等于T，并且總共的本數小于等于一個給定的數N。而研究這些魔導書之后習得的魔法的威力就是被研究的魔導書的威力之和。
為了擊敗帕秋莉，魔理沙想要利用自己發現的規律來獲得最有威力的魔法。
她列出了計劃中之后M 次的借還事件，并想要知道每個事件之后自己所能獲得的魔法的最大威力。可她忙于魔法材料——蘑菇的收集，于是這個問題就交給你來解決了。

Input
輸入文件grimoire.in。
第1 行2 個整數N,M，分別表示魔理沙能研究的魔導書本數的上限和她的借還事件數。
之后M 行，每行的形式為“op t p”（不含引號）。Op 為“BORROW” 或“RETURN”，分別表示借書和還書。T 為一個整數，表示這本書的類別編號。P為一個整數，表示這本書的威力大小。注意，還書時如果有多本書滿足類別編號為t，威力大小為p，這表明這些書都是相同的，魔理沙會任選其中一本書還回去。如果你問我為何會有相同的書，多半因為這是魔導書吧。

Output
輸出文件grimoire.out。
一共M 行，每行一個整數，即每個事件之后的最大威力。

Sample Input
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

Sample Output
5811
10843
5811
11361
14847
9036
3486
8602
18165
18259

Data Constraint
對于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” 操作。這部分數據均勻分布。
.
.
.
.
.

程序：

#include <iostream> #include <cstdlib> #include <cstdio> #define fo(a,b,c) for (a=b; a<=c; a++) #define fd(a,b,c) for (a=b; a>=c; a--) #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) #define Len 1000000000 using namespace std;long long tr[20000001][5]; int n,m,i,j,k,l,x,y,len,S,S2; char s[20]; long long ans;void New(int t,int x) {if (!tr[t][x])tr[t][x]=++len; }void change(int t,int l,int r,int x,int s) {int mid=(l+r)/2;tr[t][2]+=s;if (tr[t][2]<0)cout<<tr[t][2]<<endl;tr[t][3]+=s*x;if (l==r){if (tr[t][2])tr[t][4]=x;elsetr[t][4]=0;return;}if (x<=mid){New(t,0);change(tr[t][0],l,mid,x,s);}else{New(t,1);change(tr[t][1],mid+1,r,x,s);}tr[t][4]=max(tr[tr[t][0]][4],tr[tr[t][1]][4]); }void get(int t,int l,int r,long long k) {int mid=(l+r)/2;if (l==r){ans+=(long long)min(k,tr[t][2])*l;return;}if (tr[tr[t][1]][2]<=k){ans+=tr[tr[t][1]][3];if (tr[tr[t][0]][2] && k>tr[tr[t][1]][2])get(tr[t][0],l,mid,k-tr[tr[t][1]][2]);}else{if (tr[tr[t][1]][2])get(tr[t][1],mid+1,r,k);} }void Get(int t,int l,int r,int x,int y) {int mid=(l+r)/2;if (x<=l && r<=y){S+=tr[t][2];return;}if (x<=mid && tr[tr[t][0]][2])Get(tr[t][0],l,mid,x,y);if (mid<y && tr[tr[t][1]][2])Get(tr[t][1],mid+1,r,x,y); }void find(int t,int l,int r,int k) {int mid=(l+r)/2;if (l==r){if (k<=tr[t][2])S2=l;return;}if (tr[tr[t][1]][2]<k){if (tr[tr[t][0]][2])find(tr[t][0],l,mid,k-tr[tr[t][1]][2]);}else{if (tr[tr[t][1]][2])find(tr[t][1],mid+1,r,k);} }int main() {freopen("grimoire.in","r",stdin);freopen("grimoire.out","w",stdout);scanf("%d%d",&n,&m);len=300001;fo(i,1,m){scanf("%s%d%d",s,&x,&y);if (s[0]=='B'){change(x,1,Len,y,1);S=0;Get(x,1,Len,y,Len);if (S<=x){change(300001,1,Len,y,1);S2=0;find(x,1,Len,x+1);if (S2)change(300001,1,Len,S2,-1);}}else{S=0;Get(x,1,Len,y,Len);change(x,1,Len,y,-1);if (S<=x){change(300001,1,Len,y,-1);S2=0;find(x,1,Len,x);if (S2)change(300001,1,Len,S2,1);}}ans=0;get(300001,1,Len,n);printf("%lld\n",ans);}fclose(stdin);fclose(stdout);return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/9499926.html

總結

以上是生活随笔為你收集整理的【NOIP2015模拟10.27】魔道研究的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。