多校联合 F Magic Ball Game （hdu 4605） (二)
1,1)>0)//如果已经存在x
{
ans[num][0]=-1;
}
else
{
int lma,lmi,rma,rmi;// 左边大于，左边小于，右边大于，右边小于
lmi=getsum(x-1,0);
lma=getsum(len,0)-getsum(x,0);
rmi=getsum(x-1,1);
rma=getsum(len,1)-getsum(x,1);
ans[num][0]=rmi;
ans[num][1]=3*(rmi+lmi)+rma+lma;
}
}
if(node[now].left!=-1)
{
addnum(w,1,0);
dfs(node[now].left);
addnum(w,-1,0);
}
if(node[now].right!=-1)
{
addnum(w,1,1);
dfs(node[now].right);
addnum(w,-1,1);
}
}
int main()
{
//freopen("dd.txt","r",stdin);
int ncase;
scanf("%d",&ncase);
while(ncase--)
{
int n,i,m,q,x,v;
scanf("%d",&n);
init(n);
for(i=1;i<=n;i++)
{
scanf("%d",&node[i].w);
po[i]=node[i].w;
}
scanf("%d",&m);
int a,b,cc;
memset(vis,0,sizeof(vis));
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&cc);
add(a,b,cc);
vis[b]=vis[cc]=1;
}
scanf("%d",&q);
for(i=1;i<=q;i++)
{
scanf("%d%d",&v,&x);
vec[v].push_back(x);
vec[v].push_back(i);
po[i+n]=x;
}
sort(po+1,po+q+n+1);
len=unique(po+1,po+q+n+1)-(po+1);
int root;
for(i=1;i<=n;i++)
{
if(!vis[i])
{
root=i;
break;
}
}
for(i=0;i<=len;i++)
c[i][0]=c[i][1]=0;
dfs(root);
for(i=1;i<=q;i++)
{
if(ans[i][0]==-1)
printf("0\n");
else
printf("%d %d\n",ans[i][0],ans[i][1]);
}
}
return 0;
}
#include
#include
#include
#include
#include
#define maxn 100010
#define mid ((t[p].l+t[p].r)>>1)
#define ls (p<<1)
#define rs (ls|1)
using namespace std;
struct Tree
{
int w;
int left,right;
}node[maxn];
vector vec[maxn];
int c[maxn<<1][2];
void init(int n)
{
for(int i=0;i<=n;i++)
{
vec[i].clear();
node[i].left=node[i].right=node[i].w=-1;
}
}
void add(int a,int b,int c)
{
node[a].left=b;
node[a].right=c;
}
int ans[maxn][2],vis[maxn],po[maxn<<1],len;
int lowbit(int x)
{
return x&(-x);
}
void addnum(int x,int val,int tt)
{
while(x<=len)
{
c[x][tt]+=val;
x+=lowbit(x);
}
}
int getsum(int x,int tt)
{
int sum=0;
while(x>0)
{
sum+=c[x][tt];
x-=lowbit(x);
}
return sum;
}
int search(int len,int x)
{
int mi=1,ma=len,Mid;
while(mi<=ma)
{
Mid=(mi+ma)>>1;
if(po[Mid]==x)
return Mid;
if(po[Mid]0||getsum(x,1)-getsum(x-1,1)>0)//如果已经存在x
{
ans[num][0]=-1;
}
else
{
int lma,lmi,rma,rmi;// 左边大于，左边小于，右边大于，右边小于
lmi=getsum(x-1,0);
lma=getsum(len,0)-getsum(x,0);
rmi=getsum(x-1,1);
rma=getsum(len,1)-getsum(x,1);
ans[num][0]=rmi;
ans[num][1]=3*(rmi+lmi)+rma+lma;
}
}
if(node[now].left!=-1)
{
addnum(w,1,0);
dfs(node[now].left);
addnum(w,-1,0);
}
if(node[now].right!=-1)
{
addnum(w,1,1);
dfs(node[now].right);
addnum(w,-1,1);
}
}
int main()
{
//freopen("dd.txt","r",stdin);
int ncase;
scanf("%d",&ncase);
while(ncase--)
{
int n,i,m,q,x,v;
scanf("%d",&n);
init(n);
for(i=1;i<=n;i++)
{
scanf("%d",&node[i].w);
po[i]=node[i].w;
}
scanf("%d",&m);
int a,b,cc;
memset(vis,0,sizeof(vis));
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&cc);
add(a,b,cc);
vis[b]=vis[cc]=1;
}
scanf("%d",&q);
for(i=1;i<=q;i++)
{
scanf("%d%d",&v,&x);
vec[v].push_back(x);
vec[v].push_back(i);
po[i+n]=x;
}
sort(po+1,po+q+n+1);
len=unique(po+1,po+q+n+1)-(po+1);
int root;
for(i=1;i<=n;i++)
{
if(!vis[i])
{
root=i;
break;
}
}
for(i=0;i<=len;i++)
c[i][0]=c[i][1]=0;
dfs(root);
for(i=1;i<=q;i++)
{
if(ans[i][0]==-1)
printf("0\n");
else
printf("%d %d\n",ans[i][0],ans[i][1]);
}
}
return 0;
}
| 评论 |
|
|