Codeforces 348C Subset Sums 分块思想
2024-09-01 15:10:16
题意思路:https://www.cnblogs.com/jianrenfang/p/6502858.html
第一次见这种思路,对于集合大小分为两种类型,一种是重集合,一种是轻集合,对于重集合,我们维护这个集合加上的和,已经集合的和。对于轻集合,我们直接暴力在序列上加上和,以及把这种加和对重集合的影响加上。
代码:
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 100010;
int cnt[maxn][350];
LL sum[maxn], add[maxn], a[maxn];
int mp[350], tot;
vector<int> s[maxn];
bool is_big[maxn];
int main() {
int n, m, x, y, T;
scanf("%d%d%d", &n, &m, &T);
int block = sqrt(n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= m; i++) {
scanf("%d", &x);
while(x--) {
scanf("%d", &y);
s[i].push_back(y);
}
sort(s[i].begin(), s[i].end());
if(s[i].size() >= block) {
mp[++tot] = i;
is_big[i] = 1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= tot; j++) {
int now = mp[j], l = 0, r = 0;
for (; l < s[i].size(); l++) {
while(r < s[now].size() && s[now][r] < s[i][l]) r++;
if(s[now][r] == s[i][l]) cnt[i][j]++;
}
}
}
for (int i = 1; i <= tot; i++)
for (int j = 0; j < s[mp[i]].size(); j++) {
sum[mp[i]] += a[s[mp[i]][j]];
}
char str[3];
while(T--) {
scanf("%s", str + 1);
if(str[1] == '+') {
scanf("%d %d", &x, &y);
if(is_big[x]) add[x] += y;
else {
for (int i = 0; i < s[x].size(); i++)
a[s[x][i]] += y;
for (int i = 1; i <= tot; i++)
sum[mp[i]] += (LL)cnt[x][i] * y;
}
} else {
LL ans = 0;
scanf("%d", &x);
if(is_big[x]) {
ans += sum[x];
for (int i = 1; i <= tot; i++) {
ans += add[mp[i]] * (LL)cnt[x][i];
}
printf("%lld\n", ans);
} else {
for (int i = 0; i < s[x].size(); i++) {
ans += a[s[x][i]];
}
for (int i = 1; i <= tot; i++)
ans += add[mp[i]] * (LL)cnt[x][i];
printf("%lld\n", ans);
}
}
}
}
最新文章
- 首师大附中互测题:LJX的校园:入学典礼【C003】
- ThinkPHP_SQL(1)查询语言
- java 编译时的初始化顺序
- Java虚拟机支持的最大内存限制
- 初始化css代码需要注意的
- linux ubuntu删除引导 grub出现错误解决方案
- SQL2008R2日志传送需要注意点
- TreeMap 排序
- Bye 14 Hello 15
- java Map使用Object 做为Key的问题
- Memcached基本架构和思想
- qrcode 4.0.4 : Python Package Index
- 正确释放Vector的内存
- CF Round#436 div2
- sublime如何实现函数折叠
- hex转mif文件 verilog
- 在vue项目中 获取容器的高度
- CSS3 Drop-Shadows效果制作教程分享
- 30-hadoop-hbase-安装squirrel工具
- 配置阿里云Docker镜像加速仓库