首页 > 代码库 > Magic Board (codechef February 2013 Challenge)
Magic Board (codechef February 2013 Challenge)
题目链接 ： http://acm.bnu.edu.cn/v3/problem_show.php?pid=40517
这又是很不错的一道题目。
题意是给一个n*n(n <= 1e5)的矩阵，初始都为0，然后m(<=1e5)次操作，每次可以把一行或者一列全部标记为0或者1，或者询问某一行或者某一列有多少个0.
做法很巧妙，考虑到我如果查询第x行，那么的话我先找到前一次对x行操作的的时间点time_x，这样的话在time_x之前的所有操作对于x行都是无影响的，然后现在对于x行有影响的就只有在时间点time_x+1 到上一次操作所有对列的置1操作数或者置0操作数，这里假如先对y列进行了置1，后来又对y进行置0或者1操作的话需要把前一次操作的影响给去掉的，这样我们可以对于时间开一棵线段树/BIT，区间查询和单点修改就行了。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 using namespace std; 6 #define lson a, rt<<1, l, mid 7 #define rson a, rt<<1|1, mid+1, r 8 const int MAXN = 500005; 9 int O[2][MAXN<<2] = {0}, I[2][MAXN<<2] = {0};10 int ord[2][MAXN];11 int pre[2][MAXN];12 int n, m;13 14 void Up(int a[], int rt) {15 a[rt] = a[rt<<1] + a[rt<<1|1];16 }17 int query(int a[], int rt, int l, int r, int L, int R) {18 if (l >= L && r <= R) {19 return a[rt];20 }21 int mid = r + l >> 1, ret = 0;22 if (mid >= L) ret += query(lson, L, R);23 if (R > mid) ret += query(rson, L, R);24 return ret;25 }26 void update(int a[], int rt, int l, int r, int p, int c) {27 if (l == r) {28 a[rt] = c;29 return ;30 }31 int mid = r + l >> 1;32 if (mid >= p) update(lson, p, c);33 else update(rson, p, c);34 Up(a, rt);35 return ;36 }37 void init() {38 for (int i = 1; i <= n; i++) pre[0][i] = pre[1][i] = 0;39 for (int i = 1; i <= n; i++) ord[0][i] = ord[1][i] = 0;40 }41 42 int main() {43 scanf("%d%d", &n, &m);44 init();45 for (int q = 1; q <= m; q ++) {46 char op[11];47 int d, x, y, ret;48 scanf("%s", op);49 d = (op[0] == ‘R‘);50 if (op[3] == ‘Q‘) {51 scanf("%d", &x);52 if (ord[d][x] == 1) {53 ret = query(O[d^1], 1, 1, m, pre[d][x]+1, q);54 }else {55 ret = n - query(I[d^1], 1, 1, m, pre[d][x]+1, q);56 }57 printf("%d\n", ret);58 }else {59 scanf("%d%d", &x, &y);60 update(y == 1 ? I[d] : O[d], 1, 1, m, q, 1);61 if (ord[d][x] == 0) {62 if (pre[d][x] >= 1)update(O[d], 1, 1, m, pre[d][x], 0);63 }else {64 if (pre[d][x] >= 1)update(I[d], 1, 1, m, pre[d][x], 0);65 }66 ord[d][x] = y; pre[d][x] = q;67 }68 }69 return 0;70 }
Magic Board (codechef February 2013 Challenge)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。