UESTC 841 权值线段树

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
#define LL long long
const int N=1000010;
const int MAX=1e9+7;
int n,k;
struct Q
{
char c;
int a;
int b;
}q[N];
struct ha
{
int num;
int b;
int hao;
}a[N];
int len;
int d[N];
inline void R(int &v)//读入优化（必加，否则TLE）
{
v=0;
char ch=getchar();
int f=0;
while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
while(isdigit(ch)){v=(v<<3)+(v<<1)+ch-'0';ch=getchar();}
if(f) v=-v;
}
namespace ib {char b[100];}
inline void P(int x)//输出优化（必加，否则TLE）
{
if(x==0) {putchar(48); return;}
if(x<0) {putchar('-'); x=-x;}
char *s=ib::b;
while(x) *(++s)=x%10, x/=10;
while(s!=ib::b) putchar((*(s--))+48);
}
struct Segtree
{
struct trie
{
int l,r,len;
int sum;
int lz;
}tree[N<<2];
void updata(int o)//更新
{
tree[o].sum=tree[o<<1].sum+tree[o<<1|1].sum;
}
void build(int o,int l,int r)//建树
{
tree[o].sum=0;
tree[o].l=l;
tree[o].r=r;
tree[o].len=r-l+1;
if(l==r) {tree[o].sum=0;return;}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
updata(o);
}
void change(int o,int q,int v)//单点加
{
int l=tree[o].l,r=tree[o].r;
if(l==r) {tree[o].sum+=v;return;}
int mid=l+r>>1;
if(q<=mid) change(o<<1,q,v);
else change(o<<1|1,q,v);
updata(o);
}
int find(int o,int k)//线段树二分查找后缀和（必须为单调序列）
{
if(tree[o].l==tree[o].r) return tree[o].l;
int lo=o<<1,ro=o<<1|1;
if(tree[ro].sum>=k) return find(ro,k);
else return find(lo,k-tree[ro].sum);
}
}A;
void init()//初始化
{
len=0;
memset(d,0,sizeof(d));
memset(a,0,sizeof(a));
}
bool cmp(const ha &a,const ha &b)
{
return a.num<b.num;
}
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
int i,j;
while(scanf("%d",&n)!=EOF)
{
init();
scanf("%d",&k);
for(i=1;i<=n;++i)
{
scanf("n");
q[i].c=getchar();
if(q[i].c=='I')R(q[i].a),a[++len].num=q[i].a,a[len].hao=i;
}
sort(a+1,a+len+1,cmp);//离散化
int x=0;
for(i=1;i<=len;++i)
{
if(a[i].num!=a[i-1].num) x++;
a[i].b=x;
d[x]=a[i].num;//指向原数
q[a[i].hao].b=a[i].b;//指向离散化后的数
}
A.build(1,0,x);
for(i=1;i<=n;++i)
{
if(q[i].c=='I') A.change(1,q[i].b,1);
else
{
P(d[A.find(1,k)]);//寻找后缀和为k的点
puts("");
}
}
}
return 0;
}