Garlands

我怎么感觉好水啊。

因为询问只有2000组, 离线询问, 枚举联通块再枚举询问, 二维树状数组更新答案。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); int n, m, k, q, cntq;
LL ans[N];
pair<PII, PII> qus[N];
bool on[N], can[N][N];
vector<pair<PII, int>> vc[N];
char op[]; struct Bit {
LL a[N][N];
void modify(int x, int y, int v) {
for(int i = x; i < N; i += i & -i)
for(int j = y; j < N; j += j & -j)
a[i][j] += v;
}
LL sum(int x, int y) {
LL ans = ;
for(int i = x; i; i -= i & -i)
for(int j = y; j; j -= j & -j)
ans += a[i][j];
return ans;
}
LL query(int x1, int y1, int x2, int y2) {
return sum(x2, y2) - sum(x2, y1 - ) - sum(x1 - , y2) + sum(x1 - , y1 - );
}
} bit; int main() {
scanf("%d%d%d", &n, &m, &k);
for(int i = ; i <= k; i++) {
int len; scanf("%d", &len);
for(int j = ; j <= len; j++) {
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
vc[i].push_back(mk(mk(x, y), w));
}
}
memset(on, true, sizeof(on));
scanf("%d", &q);
while(q--) {
scanf("%s", op);
if(op[] == 'A') {
cntq++;
scanf("%d%d", &qus[cntq].fi.fi, &qus[cntq].fi.se);
scanf("%d%d", &qus[cntq].se.fi, &qus[cntq].se.se);
memcpy(can[cntq], on, sizeof(on));
} else {
int x;
scanf("%d", &x);
on[x] = !on[x];
}
}
for(int i = ; i <= k; i++) {
for(auto& t : vc[i]) bit.modify(t.fi.fi, t.fi.se, t.se);
for(int j = ; j <= cntq; j++) {
if(!can[j][i]) continue;
ans[j] += bit.query(qus[j].fi.fi, qus[j].fi.se, qus[j].se.fi, qus[j].se.se);
}
for(auto& t : vc[i]) bit.modify(t.fi.fi, t.fi.se, -t.se);
}
for(int i = ; i <= cntq; i++) printf("%lld\n", ans[i]);
return ;
} /*
*/

最新文章

  1. 《JS设计模式笔记》构造函数和工厂模式创建对象
  2. 快速提升word文档编写质量
  3. A Simple C++ Template Class that Matches a String to a Wildcard Pattern
  4. vs2013 下载
  5. Spring自定义一个拦截器类SomeInterceptor,实现HandlerInterceptor接口及其方法的实例
  6. HDU 4930 Fighting the Landlords --多Trick,较复杂模拟
  7. MVC:上传文件
  8. scala 入门(2)--数组相关操作
  9. Keil MDK中使用pc-lint的详细方法
  10. USACO The Tamworth Two 模拟
  11. Android imageView图片按比例缩放
  12. 针对ie9写特殊的样式
  13. 2.Perl 多线程:Threads(线程返回值)
  14. POJ - 3062 Borg Maze
  15. 在windos 环境下安装
  16. Java学习笔记记录(一)
  17. HDOJ5551 Huatuo&#39;s Medicine
  18. MongoDB 数据恢复与导出
  19. LaTex in Markdown
  20. linux下fallocate快速创建大文件

热门文章

  1. ubuntu18.04使用sudo时反应时间长
  2. sql 把多列内容合并
  3. python的安装和pycharm的安装
  4. luogu P1627 [CQOI2009]中位数
  5. CF1009E [Intercity Travelling]
  6. jQuery - 几种异步提交方式
  7. Jetson tk1 刷机教程
  8. 一个有趣的小例子,带你入门协程模块-asyncio
  9. mac安装pyspider报错
  10. ubuntu 下抓包