#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; int n,m,cnt,tot,root[N]; ll ans1,ans2,ans3; char s[20]; struct node { int l,r,sum; }t[N*20]; //这题貌似开40会炸掉 struct Node { int id; int l,r,x; }ip[N*2]; //离线储存询问 vector<int> v; int getid(int x){ return lower_bound(v.begin(),v.end(),x)-v.begin()+1; } void update(int l,int r,int &x,int y,int pos) //更新主席树 { t[++cnt]=t[y],t[cnt].sum++,x=cnt; if(l==r) return ; int m=(l+r)/2; if(pos<=m) update(l,m,t[x].l,t[y].l,pos); if(pos>m) update(m+1,r,t[x].r,t[y].r,pos); } int query1(int l,int r,int x,int y,int k) //查询区间第k小 { if(l==r) return l; int s=t[t[y].l].sum-t[t[x].l].sum; int m=(l+r)/2; if(s>=k) return query1(l,m,t[x].l,t[y].l,k); else return query1(m+1,r,t[x].r,t[y].r,k-s); } int query2(int l,int r,int x,int y,int k) //查询k在当前区间排第几 { if(l==r) return t[y].sum-t[x].sum; int m=(l+r)/2; int g=t[t[y].l].sum-t[t[x].l].sum; if(k<=m) return query2(l,m,t[x].l,t[y].l,k); else return g+query2(m+1,r,t[x].r,t[y].r,k); } int main() { int kase=0; while(scanf("%d",&n)!=EOF) { cnt=0,tot=0,v.clear(); for(int i=1;i<=n;i++) //离线储存所有的询问 { scanf(" %s",s); if(s[0]=='I') { scanf("%d",&ip[i].x); v.push_back(ip[i].x); ip[i].id=1; } if(s[6]=='1') scanf("%d%d%d",&ip[i].l,&ip[i].r,&ip[i].x),ip[i].id=2; if(s[6]=='2') scanf("%d",&ip[i].x),ip[i].id=3; if(s[6]=='3') scanf("%d",&ip[i].x),ip[i].id=4; } sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end()); //离散化 int g=1; //记录序列的更新情况 tot=v.size(); //判断一共有多少个元素 ans1=0,ans2=0,ans3=0; for(int i=1;i<=n;i++) { if(ip[i].id==1) update(1,tot,root[g],root[g-1],getid(ip[i].x)),g++; //更新主席树 if(ip[i].id==2) ans1+=v[query1(1,tot,root[ip[i].l-1],root[ip[i].r],ip[i].x)-1]; //查询l r第k小 if(ip[i].id==3) ans2+=query2(1,tot,root[0],root[g-1],getid(ip[i].x)); //查询x在当前序列排第几 if(ip[i].id==4) ans3+=v[query1(1,tot,root[0],root[g-1],ip[i].x)-1]; //查询当前序列第k小 } printf("Case %d: ",++kase); printf("%lld %lld %lld ",ans1,ans2,ans3); } }