首页 > 代码库 > Codeforces 707 E. Garlands (二维树状数组)
Codeforces 707 E. Garlands (二维树状数组)
题目链接：http://codeforces.com/problemset/problem/707/E
给你nxm的网格，有k条链，每条链上有len个节点，每个节点有一个值。
有q个操作，操作ask问你一个子矩阵的和是多少，操作switch将第i条链上的值0变原来的数or原来的数变0。
比较明显的二维数组数组暴力，注意的是ask操作不会超过2000，所以在switch操作的时候不能进行update操作，否则会超时。所以你在ask操作的时候update就会省时。
复杂度大概是2000*2000*log2(2000)*log2*(2000)，cf上3s妥妥过。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 2e3 + 5;17 int n, m;18 LL bit[N][N];19 struct data {20 int x[N], y[N], w[N], len;21 }a[N];22 bool change[N];23 int flag[N];24 25 void update(int x, int y, LL val) {26 for(int i = x; i <= n; i += (i&-i)) {27 for(int j = y; j <= m; j += (j&-j)) {28 bit[i][j] += val;29 }30 }31 }32 33 LL sum(int x, int y) {34 LL s = 0;35 for(int i = x; i >= 1; i -= (i&-i)) {36 for(int j = y; j >= 1; j -= (j&-j)) {37 s += bit[i][j];38 }39 }40 return s;41 }42 43 int main()44 {45 int k, q;46 scanf("%d %d %d", &n, &m, &k);47 for(int i = 1; i <= k; ++i) {48 scanf("%d", &a[i].len);49 for(int j = 1; j <= a[i].len; ++j) {50 scanf("%d %d %d", &a[i].x[j], &a[i].y[j], &a[i].w[j]);51 update(a[i].x[j], a[i].y[j], (LL)a[i].w[j]);52 }53 }54 scanf("%d", &q);55 char query[10];56 int x1, y1, x2, y2, c;57 for(int i = 1; i <= q; ++i) {58 scanf("%s", query);59 if(query[0] == ‘A‘) {60 scanf("%d %d %d %d", &x1, &y1, &x2, &y2);61 for(int id = 1; id <= k; ++id) {62 if(change[id]) {63 if(flag[id] % 2) {64 for(int j = 1; j <= a[id].len; ++j) {65 update(a[id].x[j], a[id].y[j], (LL)a[id].w[j]);66 }67 } else {68 for(int j = 1; j <= a[id].len; ++j) {69 update(a[id].x[j], a[id].y[j], (LL)-a[id].w[j]);70 }71 }72 change[id] = change[id] ? false: true;73 ++flag[id];74 }75 }76 printf("%lld\n", sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1));77 } else {78 scanf("%d", &c);79 change[c] = change[c] ? false: true;80 }81 }82 return 0;83 }
Codeforces 707 E. Garlands (二维树状数组)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。