题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1503
好奇怪呀!为什么而TLE?
各种修改终于卡时过了。可是大家比我快多了呀?难道是因为自己把相同节点弄成一个节点、记了一个cnt的缘故?
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=1e5+;
int n,c[N][],fa[N],siz[N],cnt[N],ans,tot,rt;
ll lm,val[N],fx;
void pushup(int k){siz[k]=siz[c[k][]]+siz[c[k][]]+cnt[k];}
//void insert(int &k,int f,ll s)
//{
// if(!k){k=++tot;siz[k]=1;cnt[k]=1;val[k]=s;fa[k]=f;return;}
// if(s==val[k]){cnt[k]++;siz[k]++;return;}
// int d=(s>val[k]);insert(c[k][d],k,s);
// pushup(k);
//}
void rotate(int x,int &k)
{
int y=fa[x],z=fa[y];
if(y==k)k=x;
else c[z][y==c[z][]]=x;
int d=(x==c[y][]);
fa[x]=z;fa[y]=x;fa[c[x][!d]]=y;//fa[x]=z在这里,不是43行
c[y][d]=c[x][!d];c[x][!d]=y;
pushup(y);pushup(x);
}
void splay(int x,int &k)
{
while(x!=k)
{
int y=fa[x],z=fa[y];
if(y!=k)
{
if((c[y][]==x)^(c[z][]==y))rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
void insert(ll s)
{
if(!rt){rt=++tot;siz[rt]=;cnt[rt]=;val[rt]=s;fa[rt]=;return;}
int z,p=rt;
while(p)
{
z=p;
siz[p]++;
if(s==val[p]){cnt[p]++;splay(p,rt);return;}//
p=c[p][s>val[p]];
}
p=++tot;cnt[p]=;siz[p]=;val[p]=s;
fa[p]=z;c[z][s>val[z]]=p;
splay(p,rt);//
}
int find(int k,ll s)
{
if(!k)return ;
if(val[k]==s)return k;
int d=(s>val[k]);
return find(c[k][d],s);
}
void del(ll s)
{
int k=find(rt,s);if(!k)return;//
if(k!=rt)splay(k,rt);
ans+=siz[c[k][]];
if(cnt[k]==)rt=c[k][];
else {
cnt[k]--;fa[c[k][]]=;c[k][]=;pushup(k);
}
}
ll query(int k,int s)
{
if(siz[c[k][]]<s&&siz[c[k][]]+cnt[k]>=s)return val[k];
if(siz[c[k][]]>=s)return query(c[k][],s);
else return query(c[k][],s-siz[c[k][]]-cnt[k]);//
}
int main()
{
scanf("%d%lld",&n,&lm);char ch;ll tp;
while(n--)
{
cin>>ch;scanf("%lld",&tp);
if(ch=='I')
{
if(tp-fx<lm)continue;
// else insert(rt,0,tp-fx);
else insert(tp-fx);
}
else if(ch=='A')fx+=tp,lm-=tp;
else if(ch=='S')
{
fx-=tp;lm+=tp;
// insert(rt,0,lm);
insert(lm);del(lm);
}
else {
if(tp>siz[rt])printf("-1\n");
else printf("%lld\n",query(rt,tp)+fx);
}
}
printf("%d",ans);
return ;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=1e5+;
int n,c[N][],fa[N],siz[N],cnt[N],ans,tot,rt;
ll lm,val[N],fx;
void pushup(int k){siz[k]=siz[c[k][]]+siz[c[k][]]+cnt[k];}
//void insert(int &k,int f,ll s)
//{
// if(!k){k=++tot;siz[k]=1;cnt[k]=1;val[k]=s;fa[k]=f;return;}
// if(s==val[k]){cnt[k]++;siz[k]++;return;}
// int d=(s>val[k]);insert(c[k][d],k,s);
// pushup(k);
//}
void rotate(int x,int &k)
{
int y=fa[x],z=fa[y];
if(y==k)k=x;
else c[z][y==c[z][]]=x;
int d=(x==c[y][]);
fa[x]=z;fa[y]=x;fa[c[x][!d]]=y;//fa[x]=z在这里,不是43行
c[y][d]=c[x][!d];c[x][!d]=y;
pushup(y);pushup(x);
}
void splay(int x,int &k)
{
while(x!=k)
{
int y=fa[x],z=fa[y];
if(y!=k)
{
if((c[y][]==x)^(c[z][]==y))rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
void insert(ll s)
{
if(!rt){rt=++tot;siz[rt]=;cnt[rt]=;val[rt]=s;fa[rt]=;return;}
int z,p=rt;
while(p)
{
z=p;
siz[p]++;
if(s==val[p]){cnt[p]++;splay(p,rt);return;}//
p=c[p][s>val[p]];
}
p=++tot;cnt[p]=;siz[p]=;val[p]=s;
fa[p]=z;c[z][s>val[z]]=p;
splay(p,rt);//
}
//int find(int k,ll s)
//{
// if(!k)return 0;
// if(val[k]==s)return k;
// int d=(s>val[k]);
// return find(c[k][d],s);
//}
//void del(ll s)
//{
// int k=find(rt,s);if(!k)return;//
// if(k!=rt)splay(k,rt);
// ans+=siz[c[k][0]];
// if(cnt[k]==1)rt=c[k][1];
// else {
// cnt[k]--;fa[c[k][0]]=0;c[k][0]=0;pushup(k);
// }
//}
int del(int &k,int f)
{
if(!k)return ;//
int rtn=;
if(val[k]<lm||(val[k]==lm&&cnt[k]==))
{
rtn=del(c[k][],k)+siz[c[k][]]+cnt[k];
siz[c[k][]]=siz[k]-rtn;
k=c[k][];fa[k]=f;
}
else{
if(val[k]==lm)cnt[k]--,rtn++;
rtn+=del(c[k][],k);
siz[k]-=rtn;
}
return rtn;
}
ll query(int k,int s)
{
if(siz[c[k][]]<s&&siz[c[k][]]+cnt[k]>=s)return val[k];
if(siz[c[k][]]>=s)return query(c[k][],s);
else return query(c[k][],s-siz[c[k][]]-cnt[k]);//
}
int main()
{
scanf("%d%lld",&n,&lm);char ch;ll tp;
while(n--)
{
cin>>ch;scanf("%lld",&tp);
if(ch=='I')
{
if(tp-fx<lm)continue;
// else insert(rt,0,tp-fx);
else insert(tp-fx);
}
else if(ch=='A')fx+=tp,lm-=tp;
else if(ch=='S')
{
fx-=tp;lm+=tp;
// insert(rt,0,lm);
insert(lm);
ans+=del(rt,)-;
}
else {
if(tp>siz[rt])printf("-1\n");
else printf("%lld\n",query(rt,tp)+fx);
}
}
printf("%d",ans);
return ;
}
可以非递归地 insert。
这两个的del方式不同。