题意思路: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);
}
}
}
}

  

最新文章

  1. 首师大附中互测题:LJX的校园:入学典礼【C003】
  2. ThinkPHP_SQL(1)查询语言
  3. java 编译时的初始化顺序
  4. Java虚拟机支持的最大内存限制
  5. 初始化css代码需要注意的
  6. linux ubuntu删除引导 grub出现错误解决方案
  7. SQL2008R2日志传送需要注意点
  8. TreeMap 排序
  9. Bye 14 Hello 15
  10. java Map使用Object 做为Key的问题
  11. Memcached基本架构和思想
  12. qrcode 4.0.4 : Python Package Index
  13. 正确释放Vector的内存
  14. CF Round#436 div2
  15. sublime如何实现函数折叠
  16. hex转mif文件 verilog
  17. 在vue项目中 获取容器的高度
  18. CSS3 Drop-Shadows效果制作教程分享
  19. 30-hadoop-hbase-安装squirrel工具
  20. 配置阿里云Docker镜像加速仓库

热门文章

  1. Oracle Linux下使用sqlplus的edit命令
  2. 【转】java中JVM的原理
  3. day12 python函数名的应用 闭包 迭代器
  4. 启动ABP项目
  5. 【串线篇】SpringMVC九大组件
  6. excel acm 高校排名(hdoj)
  7. python3 实现简单ftp服务功能(服务端 For Linux)
  8. Spring中自动装配的模式
  9. 百度地图,删除marker,创建marker
  10. 如果全球的沙子都对你发起DDoS攻击,如何破?