MXOJ Next Problem 3 Solution

题目

here

思路

询问离线和双树状数组解法还是太复杂了。

首先，题面的意思就是完全不用考虑糖果的顺序，只考虑每一个糖果种类的数量。

愤怒值的本质，就是分给一个小朋友的糖果数量减去种数。

但是，这种方法前人已经提过了，考虑换一个角度。

给 $k$ 个小朋友分糖果，本质上相当于最多有 $k$ 个同种糖果不会对答案产生贡献。

也就是说，令 $m=n+q$，$c_i$ 为目前第 $i$ 种糖果的个数，则所有糖果中最多有 $\sum_{i=1}^m \min(k,c_i)$ 个不对答案做贡献。

将糖果总数减去上述表达式的值即为答案。

解题方法

使用树状数组对 $\sum_{i=1}^m \min(k,c_i)$ 进行维护。

复杂度

时间复杂度

令 $m=n+q$。

每次增加、减少、查询时都需要对树状数组进行操作，故单次操作时间复杂度为 $O(\log m)$。

总时间复杂度 $O(q\log m)$。

空间复杂度

令 $m=n+q$。

最多可能有 $O(m)$ 个糖果，故树状数组的大小为 $O(m)$。

总空间复杂度 $O(m)$。

Code

#include <iostream>
using namespace std;
const int N = 2e6 + 10;
int n, q, op, x;
int tr[N], buc[N];
inline void update(int x, int y)
{
    for (; x < N; x += (x & -x))
        tr[x] += y;
}
inline int query(int x)
{
    int res = 0;
    for (; x; x -= (x & -x))
        res += tr[x];
    return res;
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        buc[x]++;
        update(buc[x], 1);
    }
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d", &op, &x);
        if (op == 3)
        {
            printf("%d\n", n - query(x));
            continue;
        }
        if (op == 1)
        {
            buc[x]++, n++;
            update(buc[x], 1);
            continue;
        }
        update(buc[x], -1);
        buc[x]--, n--;
    }
}

T2：催化剂

思路

我们能发现，对于每次查找，若有一种糖果类型的糖果数超过 $k$，则它一定会积累最终的答案。

所以，我们需要将每类糖果先给每个小朋友一个，其余的都给一个小朋友即可。

这样一来，问题就转变为了计算：

• $a$ 为糖果数量大于 $k$ 的糖果类型的总糖果数量有多少。
• $b$ 为糖果数量大于 $k$ 的糖果类型的糖果数量之和。
• $k$ 与题意相同。

解题方法

我们使用树状数组进行维护，一个负责找到超过 $k$ 的糖果类型有几个，另一个负责找到超过 $k$ 的糖果类型的总糖果数量有多少。

简单的说，一个在变动时只是 +1 和 -1 的变化，另一个则是 +x 和 -x 的变化。

Code

#include <bits/stdc++.h> 
#define ll long long
using namespace std;
long long n,m;
long long c[1000011*6],a;
ll p[1000011];
ll cs[1000011*6];
long long lowbit(long long x){
	return x&(-x);
}
long long getsun(long long x){
	if(!x) return 0;
	long long sum=0;
	for(long long i=x;i;i-=lowbit(i)) sum+=c[i];
	return sum;
}
void update(long long x,long long y){
	if(!x) return ;
	for(long long i=x;i<=2300000;i+=lowbit(i)){
		c[i]+=y;
	} 
}
long long lowbits(long long x){
	return x&(-x);
}
long long getsuns(long long x){
	if(!x) return 0;
	long long sum=0;
	for(long long i=x;i;i-=lowbits(i)) sum+=cs[i];
	return sum;
}
void updates(long long x,long long y){
	if(!x) return ;
	for(long long i=x;i<=2300000;i+=lowbits(i)){
		cs[i]+=y;
	} 
}
// 直接粘贴，懒
int main(){
	cin >>n >>m;
	for(long long i=1;i<=n;i++){
		ll x;
		scanf("%lld",&x);
		updates(p[x]+1,p[x]+1);
		update(p[x]+1,1);
		updates(p[x],-p[x]);
		update(p[x],-1);
		p[x]++;
	}
	while(m--){
		int op;
		scanf("%d",&op);
		if(op==1){
			long long x;
			scanf("%lld",&x);
			update(p[x]+1,1);
			updates(p[x]+1,p[x]+1);
			update(p[x],-1);
			updates(p[x],-p[x]);
			p[x]++;
		}else if(op==2){
			ll x;
			cin >>x;
			update(p[x],-1);
			updates(p[x],-p[x]);
			update(p[x]-1,1);
			updates(p[x]-1,p[x]-1);
			p[x]--;
		}else{
			long long x;
			scanf("%lld",&x);
			cout <<getsuns(2000000)-getsuns(x)-(getsun(2000000)-getsun(x))*x <<'\n';
		}
	}
	return 0;
}

