一道权值线段树的题，比较裸
代码：
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #include<vector> #include<cmath> #include<map> #include<set> #include<stack> #define INF 0x3f3f3f3f #define EXP 0.00000001 #define MOD 1000000007 #define MAXN 100005 #define PI acos(-1.0) #define ltree 2*id,ll,mid #define rtree 2*id+1,mid+1,rr #define mem(a) memset(a,0,sizeof(a)) typedef long long LL; using namespace std; int tree[1000005]; int add=0; int lazy[1000005]; char op[20]; void Pushdown(int id) { lazy[id]=0; lazy[id<<1]=lazy[id<<1|1]=1; tree[id<<1]=tree[id<<1|1]=0; } void Update(int id,int ll,int rr,int x,int v) { tree[id]+=v; int mid=(ll+rr)/2; if(ll==rr) return; if(lazy[id]) Pushdown(id); if(x<=mid) Update(ltree,x,v); else Update(rtree,x,v); } int Del(int id,int ll,int rr,int mi) { if(rr<=mi) { int res=tree[id]; tree[id]=0; lazy[id]=1; return res; } if(lazy[id]) Pushdown(id); int mid=(ll+rr)/2; int res=Del(ltree,mi); if(mid<=mi-1) res+=Del(rtree,mi); tree[id]-=res; return res; } int Kthmin(int id,int ll,int rr,int k) { if(ll==rr) return ll; if(lazy[id]) Pushdown(id); int mid=(ll+rr)/2; if(tree[id<<1]>=k) return Kthmin(ltree,k); else return Kthmin(rtree,k-tree[id<<1]); } int Rank(int id,int ll,int rr,int x) { if(ll>=x) return tree[id]; if(lazy[id]) Pushdown(id); int mid=(ll+rr)/2; int res=Rank(rtree,x); if(x<=mid) res+=Rank(ltree,x); return res; } int main() { //freopen("test6.in","r",stdin); //freopen("test6.out","w",stdout); int n; scanf("%d",&n); int ans=0; mem(tree); mem(lazy); add=0; while(n--) { int x; scanf("%s%d",&op,&x); if(op[0]=='I') Update(1,0,300000,x-add+100000,1); else if(op[0]=='A') add+=x; else if(op[0]=='D') ans+=Del(1,0,300000,x-add+100000); else if(op[0]=='M') { if(x>tree[1]) printf("-1\n"); else printf("%d\n",Kthmin(1,0,300000,x)+add-100000); } else { printf("%d\n",Rank(1,0,300000,x-add)); } } printf("%d\n",ans); return 0; }