Codeforces 707E Garlands
2024-10-19 17:44:04
我怎么感觉好水啊。
因为询问只有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 ;
} /*
*/
最新文章
- 《JS设计模式笔记》构造函数和工厂模式创建对象
- 快速提升word文档编写质量
- A Simple C++ Template Class that Matches a String to a Wildcard Pattern
- vs2013 下载
- Spring自定义一个拦截器类SomeInterceptor,实现HandlerInterceptor接口及其方法的实例
- HDU 4930 Fighting the Landlords --多Trick,较复杂模拟
- MVC:上传文件
- scala 入门(2)--数组相关操作
- Keil MDK中使用pc-lint的详细方法
- USACO The Tamworth Two 模拟
- Android imageView图片按比例缩放
- 针对ie9写特殊的样式
- 2.Perl 多线程:Threads(线程返回值)
- POJ - 3062 Borg Maze
- 在windos 环境下安装
- Java学习笔记记录(一)
- HDOJ5551 Huatuo&#39;s Medicine
- MongoDB 数据恢复与导出
- LaTex in Markdown
- linux下fallocate快速创建大文件