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

原理

tree

形态如图

Cx=i=x2k+1x2k+xAiC_x = \sum_{i=x-2^k+1}^{x-2^k+x}A_i
2k2^k为区间最小二次幂,即lowbit(x)

e.g. (8)10=(1000)2(8)_{10} = (1000)_2lowbit(8)=23lowbit(8) = 2^3
e.g. (10)10=(1010)2(10)_{10} = (1010)_2lowbit(10)=21lowbit(10) = 2^1

以区间的方式存储,可以方便的求和、维护(前缀和等)

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;
}

题目传送门