音乐会节目单

音乐会节目单的题解

题意

Sub3 : \(k = 1\)

也就是说：给你一个数组，要求找出有多少段满足：有一个及以上的数出现一次

思路

Step 1 扫描线

固定 \(r\) ， 设 \(f_l\) 表示 \(l\) 到 \(r\) 之间有多少个只出现一次的数

预处理一个 \(last\) 数组， \(last_i\) 表示上一个值为 \(a_i\) 的编号

对于新的 \(r\) ，\(f\) 做如下更新

\((last_i, r]\)++, \((last_{last_i} last_i]\)--

显然，如果 \(last_i = -1\) ， 没有与 \(a_i\) 相同的

那么不进行 \((last_{last_i} last_i]\)-- 操作

Step 2 数据结构

等价于维护一个数据结构，实现区间修改， 求 \([1, r]\) 之间大于 \(0\) 的个数

不难想到分块

对于整块开一个桶和一个 \(tag\) 表示增量

散块暴力重构

旦整块怎么查询大于 \(0\) 的个数呢？

• 显然这道题可以用一个 \(cnt\) 在修改时动态维护

  因为每次修改只增加一个数

• 但是我懒为了使方法具有普适性

  使用树状数组维护值域，可以支持大范围修改

• 这里还有一个不用开桶的做法

  散块重构是sort，保证整块单调

  每次二分答案

• 好像可以用树套树做，空间应该是可以的

Step 3 时间复杂度 & 细节

卡时间

分析时间复杂度：最坏 \(O(n * \sqrt n * log(n))\)

\(n = 1e5\) 的情况下能达到 \(525242950\)

所以我被卡了 (原题2s可过，新题实现1s)

djx提供了神秘小技巧

将块长改为pow(n, 0.45)

竟顺利通过

卡空间

这道题一眼就是要开long long的

#define int long long是不好的习惯

否则会MLE得很惨，自己去看那些需要开

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, K = 600;

struct BIT {
	int tree[N];
	int lowbit(int x) {
		return x & - x;
	}
	long long sum(int x) {
		long long s = 0;
        x++;
        if(x <= 0) return 0;
		for(int i = x; i >= 1; i -= lowbit(i)) {
			s += tree[i];
		}
		return s;
	}
	void add(int x, int val) {
        x++;
        if(x <= 0) return;
		for(int i = x; i <= N; i += lowbit(i)) {
			tree[i] += val;
		}
	}
};

int n, k, problem_k;
int f[N], a[N], tag[K], last[N], t[N];
BIT b[K];
void change(int l, int r, int val) {
	int L = l / k, R = r / k;
	if(L == R) {
		for(int i = l; i <= r; i++) {
			b[i / k].add(f[i], -1);
			f[i] += val;
			b[i / k].add(f[i], 1);
		}
		return;
	}
	for(int i = l; i < (L + 1) * k; i++) {
		b[i / k].add(f[i], -1);
		f[i] += val;
		b[i / k].add(f[i], 1);
	} 
	for(int i = L + 1; i < R; i++) {
		tag[i] += val;
	} 
	for(int i = R * k ; i <= r; i++) {
		b[i / k].add(f[i], -1);
		f[i] += val;
		b[i / k].add(f[i], 1);
	} 
}
long long query(int l, int r) {
	int L = l / k, R = r / k;
	long long ret = 0;
	if(L == R) {
		for(int i = l; i <= r; i++) {
			ret += (f[i] + tag[i / k]) > 0;
		}
		return ret;
	}
	for(int i = l; i < (L + 1) * k; i++) {
		ret += (f[i] + tag[i / k]) > 0;
	} 
	for(int i = L + 1; i < R; i++) {
        int total = (i == (n - 1) / k) ? (n - i * k) : k;
        ret += total - b[i].sum(-tag[i]);
	} 
	for(int i = R * k ; i <= r; i++) {
		ret += (f[i] + tag[i / k]) > 0;
	} 
	return ret;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> problem_k;
	k = pow(n, 0.45);
    memset(t, -1, sizeof(t));
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		last[i] = t[a[i]];
		t[a[i]] = i;
        
        b[i / k].add(0, 1);
	}

	long long ans = 0;
	for(int r = 0; r < n; r++) {
		change(last[r] + 1, r, 1);
		if(last[r] != -1)
		change(last[last[r]] + 1, last[r], -1);
		ans += query(0, r);
	}
	cout << ans;
	return 0;
}