Haokee Note

ABC347E Set Add Query

3 min read

前缀和

题目大意

给定 次操作，每一次操作都是往集合里添加一个数，如果已存在就删去这个数。每一次操作之后令集合大小为 ，那么所有 ， 都要加上 。

解法

我们发现，加入一个元素到集合里和删除这个元素使非常迅速的，而拖慢我们暴力思路的元凶是统计答案，如果一个元素一直在这个集合里出现的话我们每一次都要进行相加。

因此我们需要对集合数量做一个前缀和，然后找出每一个元素是什么时候进来、什么时候出去的，方便统计这个元素对答案的贡献，然后加入到答案数组里就行了。

对于元素 ， 时插入进去， 时删除掉，那么对答案 的贡献就是 。注意有些元素可能最后没有被删除，那么就需要进行特殊处理。

代码

#include <iostream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5;
 
LL idx[kMaxN], s[kMaxN], a[kMaxN], n, q, sz;
 
int main() {
  cin >> n >> q;
  for (LL i = 1, x; i <= q; i++) {
    cin >> x;
    if (!idx[x]) {                       // 如果没有出现
      idx[x] = i;                        // 记录出现的位置
      sz++;                              // 记录集合大小
    } else {                             // 如果已经出现过
      a[x] += s[i - 1] - s[idx[x] - 1];  // 计算贡献
      idx[x] = 0;                        // 删除这个数
      sz--;                              // 记录集合大小
    }
    s[i] = s[i - 1] + sz;                // 计算前缀和
  }
  for (LL i = 1; i <= n; i++) {          // 输出答案
    cout << a[i] + (idx[i] ? s[q] - s[idx[i] - 1] : 0) << ' ';
  }
  return 0;
}

Graph View