这是比较让我这个蒟蒻绝望的东西(以后可能一直这样)
原理

形态如图
为区间最小二次幂,即lowbit(x)
e.g. ,
e.g. ,
以区间的方式存储,可以方便的求和、维护(前缀和等)
lowbit的位运算
因为是求最小二次幂
所以是(~x+1)&x
,即(-x)&x
核心代码
//维护|构建
void build(int x)
{
while(x <= N)
{
c[x] += a[x];
x += lowbit(x);
}
}
//求和
int sum(int x)
{
int res = 0;
while(x > 0)
{
res += c[x];
x -= lowbit(x);
}
return res;
}
//求最小二次幂
int lowbit(int x)
{
return (-x) & x;
}
模版
#include<cstdio>
#include<algorithm>
#include<cstring>
#define Maxn 15000+10
#define Maxc 32000+10
using namespace std;
struct node{
int x, y;
}p[Maxn];
int n, m = 32001;
int c[Maxc], ans[Maxc];
int lowbit(int);
void build(int, int);
int sum(int);
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; ++i)
scanf("%d%d", &p[i].x, &p[i].y);
for(int i=1; i<=n; ++i)
{
int u = p[i].x+1; //树状数组无法维护下标0
int w = sum(u);
build(u, 1);
++ans[w];
}
for(int i=0; i<n; ++i)
printf("%d\n", ans[i]);
return 0;
}
int lowbit(int x)
{
return (-x) & x;
}
void build(int x, int y)
{
while(x <= m) //x范围不定,直接计算到最大
{
c[x] += y;
x += lowbit(x);
}
}
int sum(int x)
{
int res = 0;
while(x > 0)
{
res += c[x];
x -= lowbit(x);
}
return res;
}
题目传送门