S001B. 催化剂

$\mathsf{\color{Thistle}Statement}$

给定一个长度为 $n$ 的序列 $a$，$i$ 位置表示有一个种类为 $a_i$ 的糖果（$a_i$ 可以重复，即同一个种类有多个糖果），接下来有 $q$ 次查询：

• 1 x：表示种类 $x$ 多了 $1$ 个糖果
• 2 x：表示种类 $x$ 少了 $1$ 个糖果
• 3 k：输出将所有糖果分给 $k$ 个小朋友的最小愤怒值之和
  • 愤怒值：令第 $i$ 个小朋友所拥有的第 $j$ 种糖果的数量为 $b_{i,j}$，则愤怒值之和为 $\sum_{i=1}^k \sum_{j=1}^n \max(0,b_{i,j}-1)$

$\mathsf{\color{Thistle}Solution}$

若第 $i$ 种糖果的数量为 $c_i$，则对于 $k$ 个小朋友，最小愤怒值为 $\sum_{i=1}^n \max(0,c_i-k)$，其实就是每种糖果平均分给 $k$ 个小朋友，可以证明这是最优的。比如说：糖果为 $2,2,2,2,3,5,5$，$2$ 个小朋友，划分方案如下。

那么，问题转化为了动态求出现所有出现次数 $\ge k$ 的数的和 $-$ $k\times$ 出现次数 $\ge k$ 的数的个数。这个是可以通过平衡树来维护的，不过难写且麻烦。

不妨考虑将询问离线，对于一次更改，相当于对所有 $\le cnt$ 询问作统一的更改（$cnt$ 表示当前更改后该糖果种类的数量）。故，考虑将询问排序，每次更改通过树状数组实现即可。

$\mathsf{\color{Thistle}Code}$

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> q;
	int op, x;
	for (int i = 1; i <= n; i ++)
		cin >> x, opr[ ++ m] = {x, 1};
	while (q -- ) {
		cin >> op >> x;
		if (op == 1) opr[ ++ m] = {x, 1};
		else if (op == 2) opr[ ++ m] = {x, -1};
		else k ++, qry[k] = {x, k}, upd[m].push_back(k);
	}
	sort(qry + 1, qry + 1 + k);
	for (int i = 1; i <= k; i ++) pos[qry[i].se] = i;

	for (int i = 1; i <= m; i ++) {
		sum.add(lst[opr[i].fi], -tot[opr[i].fi]);
		tot[opr[i].fi] += opr[i].se;
		cnt.add(lst[opr[i].fi], -1);
		int l = 1, r = k, ans = -1;
		while (l <= r) {
			int mid = l + r >> 1;
			if (qry[mid].fi < tot[opr[i].fi]) l = mid + 1, ans = mid;
			else r = mid - 1;
		}
		if (ans == -1) lst[opr[i].fi] = 0;
		else lst[opr[i].fi] = k - ans + 1, sum.add(lst[opr[i].fi], tot[opr[i].fi]), cnt.add(lst[opr[i].fi], 1);
		for (auto v : upd[i])
			res[v] = sum.sum(k - pos[v] + 1) - qry[pos[v]].fi * cnt.sum(k - pos[v] + 1);
	}

	for (int i = 1; i <= k; i ++)
		cout << res[i] << endl;

	return 0;
}