首页 > 代码库 > 用堆操作不断加入点来找到每个点对应所包含的值的个数的理解
用堆操作不断加入点来找到每个点对应所包含的值的个数的理解
首先还是要清楚一下堆操作的代码，毕竟线段树打多了，打堆的时候总会往线段树方向靠近
首先是建堆：
D=1;
for(;D<maxn+2;D<<=1);
然后给堆赋予值就可以了
查找区间段的和：
int query(int s,int t)
{
int i=D+s-1,j=D+t+1,ans=0;
for(;i^j^1;i>>=1,j>>=1){
if(~i&1) ans+=sum[i^1];
if(j&1) ans+=sum[j^1];
}
return ans;
}
更新操作：
void update(int i)
{
for(;i^1;i>>=1)
sum[i>>1]=sum[i]+sum[i^1];
}
之前也做了一道star level的题写成了博客，这里继续来写一遍，就是问对于一个星星的位置，比其x小于等于和y小于等于的点有多少个
这里我们所采取的是先进行一维上的排序，然后排好序后用另一维度来建树
如星星的题目已经以y的大小先后排好序了，那我们就省事了
我们从第一个节点不断添加进去，来找比它x小的数有几个，每次添加一个x，都要tree[D+x]++，再进行更新操作，因为后面的点是绝对不会影响到前面的点的
所以是可以这样做的：
第二题：
SPOJ RATING
这道题目也是两个维度，不过如果出现一样的值的话，者之间是不算谁比谁大的，这是跟星星不一样的地方
所以我们排好序后，每次添加点进入的时候还需要判断是否与前一个点值完全相同，如果相同不访问，直接继承前面一个点的值就可以了，然后再做更新
同时星星的点是题目本身按顺序给出的，而这里是乱序的，我们需要事先排好序然后不断添入点
我采取的方法是，建立结构体，除2维的数据外，还需记录id号，不然没法记录每个位置比别人大的个数
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define N 300005 6 int sum[N<<2],D,maxn; 7 struct Edge{ 8 int x,y,id; 9 bool operator<(const Edge &m)const10 {11 return x==m.x?y<m.y:x<m.x;12 }13 }e[N];14 void update(int i)15 {16 for(;i^1;i>>=1)17 sum[i>>1]=sum[i]+sum[i^1];18 }19 int query(int s,int t)20 {21 int i=D+s-1,j=D+t+1,ans=0;22 for(;i^j^1;i>>=1,j>>=1){23 if(~i&1) ans+=sum[i^1];24 if(j&1) ans+=sum[j^1];25 }26 return ans;27 }28 int main()29 {30 int n,ans[N];31 maxn=0;32 memset(sum,0,sizeof(sum));33 scanf("%d",&n);34 for(int i=0;i<n;i++){35 scanf("%d%d",&e[i].x,&e[i].y);36 maxn=max(maxn,e[i].y);37 e[i].id=i;38 }39 D=1;40 for(;D<maxn+2;D<<=1);41 sort(e,e+n);42 int k;43 for(int i=0;i<n;i++){44 if(i>1&&e[i].x==e[i-1].x&&e[i].y==e[i-1].y){45 }46 else{47 k=query(1,e[i].y);48 }49 ans[e[i].id]=k;50 sum[D+e[i].y]++;51 update(D+e[i].y);52 }53 for(int i=0;i<n;i++)54 printf("%d\n",ans[i]);55 return 0;56 }