Description
Data Constraint
Solution
這是道資料結構的裸題。我們對于每一組分别維護兩個set，一個以體力為關鍵字，另一個以刷題量為關鍵字，再全局維護一個系統編号的set和一個維護每組刷題量最小值的set。對于加入操作，我們直接新開一個set就好。對于P操作，我們可以直接在該點所在的set中查找出資訊，并作修改。對于D操作，我們存兩個個數組表示每個組整體的體力和刷題量增減。對于E操作，直接找出該人所在組set中的資訊删去即可。對于M操作，我們可以用啟發式合并，将較小的set中的每個值取出，将之前記錄的整體體力、刷題量更新上去後再重新插入。T操作是我們可以在維護每組刷題量最小值的set中取出最小的，并在該點所在的set中删除刷題量相同的點的資訊。細節有點多。
Code
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
#define ll long long
using namespace std;
const ll maxn=+;
struct code{
ll x,id;
bool friend operator < (code x,code y){
return x.x<y.x || x.x==y.x && x.id<y.id;
}
}g,g1;
ll a[maxn],b[maxn],fa[maxn],size[maxn],bz[maxn],bz1[maxn],mi[maxn];
ll n,m,i,t,j,k,l,x,y,z,mx,p;
char ch;
multiset<code> f[maxn],f1[maxn],s;
set<code>:: iterator ii,it;
set<ll>::iterator is;
multiset<ll> c;
ll getfa(ll x){
return (fa[x]==x)?x:fa[x]=getfa(fa[x]);
}
void make(ll x){
g.x=mi[x];g.id=x;
ii=s.find(g);
if (ii!=s.end())s.erase(ii);
if (f1[x].begin()!=f1[x].end()){
g=*f1[x].begin();g.id=x;mi[x]=g.x=g.x+bz1[x];
s.insert(g);
}
}
void merge(){
z=getfa(x);k=getfa(y);
if (f[z].size()>f[k].size()) swap(x,y);
if (z==k) return;
z=getfa(x);k=getfa(y);fa[z]=k;t=f[z].size();
while (f[z].size()){
ii=f[z].end();ii--;g=*ii;
g1=g;a[g.id]=g.x=g.x-bz[z]+bz[k];b[g.id]=g1.x=b[g.id]+bz1[z]-bz1[k];
f[k].insert(g);f1[k].insert(g1);f[z].erase(ii);
size[k]+=g1.x+bz1[k];
}
g.x=mi[z];g.id=z;
ii=s.find(g);
s.erase(ii);
make(k);
}
void clear(ll x){
g1=*f1[x].begin();
while(f1[x].begin()!=f1[x].end()){
ii=f1[x].begin();g=*ii;
if (g.x!=g1.x) break;
size[x]-=bz1[x]+b[g.id];
f1[x].erase(ii);
g.x=a[g.id];f[x].erase(g);c.erase(g.id);
}
make(x);
}
int main(){
freopen("training.in","r",stdin);freopen("training.out","w",stdout);
scanf("%lld\n",&m);
while(m--){
scanf("%c",&ch);
if (ch=='J'){
scanf("%lld%lld",&g.x,&g1.x);
a[++mx]=g.x;b[mx]=g1.x;fa[mx]=mx;g.id=g1.id=mx;
f[mx].insert(g);f1[mx].insert(g1);
size[mx]=g1.x;
c.insert(mx);
mi[mx]=g1.x;make(mx);
}else if (ch=='P'){
scanf("%lld%lld%lld",&i,&x,&y);z=getfa(i);g.x=a[i];g1.x=b[i];g1.id=g.id=i;
ii=f[z].find(g);it=f1[z].find(g1);
g=*ii;g1=*it;
f[z].erase(ii);f1[z].erase(it);
if (a[i]>x+bz[z]){
g.x=a[i]=a[i]-x,f[z].insert(g);g1.x=b[i]=b[i]+y;
f1[z].insert(g1),size[z]+=y;
}else c.erase(i),size[z]-=b[i]+bz1[z];
make(z);
}else if (ch=='D'){
scanf("%lld%lld%lld",&i,&x,&y);z=getfa(i);bz[z]+=x;
while(f[z].size()){ii=f[z].begin();
g=*ii;
if (g.x>bz[z]) break;
size[z]-=bz1[z]+b[g.id];
f[z].erase(ii);g1.x=b[g.id];g1.id=g.id;
it=f1[z].find(g1);
f1[z].erase(it);c.erase(g.id);
}bz1[z]+=y;
size[z]+=f[z].size()*y;
make(z);
}else if (ch=='E'){
scanf("%lld",&i);z=getfa(i);
c.erase(i);g.x=a[i];g.id=i;
ii=f[z].find(g);
f[z].erase(ii);g.x=b[i];
ii=f1[z].find(g);f1[z].erase(ii);
size[z]-=b[i]+bz1[z];
make(z);
}else if (ch=='M'){
scanf("%lld%lld",&x,&y);merge();
}else if (ch=='C'){
if (c.begin()==c.end()) continue;
is=c.end();is--;
x=*c.begin();y=*is;
merge();
}else if (ch=='T'){
if (c.begin()==c.end()) continue;
g=*s.begin();t=g.x;
while(s.begin()!=s.end()){
g=*s.begin();
if (g.x!=t) break;
clear(g.id);
}
}else if (ch=='Q'){
scanf("%lld",&x);z=getfa(x);t=f[z].size();
printf("%lld %lld\n",t,size[z]);
}
scanf("\n");
}
}