structHeal
{
priority_queue<int> real;
priority_queue<int> stack;
void push(int x){
real.push(x);
}
void pop(int x){
stack.push(x);
}
int top(){
while(real.empty()==&&stack.empty()==&&real.top()==stack.top())
real.pop(),stack.pop();
if(real.empty())return0;
return real.top();
}
}
这样打堆虽然方便但是top到最后大约有6，7的常数。
今天考试卡常卡的怀疑人生……..这个故事告诉我们千万不要忘了常数分析..........
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<ctime>
#include<iostream>
#define MAXN 1000010
using namespace std;
inline int read()
{
int sum=;
char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<='')
{
sum=(sum<<)+(sum<<)+ch-'';
ch=getchar();
}
return sum;
}
struct ScapeGoat_Tree
{
struct node
{
node *ch[];
int key,size,cover,ex;
void update()
{
size=ch[]->size+ch[]->size+ex;
cover=ch[]->cover+ch[]->cover+;
}
bool bad()
{
return ch[]->cover>=cover*0.756+||ch[]->cover>=cover*0.756+;
}
}Mem[MAXN],*null,*root,*stack[MAXN],*lst[MAXN];
int len,top;
void Init()
{
root=null=Mem;
null->size=null->cover=null->ex=;
null->ch[]=null->ch[]=Mem;
for(int i=;i<MAXN;i++)stack[++top]=Mem+i;
}
node *New(int key)
{
node *t=stack[top--];
t->ch[]=t->ch[]=null;
t->size=t->cover=t->ex=;
t->key=key;
return t;
}
void travel(node *p)
{
if(p==null)return;
travel(p->ch[]);
if(p->ex)lst[++len]=p;
else stack[++top]=p;
travel(p->ch[]);
}
node *divide(int l,int r)
{
if(l>r)return null;
int mid=(l+r)>>;
lst[mid]->ch[]=divide(l,mid-);
lst[mid]->ch[]=divide(mid+,r);
lst[mid]->update();
return lst[mid];
}
void rebuild(node *&p)
{
len=;
travel(p);
p=divide(,len);
}
node **insert(node *&p,int key)
{
if(p==null)
{
p=New(key);
return &null;
}
p->size++;
p->cover++;
node **ret=insert(p->ch[p->key<=key],key);
if(p->bad())ret=&p;
return ret;
}
void erace(node *p,int k)
{
p->size--;
if(p->ex&&k==p->ch[]->size+)
{
p->ex=;
return;
}
if(k<=p->ch[]->size)erace(p->ch[],k);
else erace(p->ch[],k-p->ch[]->size-p->ex);
}
int Kth(int k)
{
node *p=root;
while(p!=null)
{
if(p->ex&&k==p->ch[]->size+)return p->key;
else if(p->ch[]->size>=k)p=p->ch[];
else k-=p->ch[]->size+p->ex,p=p->ch[];
}
}
int Rank(int x)
{
node *p=root;
int ret=;
while(p!=null)
if(p->key>=x)
p=p->ch[];
else
ret+=p->ch[]->size+p->ex,p=p->ch[];
return ret;
}
void Insert(int x)
{
node **p=insert(root,x);
if(*p!=null)rebuild(*p);
}
void Erace_kth(int k)
{
erace(root,k);
if(root->size<root->cover*0.756)rebuild(root);
}
void Erace(int x)
{
Erace_kth(Rank(x));
}
}YY;
inline int Max(int x,int y)
{
return x>y?x:y;
}
inline int Abs(int x)
{
return x<?-x:x;
}
int n,m;
struct Tr
{
int to,next,w;
}c[MAXN<<];
int head[MAXN],t;
int f[MAXN];
inline void add(int x,int y,int z)
{
c[++t].to=y;
c[t].w=z;
c[t].next=head[x];
head[x]=t;
}
int A[MAXN];
bool mark[MAXN];
int q[MAXN],top,tail,one,two;
inline void bfs1()
{
memset(mark,,sizeof(mark));
memset(A,,sizeof(A));
q[]=;
top=tail=;
int now=;
one=;
mark[]=;
while(top<=tail)
{
int x=q[top++];
if(A[x]>now)
{
one=x;
now=A[x];
}
for(int i=head[x];i;i=c[i].next)
if(mark[c[i].to]==)
{
mark[c[i].to]=;
q[++tail]=c[i].to;
A[c[i].to]=A[x]+c[i].w;
}
}
}
inline void bfs2()
{
memset(mark,,sizeof(mark));
memset(A,,sizeof(A));
q[]=one;
top=tail=;
int now=;
two=one;
mark[one]=;
while(top<=tail)
{
int x=q[top++];
if(A[x]>now)
{
two=x;
now=A[x];
}
for(int i=head[x];i;i=c[i].next)
if(mark[c[i].to]==)
{
mark[c[i].to]=;
q[++tail]=c[i].to;
A[c[i].to]=A[x]+c[i].w;
}
}
}
inline void bfs3()
{
memset(mark,,sizeof(mark));
memset(A,,sizeof(A));
q[]=one;
top=tail=;
mark[one]=;
while(top<=tail)
{
int x=q[top++];
for(int i=head[x];i;i=c[i].next)
if(mark[c[i].to]==)
{
mark[c[i].to]=;
q[++tail]=c[i].to;
A[c[i].to]=A[x]+c[i].w;
}
}
}
int B[MAXN];
inline void bfs4()
{
memset(mark,,sizeof(mark));
q[]=two;
top=tail=;
mark[two]=;
while(top<=tail)
{
int x=q[top++];
for(int i=head[x];i;i=c[i].next)
if(mark[c[i].to]==)
{
mark[c[i].to]=;
q[++tail]=c[i].to;
B[c[i].to]=B[x]+c[i].w;
}
}
}
inline void Init()
{
n=read(),m=read();
m=Abs(m);
YY.Init();
for(int i=;i<=n;i++)
{
int x=read(),y=read();
add(x,i,y);
add(i,x,y);
}
bfs1(),bfs2(),bfs3(),bfs4();
for(int i=;i<=n;i++)A[i]=Max(A[i],B[i]);
}
inline bool jud(int p)
{
int x=YY.Kth(),y=YY.Kth(YY.root->size);
if(Abs(x-p)>m||Abs(y-p)>m)return ;
return ;
}
inline void work()
{
top=;
int ans=;
YY.Insert(A[]);
for(int i=;i<=n;i++)
{
while(top!=i&&!jud(A[i]))
YY.Erace(A[top]),top++;
YY.Insert(A[i]);
ans=Max(ans,YY.root->size);
}
printf("%d",ans);
}
int main()
{
//freopen("race.in","r",stdin);
//freopen("race.out","w",stdout);
Init();
work();
return ;
}