牛客练习赛42 E.热爆了
2024-09-02 17:19:10
这可能是全场最长的一份代码
问的其实是对于关键点的斯坦纳树大小
考虑补集转化，不合法的点就是它的子树中没有关键点的点和斯坦纳树根的祖先
树根不难求，关键点中dfs序最大最小点的LCA就是了
问题在前者
假如我们把子树中的点拿出来排序，这个点不合法的条件就是存在ax,ax+1满足ax<=l-1且r+1<=ax+1，有个很妙的性质就是这个合法的x只有1个
考虑启发式合并把这个顺序搞出来，可以证明点数是nlogn级别的，因为每次合并均摊加入logn个点，合并n次。数列相邻的两项成为一个点，插入要用到一棵splay来维护一下。。。
把这些点放到二维平面二维数点即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int _=1e2;
const int maxn=1e5+_;
const int maxQ=5e5+_;
const int mbit=;
const int fbin=(<<)+_;
int read()
{
int x=,f=; char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=x*+ch-'',ch=getchar();
return x*f;
}
void write(int x)
{
if(x>=)write(x/);
putchar(x%+'');
}
int n,Q;
struct node
{
int x,y,next;
}a[*maxn];int len,last[maxn],d[maxn];
void ins(int x,int y)
{
len++;
a[len].x=x;a[len].y=y;
a[len].next=last[x];last[x]=len;
} //--------------------------------------------def------------------------------------------------------- namespace TREE
{
namespace Segtree
{
struct segtree{int mx,mn;segtree(){mn=(<<);}}tr[*fbin];
void update(int now)
{
int lc=(now<<),rc=(now<<|);
tr[now].mx=max(tr[lc].mx,tr[rc].mx);
tr[now].mn=min(tr[lc].mn,tr[rc].mn);
}
void pushdown(int now)
{
int lc=(now<<),rc=(now<<|);
tr[lc].mx=max(tr[now].mx,tr[lc].mx);
tr[rc].mn=min(tr[now].mn,tr[rc].mn);
}
void change(int now,int ql,int qr,int p,int k)
{
if(ql==qr)
{
tr[now].mx=max(tr[now].mx,k);
tr[now].mn=min(tr[now].mn,k);
return ;
}
int lc=(now<<),rc=(now<<|),mid=(ql+qr)/;
pushdown(now);
if(p<=mid)change(lc,ql,mid,p,k);
else change(rc,mid+,qr,p,k);
update(now);
}
int getmax(int now,int ql,int qr,int l,int r)
{
if(ql==l&&qr==r)return tr[now].mx;
int lc=(now<<),rc=(now<<|),mid=(ql+qr)/;
pushdown(now);
if(r<=mid) return getmax(lc,ql,mid,l,r);
else if(mid+<=l)return getmax(rc,mid+,qr,l,r);
else return max(getmax(lc,ql,mid,l,mid),getmax(rc,mid+,qr,mid+,r));
}
int getmin(int now,int ql,int qr,int l,int r)
{
if(ql==l&&qr==r)return tr[now].mn;
int lc=(now<<),rc=(now<<|),mid=(ql+qr)/;
pushdown(now);
if(r<=mid) return getmin(lc,ql,mid,l,r);
else if(mid+<=l)return getmin(rc,mid+,qr,l,r);
else return min(getmin(lc,ql,mid,l,mid),getmin(rc,mid+,qr,mid+,r));
}
}
//~~~~~~~~~~~~~~getnum~~~~~~~~~~~~~~~~~ int z,pos[maxn];
int dep[maxn],fa[mbit][maxn];
void dfs(int x,int fr)
{
pos[++z]=x;
Segtree::change(,,n,d[x],z);
for(int i=;(<<i)<=dep[x];i++)fa[i][x]=fa[i-][fa[i-][x]];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa[][x])
{
fa[][y]=x;
dep[y]=dep[x]+;
dfs(y,x);
}
}
}
int LCA(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=;i>=;i--)
if(dep[x]-dep[y]>=(<<i))x=fa[i][x];
if(x==y)return x;
for(int i=;i>=;i--)
if(dep[x]>=(<<i)&&fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];
return fa[][x];
}
int getnum(int l,int r)
{
return dep[LCA(pos[Segtree::getmax(,,n,l,r)],pos[Segtree::getmin(,,n,l,r)])];
}
//~~~~~~~~~~~~~~~make~~~~~~~~~~~~~~~~~ int ls[maxn],id[maxn];
bool cmp(int x,int y){return d[x]<d[y];}
int getl(int l){return lower_bound(ls+,ls+n+,l)-ls;}
int getr(int r){return upper_bound(ls+,ls+n+,r)-ls-;}
void LSH()
{
for(int i=;i<=n;i++)ls[i]=d[i],id[i]=i;
sort(ls+,ls+n+);
sort(id+,id+n+,cmp);
for(int i=;i<=n;i++)d[id[i]]=i;
}
//~~~~~~~~~~~~~~~~LSH~~~~~~~~~~~~~~~~ void main(){LSH();dfs(,);}
} //-------------------------------------------------------------------------------------------- namespace COUNT
{
namespace Chair
{
struct chairmantree
{
int lc,rc,c;
}tr[*maxn];int trlen,rt[maxn];
int insert(int x,int ql,int qr,int p,int c)
{
if(x==)x=++trlen;
tr[x].c+=c;
if(ql==qr)return x;
int mid=(ql+qr)/;
if(p<=mid)tr[x].lc=insert(tr[x].lc,ql,mid,p,c);
else tr[x].rc=insert(tr[x].rc,mid+,qr,p,c);
return x;
}
int merge(int x,int y)
{
if(x==||y==)return x+y;
tr[x].c+=tr[y].c;
tr[x].lc=merge(tr[x].lc,tr[y].lc);
tr[x].rc=merge(tr[x].rc,tr[y].rc);
return x;
}
int getsum(int now,int ql,int qr,int l,int r)
{
if(ql==l&&qr==r){return tr[now].c;}
int lc=tr[now].lc,rc=tr[now].rc,mid=(ql+qr)/;
if(r<=mid) return getsum(lc,ql,mid,l,r);
else if(mid+<=l)return getsum(rc,mid+,qr,l,r);
else return getsum(lc,ql,mid,l,mid)+getsum(rc,mid+,qr,mid+,r);
} void newid(int &x,int &y){x++,y=n+-y+;}
void paint(int x,int y,int c)
{
newid(x,y);
rt[x]=insert(rt[x],,n+,y,c);
}
int getnum(int x,int y)
{
newid(x,y);
return getsum(rt[x],,n+,,y);
}
void pre()
{
for(int i=;i<=n+;i++)
rt[i]=merge(rt[i],rt[i-]);
}
}
namespace Splay
{
struct splay
{
int f,son[];
int q,x,c,lazy;
}tr[*maxn];int trlen,rt[maxn],tot[maxn],id[**maxn],idtp;
void init(){for(int i=;i<*maxn;i++)id[i]=i;idtp=*maxn;}
void tap(int w){tr[rt[w]].c++,tr[rt[w]].lazy++;}
void rotate(int x,int w)
{
int f=tr[x].f,ff=tr[f].f;
int R,r; R=f,r=tr[x].son[w];
tr[R].son[-w]=r;
if(r!=)tr[r].f=R; R=ff,r=x;
if(tr[ff].son[]==f)tr[R].son[]=r;
else tr[R].son[]=r;
tr[r].f=R; R=x,r=f;
tr[R].son[w]=r;
tr[r].f=R;
}
void pushdown(int now)
{
int lc=tr[now].son[],rc=tr[now].son[];
tr[lc].c+=tr[now].lazy,tr[lc].lazy+=tr[now].lazy;
tr[rc].c+=tr[now].lazy,tr[rc].lazy+=tr[now].lazy;
tr[now].lazy=;
}
int tt,tmp[maxn];
void splay(int x,int F,int w)
{
int i=x; tt=;
while(i!=F)
tmp[++tt]=i,i=tr[i].f;
while(tt>)
{
if(tr[tmp[tt]].lazy!=)pushdown(tmp[tt]);
tt--;
} while(tr[x].f!=F)
{
int f=tr[x].f,ff=tr[f].f;
if(ff==F)
{
if(tr[f].son[]==x)rotate(x,);
else rotate(x,);
}
else
{
if(tr[ff].son[]==f&&tr[f].son[]==x)rotate(f,),rotate(x,);
else if(tr[ff].son[]==f&&tr[f].son[]==x)rotate(f,),rotate(x,);
else if(tr[ff].son[]==f&&tr[f].son[]==x)rotate(x,),rotate(x,);
else if(tr[ff].son[]==f&&tr[f].son[]==x)rotate(x,),rotate(x,);
}
}
if(F==)rt[w]=x;
}
//~~~~~~~~~~~~~~~~~~~~in~~~~~~~~~~~~~~~~~~~~~~ int findip(int w,int d)
{
int x=rt[w];
while()
{
pushdown(x);
int lc=tr[x].son[],rc=tr[x].son[];
if(d<tr[x].x)
{
if(lc==)return x;
x=lc;
}
else
{
if(rc==)return x;
x=rc;
}
}
}
int findqq(int x,int w)
{
splay(x,,w);
x=tr[x].son[];
while(tr[x].son[]!=)x=tr[x].son[];
return x;
}
int findhj(int x,int w)
{
splay(x,,w);
x=tr[x].son[];
while(tr[x].son[]!=)x=tr[x].son[];
return x;
}
//~~~~~~~~~~~~~~~~~~~find~~~~~~~~~~~~~~~~~~~~~~ void add(int x)
{
trlen++; if(trlen==**maxn)trlen=;
tr[id[trlen]].x=x;
tr[id[trlen]].c=,tr[id[trlen]].lazy=;
}
void insert(int w,int d)
{
tot[w]++;add(d);
if(rt[w]==)rt[w]=id[trlen];
else if(tot[w]==)
{
tr[rt[w]].son[]=id[trlen];
tr[id[trlen]].f=rt[w];
tr[id[trlen]].q=;
}
else
{
int p=findip(w,d);
if(d<tr[p].x)tr[p].son[]=id[trlen];
else tr[p].son[]=id[trlen];
tr[id[trlen]].f=p; tr[id[trlen]].q=tr[findqq(id[trlen],w)].x;
int h=findhj(id[trlen],w);splay(h,,w);
if(tr[h].c!=)Chair::paint(tr[h].q,tr[h].x,tr[h].c),tr[h].c=;
tr[h].q=tr[id[trlen]].x;
}
}
//~~~~~~~~~~~~~~~~~base~~~~~~~~~~~~~~~~~~~~~~~~ void dfs(int w,int x)
{
if(tr[x].c!=&&tr[x].x!=)Chair::paint(tr[x].q,tr[x].x,tr[x].c);
if(tr[x].x!=&&tr[x].x!=n+)
{
insert(w,tr[x].x);
id[idtp++]=x;
if(idtp==**maxn)idtp=;
}
pushdown(x);
if(tr[x].son[]!=)dfs(w,tr[x].son[]);
if(tr[x].son[]!=)dfs(w,tr[x].son[]);
}
void merge(int x,int y)
{
if(tot[x]<tot[y])swap(rt[x],rt[y]),swap(tot[x],tot[y]);
dfs(x,rt[y]);
}
void dfs2(int x)
{
if(tr[x].c!=&&tr[x].x!=)Chair::paint(tr[x].q,tr[x].x,tr[x].c);
pushdown(x);
if(tr[x].son[]!=)dfs2(tr[x].son[]);
if(tr[x].son[]!=)dfs2(tr[x].son[]);
}
void divi(){dfs2(rt[]);}
} void dfs(int x,int fr)
{
for(int k=last[x];k;k=a[k].next)
if(a[k].y!=fr)dfs(a[k].y,x);
Splay::insert(x,);
Splay::insert(x,n+);
Splay::insert(x,d[x]);
for(int k=last[x];k;k=a[k].next)
if(a[k].y!=fr)Splay::merge(x,a[k].y);
Splay::tap(x);
}
void main()
{
Splay::init();dfs(,);
Splay::divi();
Chair::pre();
}
} //-------------------------------------------------------------------------------------------- namespace QUERY
{
void main()
{
int l,r;
while(Q--)
{
l=read(),r=read();
l=TREE::getl(l);
r=TREE::getr(r);
if(l>r)puts("");
else write(n- (TREE::getnum(l,r)) - (COUNT::Chair::getnum(l-,r+)) ),putchar('\n');
}
}
} //-------------------------------------------------------------------------------------------- int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int x,y;
n=read(),Q=read();
for(int i=;i<=n;i++)d[i]=read();
for(int i=;i<n;i++)
{
x=read(),y=read();
ins(x,y),ins(y,x);
}
TREE::main();
COUNT::main();
QUERY::main(); return ;
}
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int _=1e2;
const int maxn=1e5+_;
const int maxQ=5e5+_;
const int mbit=;
const int fbin=(<<)+_;
int read()
{
int x=,f=; char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=x*+ch-'',ch=getchar();
return x*f;
}
void write(int x)
{
if(x>=)write(x/);
putchar(x%+'');
}
int n,Q;
struct node
{
int x,y,next;
}a[*maxn];int len,last[maxn],d[maxn];
void ins(int x,int y)
{
len++;
a[len].x=x;a[len].y=y;
a[len].next=last[x];last[x]=len;
} //--------------------------------------------def------------------------------------------------------- namespace TREE
{
namespace Segtree
{
struct segtree{int mx,mn;segtree(){mn=(<<);}}tr[*fbin];
void update(int now)
{
int lc=(now<<),rc=(now<<|);
tr[now].mx=max(tr[lc].mx,tr[rc].mx);
tr[now].mn=min(tr[lc].mn,tr[rc].mn);
}
void pushdown(int now)
{
int lc=(now<<),rc=(now<<|);
tr[lc].mx=max(tr[now].mx,tr[lc].mx);
tr[rc].mn=min(tr[now].mn,tr[rc].mn);
}
void change(int now,int ql,int qr,int p,int k)
{
if(ql==qr)
{
tr[now].mx=max(tr[now].mx,k);
tr[now].mn=min(tr[now].mn,k);
return ;
}
int lc=(now<<),rc=(now<<|),mid=(ql+qr)/;
pushdown(now);
if(p<=mid)change(lc,ql,mid,p,k);
else change(rc,mid+,qr,p,k);
update(now);
}
int getmax(int now,int ql,int qr,int l,int r)
{
if(ql==l&&qr==r)return tr[now].mx;
int lc=(now<<),rc=(now<<|),mid=(ql+qr)/;
pushdown(now);
if(r<=mid) return getmax(lc,ql,mid,l,r);
else if(mid+<=l)return getmax(rc,mid+,qr,l,r);
else return max(getmax(lc,ql,mid,l,mid),getmax(rc,mid+,qr,mid+,r));
}
int getmin(int now,int ql,int qr,int l,int r)
{
if(ql==l&&qr==r)return tr[now].mn;
int lc=(now<<),rc=(now<<|),mid=(ql+qr)/;
pushdown(now);
if(r<=mid) return getmin(lc,ql,mid,l,r);
else if(mid+<=l)return getmin(rc,mid+,qr,l,r);
else return min(getmin(lc,ql,mid,l,mid),getmin(rc,mid+,qr,mid+,r));
}
}
//~~~~~~~~~~~~~~getnum~~~~~~~~~~~~~~~~~ int z,pos[maxn];
int dep[maxn],fa[mbit][maxn];
void dfs(int x,int fr)
{
pos[++z]=x;
Segtree::change(,,n,d[x],z);
for(int i=;(<<i)<=dep[x];i++)fa[i][x]=fa[i-][fa[i-][x]];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa[][x])
{
fa[][y]=x;
dep[y]=dep[x]+;
dfs(y,x);
}
}
}
int LCA(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=;i>=;i--)
if(dep[x]-dep[y]>=(<<i))x=fa[i][x];
if(x==y)return x;
for(int i=;i>=;i--)
if(dep[x]>=(<<i)&&fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];
return fa[][x];
}
int getnum(int l,int r)
{
return dep[LCA(pos[Segtree::getmax(,,n,l,r)],pos[Segtree::getmin(,,n,l,r)])];
}
//~~~~~~~~~~~~~~~make~~~~~~~~~~~~~~~~~ int ls[maxn],id[maxn];
bool cmp(int x,int y){return d[x]<d[y];}
int getl(int l){return lower_bound(ls+,ls+n+,l)-ls;}
int getr(int r){return upper_bound(ls+,ls+n+,r)-ls-;}
void LSH()
{
for(int i=;i<=n;i++)ls[i]=d[i],id[i]=i;
sort(ls+,ls+n+);
sort(id+,id+n+,cmp);
for(int i=;i<=n;i++)d[id[i]]=i;
}
//~~~~~~~~~~~~~~~~LSH~~~~~~~~~~~~~~~~ void main(){LSH();dfs(,);}
} //-------------------------------------------------------------------------------------------- namespace COUNT
{
namespace Chair
{
struct chairmantree
{
int lc,rc,c;
}tr[*maxn];int trlen,rt[maxn];
int insert(int x,int ql,int qr,int p,int c)
{
if(x==)x=++trlen;
tr[x].c+=c;
if(ql==qr)return x;
int mid=(ql+qr)/;
if(p<=mid)tr[x].lc=insert(tr[x].lc,ql,mid,p,c);
else tr[x].rc=insert(tr[x].rc,mid+,qr,p,c);
return x;
}
int merge(int x,int y)
{
if(x==||y==)return x+y;
tr[x].c+=tr[y].c;
tr[x].lc=merge(tr[x].lc,tr[y].lc);
tr[x].rc=merge(tr[x].rc,tr[y].rc);
return x;
}
int getsum(int now,int ql,int qr,int l,int r)
{
if(ql==l&&qr==r){return tr[now].c;}
int lc=tr[now].lc,rc=tr[now].rc,mid=(ql+qr)/;
if(r<=mid) return getsum(lc,ql,mid,l,r);
else if(mid+<=l)return getsum(rc,mid+,qr,l,r);
else return getsum(lc,ql,mid,l,mid)+getsum(rc,mid+,qr,mid+,r);
} void newid(int &x,int &y){x++,y=n+-y+;}
void paint(int x,int y,int c)
{
newid(x,y);
rt[x]=insert(rt[x],,n+,y,c);
}
int getnum(int x,int y)
{
newid(x,y);
return getsum(rt[x],,n+,,y);
}
void pre()
{
for(int i=;i<=n+;i++)
rt[i]=merge(rt[i],rt[i-]);
}
}
namespace Splay
{
struct splay
{
int f,son[];
int q,x,c,lazy;
}tr[*maxn];int trlen,rt[maxn],tot[maxn],id[**maxn],idtp;
void init(){for(int i=;i<*maxn;i++)id[i]=i;idtp=*maxn;}
void tap(int w){tr[rt[w]].c++,tr[rt[w]].lazy++;}
void rotate(int x,int w)
{
int f=tr[x].f,ff=tr[f].f;
int R,r; R=f,r=tr[x].son[w];
tr[R].son[-w]=r;
if(r!=)tr[r].f=R; R=ff,r=x;
if(tr[ff].son[]==f)tr[R].son[]=r;
else tr[R].son[]=r;
tr[r].f=R; R=x,r=f;
tr[R].son[w]=r;
tr[r].f=R;
}
void pushdown(int now)
{
int lc=tr[now].son[],rc=tr[now].son[];
tr[lc].c+=tr[now].lazy,tr[lc].lazy+=tr[now].lazy;
tr[rc].c+=tr[now].lazy,tr[rc].lazy+=tr[now].lazy;
tr[now].lazy=;
}
int tt,tmp[maxn];
void splay(int x,int F,int w)
{
int i=x; tt=;
while(i!=F)
tmp[++tt]=i,i=tr[i].f;
while(tt>)
{
if(tr[tmp[tt]].lazy!=)pushdown(tmp[tt]);
tt--;
} while(tr[x].f!=F)
{
int f=tr[x].f,ff=tr[f].f;
if(ff==F)
{
if(tr[f].son[]==x)rotate(x,);
else rotate(x,);
}
else
{
if(tr[ff].son[]==f&&tr[f].son[]==x)rotate(f,),rotate(x,);
else if(tr[ff].son[]==f&&tr[f].son[]==x)rotate(f,),rotate(x,);
else if(tr[ff].son[]==f&&tr[f].son[]==x)rotate(x,),rotate(x,);
else if(tr[ff].son[]==f&&tr[f].son[]==x)rotate(x,),rotate(x,);
}
}
if(F==)rt[w]=x;
}
//~~~~~~~~~~~~~~~~~~~~in~~~~~~~~~~~~~~~~~~~~~~ int findip(int w,int d)
{
int x=rt[w];
while()
{
pushdown(x);
int lc=tr[x].son[],rc=tr[x].son[];
if(d<tr[x].x)
{
if(lc==)return x;
x=lc;
}
else
{
if(rc==)return x;
x=rc;
}
}
}
int findqq(int x,int w)
{
splay(x,,w);
x=tr[x].son[];
while(tr[x].son[]!=)x=tr[x].son[];
return x;
}
int findhj(int x,int w)
{
splay(x,,w);
x=tr[x].son[];
while(tr[x].son[]!=)x=tr[x].son[];
return x;
}
//~~~~~~~~~~~~~~~~~~~find~~~~~~~~~~~~~~~~~~~~~~ void add(int x)
{
trlen++; if(trlen==**maxn)trlen=;
tr[id[trlen]].x=x;
tr[id[trlen]].c=,tr[id[trlen]].lazy=;
}
void insert(int w,int d)
{
tot[w]++;add(d);
if(rt[w]==)rt[w]=id[trlen];
else if(tot[w]==)
{
tr[rt[w]].son[]=id[trlen];
tr[id[trlen]].f=rt[w];
tr[id[trlen]].q=;
}
else
{
int p=findip(w,d);
if(d<tr[p].x)tr[p].son[]=id[trlen];
else tr[p].son[]=id[trlen];
tr[id[trlen]].f=p; tr[id[trlen]].q=tr[findqq(id[trlen],w)].x;
int h=findhj(id[trlen],w);splay(h,,w);
if(tr[h].c!=)Chair::paint(tr[h].q,tr[h].x,tr[h].c),tr[h].c=;
tr[h].q=tr[id[trlen]].x;
}
}
//~~~~~~~~~~~~~~~~~base~~~~~~~~~~~~~~~~~~~~~~~~ void dfs(int w,int x)
{
if(tr[x].c!=&&tr[x].x!=)Chair::paint(tr[x].q,tr[x].x,tr[x].c);
if(tr[x].x!=&&tr[x].x!=n+)
{
insert(w,tr[x].x);
id[idtp++]=x;
if(idtp==**maxn)idtp=;
}
pushdown(x);
if(tr[x].son[]!=)dfs(w,tr[x].son[]);
if(tr[x].son[]!=)dfs(w,tr[x].son[]);
}
void merge(int x,int y)
{
if(tot[x]<tot[y])swap(rt[x],rt[y]),swap(tot[x],tot[y]);
dfs(x,rt[y]);
}
void dfs2(int x)
{
if(tr[x].c!=&&tr[x].x!=)Chair::paint(tr[x].q,tr[x].x,tr[x].c);
pushdown(x);
if(tr[x].son[]!=)dfs2(tr[x].son[]);
if(tr[x].son[]!=)dfs2(tr[x].son[]);
}
void divi(){dfs2(rt[]);}
} void dfs(int x,int fr)
{
for(int k=last[x];k;k=a[k].next)
if(a[k].y!=fr)dfs(a[k].y,x);
Splay::insert(x,);
Splay::insert(x,n+);
Splay::insert(x,d[x]);
for(int k=last[x];k;k=a[k].next)
if(a[k].y!=fr)Splay::merge(x,a[k].y);
Splay::tap(x);
}
void main()
{
Splay::init();dfs(,);
Splay::divi();
Chair::pre();
}
} //-------------------------------------------------------------------------------------------- namespace QUERY
{
void main()
{
int l,r;
while(Q--)
{
l=read(),r=read();
l=TREE::getl(l);
r=TREE::getr(r);
if(l>r)puts("");
else write(n- (TREE::getnum(l,r)) - (COUNT::Chair::getnum(l-,r+)) ),putchar('\n');
}
}
} //-------------------------------------------------------------------------------------------- int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int x,y;
n=read(),Q=read();
for(int i=;i<=n;i++)d[i]=read();
for(int i=;i<n;i++)
{
x=read(),y=read();
ins(x,y),ins(y,x);
}
TREE::main();
COUNT::main();
QUERY::main(); return ;
}
最新文章
- Execute Sql Task 的Result DataSet如何返回
- extjs combobox 事件
- CSUOJ_1000
- 手机卫士开发记录之json错误
- Tomcat Can't load AMD 64-bit .dll on a IA 32
- git rev-list
- 上下切换js
- 使用linq语句获取指定条数的记录
- HDU_1239——再次调用外星智慧
- JS实现图片翻书效果
- UVa 11879 - Multiple of 17
- python常用操作
- OSS Android SDK
- 【MySql】常用方法总结
- centos7安装配置jdk
- dedecms在后台替换文章标题、内容、摘要、关键字
- js验证身份证号，超准确
- Photoshop 基础五 橡皮擦工具
- ioctl函数详细说明（网络）
- 3D数学读书笔记——四元数