[bzoj 3809] Gty的二逼妹子序列

长度为 n 的序列 a, m 个询问: a[l..r] 中权值∈[a,b]的权值的种类数. (1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^6, a[i]∈[1,n]且为整数, 每个测试点时限 4s, 空间 28MB) 线段树套平衡树, 维护区间内每种权值的出现次数及 Σ[出现次数 > 0]. 时间有点卡, 鉴于空间限制 28MB, 可以不予考虑了.

没有修改, 不强制在线, 莫队? 可以用树状数组, 每次转移 O(lg n), 很恐怖啊......

学习了一下题解, 用分块代替树状数组. 这样, 查询 O(n^0.5), 修改 O(1). 由于莫队算法有 O((n+m)n^0.5) 次转移, 总的时间复杂度仍然为 O((n+m)n^0.5). 常数小, 时限足, 于是可以 AC 了.

const int N = 1e5, M = 1e6, SIZE = 320;

int size;

struct Block
{
	int s[SIZE], v[N];
	void add(int i, int d)
	{
		v[i] += d, s[i/size] += d;
	}
	int query(int i, int j)
	{
		int l = i/size, r = j/size, ret = 0;
		if (l == r)
			rep (k, i, j+1) ret += v[k];
		else
		{
			rep (k, i, (l+1)*size) ret += v[k];
			rep (k, l+1, r) ret += s[k];
			rep (k, r*size, j+1) ret += v[k];
		}
		return ret;
	}
} B;

struct Query
{
	int k, l, r, a, b;
	bool operator<(const Query& o) const
	{
		return make_pair(l/size, r) < make_pair(o.l/size, o.r);
	}
} Q[M];

int a[N], c[N], ans[M];

void add(int i)
{
	if (c[i]++ == 0) B.add(i, 1);
}

void remove(int i)
{
	if (--c[i] == 0) B.add(i, -1);
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	size = sqrt(n);

	rep (i, 0, n) scanf("%d", a+i), --a[i];

	rep (i, 0, m)
	{
		scanf("%d%d%d%d", &Q[i].l, &Q[i].r, &Q[i].a, &Q[i].b);
		Q[i].k = i;
		--Q[i].l, --Q[i].r, --Q[i].a, --Q[i].b;
	}

	sort(Q, Q+m);

	int l = Q[0].l, r = l-1;
	
	rep (i, 0, m)
	{
		Query& q = Q[i];
		while (r < q.r) add(a[++r]);
		while (l > q.l) add(a[--l]);
		while (r > q.r) remove(a[r--]);
		while (l < q.l) remove(a[l++]);
		ans[q.k] = B.query(q.a, q.b);
	}

	rep (i, 0, m) printf("%d\n", ans[i]);

	return 0;
}