hdu5877 week pair

hdu5877 week pair

​​each test case, print a single integer on a single line denoting the number of weak pairs in the tree.Sample Input

1 2 3 1 2 1 2

Sample Output

1

注意0的情况，数据太水

其实我觉得用树状数组显然速度会更快一些

离散化 ，有点像统计逆序对的个数 注意upper_bound&lower_bound想清楚边界条件

相当于每次给这个位置离散化的地方+1然后统计比要求的答案（k/a[x]）小的有多少

#include#include#include#define N 110000using namespace std;inline long long read(){ long long x=0;int f=1;char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f;}struct node{ int y,next;}data[N];struct node1{ int l,r,left,right,sum;}tree[N<<2];long long ans,k;int a[N],root,num,h[N],in[N],n,aa[N],nn,T;void build(int &x,int l,int r){ x=++num;tree[x].l=l;tree[x].r=r;tree[x].left=tree[x].right=tree[x].sum=0; if (l==r) return; int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);}int query(int x,int l,int r){ if (l>r) return 0; if(l<=tree[x].l&&r>=tree[x].r) return tree[x].sum; int mid=tree[x].l+tree[x].r>>1;int tmp=0; if (l<=mid) tmp+=query(tree[x].left,l,r); if (r>mid) tmp+=query(tree[x].right,l,r);return tmp;}void insert1(int x,int l,int v){ if (!x) return;tree[x].sum+=v; if (tree[x].l==tree[x].r) return; int mid=tree[x].l+tree[x].r>>1; if(l<=mid) insert1(tree[x].left,l,v);else insert1(tree[x].right,l,v);}void dfs(int x){ if (!a[x]) ans+=query(root,1,nn);else ans+=query(root,1,upper_bound(aa+1,aa+nn+1,k/a[x])-aa-1); int tmp=lower_bound(aa+1,aa+nn+1,a[x])-aa; insert1(root,tmp,1); for (int i=h[x];i;i=data[i].next) dfs(data[i].y); insert1(root,tmp,-1);}int main(){ freopen("hdu5877.in","r",stdin); T=read(); while (T--){ n=read();k=read(); for (int i=1;i<=n;++i) a[i]=read(),aa[i]=a[i]; sort(aa+1,aa+n+1);nn=unique(aa+1,aa+n+1)-aa-1; memset(h,0,sizeof(h));num=0;memset(in,0,sizeof(in)); for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。