SPOJ 10628(COT-树上第k大-函数式线段树) - c++编程基础

int size=unique(a2+1,a2+1+n)-(a2+1);a2_size=size;
For(i,size) h[a2[i]]=i;
For(i,n) w[i]=h[w[i]];
For(i,n-1)
{
int u,v;
scanf("%d%d",&u,&v);
addedge2(u,v);
}
bfs();
For(i,m)
{
int u,v,k;
scanf("%d%d%d",&u,&v,&k);
int f=lca(u,v);
ans[1]=root[u],ans[2]=root[v],ans[3]=root[f],ans[4]=root[father[f][0]];
ans_siz=4,ans_end=2;
int l=1,r=size;
while (l {
int m=l+r>>1,s;
if (k<=(s=getsum())) r=m,turn(0);else l=m+1,k-=s,turn(1);
}
printf("%d\n",a2[l]);

}

return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i #define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define MAXN (100000+10)
#define MAXM (200000+10)
#define Li (18)
int n,m,w[MAXN];
int edge[MAXM],next[MAXM]={0},pre[MAXN]={0},size=0;
void addedge(int u,int v)
{
edge[++size]=v;
next[size]=pre[u];
pre[u]=size;
}
void addedge2(int u,int v){addedge(u,v),addedge(v,u);}
struct node
{
int ch[2],c;
node(){ch[0]=ch[1]=c=0;}
}q[MAXN*Li];
int root[MAXN],tail=0;
void ins(int &x,int p,int l,int r,int c)
{
x=++tail;
if (p) q[x]=q[p];
q[x].c++;
if (l==r) return;
int m=(l+r)>>1;
if (c<=m) ins(q[x].ch[0],q[x].ch[0],l,m,c);
else ins(q[x].ch[1],q[x].ch[1],m+1,r,c);
}

map h;
int a2[MAXN],a2_size;

int d[MAXN],father[MAXN][Li]={0};
int q2[MAXN];
void bfs()
{
int head=1,tail=1;q2[1]=1;d[1]=1;ins(root[1],root[1],1,a2_size,w[1]);
while (head<=tail)
{
int x=q2[head++];
For(i,Li-1)
{
father[x][i]=father[father[x][i-1]][i-1];
if (!father[x][i]) break;
}
Forp(x)
{
int &v=edge[p];
if (d[v]) continue;
d[v]=d[x]+1;
father[v][0]=x;
q2[++tail]=v;
ins(root[v],root[x],1,a2_size,w[v]);
}
}
}
int bin[MAXN];
int lca(int u,int v)
{
if (d[u] int t=d[u]-d[v];
Rep(i,Li)
if (bin[i]&t) u=father[u][i];
int i=Li-1;
while (u^v)
{
while (i&&father[u][i]==father[v][i]) i--;
u=father[u][i],v=father[v][i];
}
return u;
}
int ans[MAXN],ans_siz=0,ans_end=0;
int getsum()
{
int tot=0;
For(i,ans_end) tot+=q[q[ans[i]].ch[0]].c;
Fork(i,ans_end+1,ans_siz) tot-=q[q[ans[i]].ch[0]].c;
return tot;
}
void turn(bool c)
{
For(i,ans_siz) ans[i]=q[ans[i]].ch[c];
}
int main()
{
// freopen("spoj10628_COT.in","r",stdin);
// freopen(".out","w",stdout);

bin[0]=1;
For(i,Li-1) bin[i]=bin[i-1]<<1;

scanf("%d%d",&n,&m);
For(i,n) scanf("%d",&w[i]),a2[i]=w[i];
sort(a2+1,a2+1+n);
int size=unique(a2+1,a2+1+n)-(a2+1);a2_size=size;
For(i,size) h[a2[i]]=i;
For(i,n) w[i]=h[w[i]];
For(i,n-1)
{
int u,v;
scanf("%d%d",&u,&v);
addedge2(u,v);
}
bfs();
For(i,m)
{
int u,v,k;
scanf("%d%d%d",&u,&v,&k);
int f=lca(u,v);
ans[1]=root[u],ans[2]=root[v],ans[3]=root[f],ans[4]=root[father[f][0]];
ans_siz=4,ans_end=2;
int l=1,r=size;
while (l {
int m=l+r>>1,s;
if (k<=(s=getsum())) r=m,turn(0);else l=m+1,k-=s,turn(1);
}
printf("%d\n",a2[l]);

}

return 0;
}

SPOJ 10628(COT-树上第k大-函数式线段树) (二)