poi 18 rod求助

常数优化后TLE只能说明您常数优化太弱了

表示我和LYP都轻松100pt啊..不明真相

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
typedef long long ll;
const int maxn=1000010;
const int max_nnode=maxn+maxn;
struct segment {
int cnt;
segment *l,*r;
segment(): cnt(1) {}
};
struct node {
int size;
bool flag;
node *l,*r,*f;
segment *tree;
node(): size(1),flag(0),l(0),r(0),f(0),tree(0) {}
};
int n,nnode;
ll ans=0;
node nodes[max_nnode];
inline int getint()
{
char c;
int res;
while(!isdigit(c=getchar()));
for(res=c-'0';isdigit(c=getchar());res=res*10+c-'0');
return res;
}
inline segment *new_tree(int pos)
{
segment *ret=new segment;
register segment *p=ret;
register int l=1,r=n,mid;
while(l<r)
{
mid=(l+r)>>1;
if(pos<=mid)
{
p->l=new segment;
p->r=NULL;
p=p->l; r=mid;
} else
{
p->r=new segment;
p->l=NULL;
p=p->r; l=mid+1;
}
}
p->l=p->r=NULL;
return ret;
}
ll sum;
segment *merge(segment *a,segment *b,int cntr)
{
if(!a) return b;
if(!b) sum+=(ll)cntr*a->cnt;
else
{
a->cnt+=b->cnt;
a->l=merge(a->l,b->l,cntr+((b->r)?b->r->cnt:0));
a->r=merge(a->r,b->r,cntr);
delete b;
}
return a;
}
void solve()
{
register node *cur=nodes+n+1;
while(cur)
{
if(cur-nodes<=n)
{
cur->tree=new_tree(cur-nodes);
for(cur=cur->f; cur->flag; cur=cur->f)
{
sum=0;
segment *a=cur->l->tree,*b=cur->r->tree;
ll cnt=(ll)a->cnt*b->cnt;
merge(cur->tree=a,b,0);
if(sum+sum>cnt) sum=cnt-sum;
ans+=sum;
}
cur->flag=true;
cur=cur->r;
} else cur=cur->l;
}
printf("%lld\n",ans);
}
int main()
{
nnode=n=getint();
register node *cur=nodes;
node *nd;
for(int i=1,p;i<n+n;++i)
{
if(p=getint())
{
nd=nodes+p;
if(cur->l) cur->r=nd;
else cur->l=nd;
nd->f=cur;
while(cur->r)
{
if(cur->l->size<cur->r->size) std::swap(cur->l,cur->r);
cur->size=cur->l->size+cur->r->size, cur=cur->f;
}
} else
{
node *nd=nodes+(++nnode);
if(cur->l) cur->r=nd;
else cur->l=nd;
nd->f=cur;
cur=nd;
}
}
solve();
return 0;
}
不知有哪位神犇能帮忙看一下？

兰州烧饼鉴定完毕TAT。用静态空间垃圾回收就可以了。。

Treap直接过吧。。。。。

平衡树启发式合并轻松过 +1

平衡树启发式合并轻松过+inf

1.3k暴力轻松过rod2