xtuoj矩形

这道题的思路是：

1.将数据排序、去重、统计次数

2.分为正方形和普通矩形处理，其中普通矩形处理运用了二分求解的思想，通过枚举每一条边x，找到其对应的上值maxy与下值miny，则对这一x满足条件的y也就是矩形个数有right-left+1个，要注意正方形只能计一次，1&2和2&1是同一种，所以在找left和right的时候要加一个判断：left=left>i?left:i+1(left=i为正方形，前面已经计算过了，left<i会有1&2和2&1重复请款）

#include<stdio.h> #include<stdlib.h> #define maxn 100005 typedef long long ll; typedef struct { ll b; int count; }node; node nodes[maxn]; ll a[maxn]; int cmp(const void*a,const void*b){ return *(ll*)a-*(ll*)b; } int find(node*nodes,int m,ll target,int flag){ int l=0,r=m-1,re=flag?m:-1; while(l<=r){ int mid=(l+r)/2; if(flag){ if(nodes[mid].b>=target){ re=mid; r=mid-1; } else l=mid+1; } else{ if(nodes[mid].b<=target){ re=mid; l=mid+1; } else r=mid-1; } }return re; } int main(){ int n; ll l,r; scanf("%d %lld %lld",&n,&l,&r); for(int i=0;i<n;i++){ scanf("%lld",&a[i]); } qsort(a,n,sizeof(ll),cmp); int m=0; for(int i=0;i<n;i++){ if(i==0||a[i]!=a[i-1]){ nodes[m].b=a[i]; nodes[m].count=1; m++; } else nodes[m-1].count++; } ll re=0; for(int i=0;i<m;i++){ ll x=nodes[i].b; if(nodes[i].count>=2&&x*x<=r&&x*x>=l)re++; } for(int i=0;i<m;i++){ ll x=nodes[i].b; ll miny=(l+x-1)/x; ll maxy=r/x; if(miny>maxy)continue; int left=find(nodes,m,miny,1); left=left>i?left:i+1; int right=find(nodes,m,maxy,0); if(left<=right)re+=(right-left+1); } printf("%lld\n",re); return 0; }