| 记录编号 |
129562 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
1753.[HZOI 2014] 天使的小纸条 |
最终得分 |
100 |
| 用户昵称 |
ztx |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
6.594 s |
| 提交时间 |
2014-10-20 07:51:31 |
内存使用 |
14.83 MiB |
显示代码纯文本
/*
author :hzoi_ztx
title :情书密码
ALG :树状数组
comment:老天保佑 没有负数 !!!
[2014 10 18]
*/
#include <cstdio>
#include <cstring>
#include <map>
#define maxn 301
#define maxc 102
#define maxq 200010
#define maxt 490010
#define lowbit(x) x&(-x)
#define Inst 1
#define Qury 2
struct que{
int mode , a , b , c , d , next , p ;
} q[maxt] ; int tot = 0 ;
int n , m ;
int C[maxn][maxn] = {0} ;
int data[maxn][maxn] = {0} ;
int ans[maxq] = {0} ;
int cnt = 0 ;
int rec[maxq] = {0} ;
std::map<int,int>Fstar ;
std::map<int,int>Bstar ;
std::map<int,bool>exist ;
void exchange(int&x , int&y) {
if (x <= y) return ;
int t = x ; x = y ; y = t ;
}
void add(int c,int p) {
if (!Fstar[c]) {
Fstar[c] = p ;
Bstar[c] = p ;
}
else {
q[Bstar[c]].next = p ;
Bstar[c] = p ;
}
}
void insert(int x , int y , int d) {
for (int i = x ; i <= n ; i += lowbit(i) )
for (int j = y ; j <= m ; j += lowbit(j) )
C[i][j] += d ;
}
int query(int x , int y) {
int ret = 0 ;
for (int i = x ; i ; i -= lowbit(i) )
for (int j = y ; j ; j -= lowbit(j) )
ret += C[i][j] ;
return ret ;
}
void solve(int v) {
memset(C , 0 , sizeof(C)) ;
int p = Fstar[v] , tmp;
while (p) {
if (q[p].mode == Inst) insert(q[p].a , q[p].b , q[p].c) ;
else {
tmp = query(q[p].a-1,q[p].c-1)+query(q[p].b,q[p].d)-query(q[p].b,q[p].c-1)-query(q[p].a-1,q[p].d) ;
ans[q[p].p] = tmp ;
}
p = q[p].next ;
}
}
int main() {
#define READ
#ifdef READ
freopen("luvletter.in" ,"r",stdin ) ;
freopen("luvletter.out","w",stdout) ;
#endif
int i , j ;
scanf("%d%d", &m , &n ) ;
for (i = 1 ; i <= n ; i ++ ) {
for (j = 1 ; j <= m ; j ++ ) {
scanf("%d", &data[i][j] ) ;
if (!exist[data[i][j]]) {
rec[++rec[0]] = data[i][j] ;
exist[data[i][j]] = true ;
}
tot ++ ; q[tot].mode = Inst ;
q[tot].a = i ; q[tot].b = j ;
q[tot].c = 1 ;
add(data[i][j] , tot) ;
}
}
int Q , mm , a , b , c , v ;
scanf("%d", &Q ) ;
while ( Q -- ) {
scanf("%d", &mm ) ;
if (mm == Inst) {
scanf("%d%d%d", &a , &b , &c ) ;
if (!exist[c]) {
exist[c] = true ;
rec[++rec[0]] = c ;
}
tot ++ ;
q[tot].a = a ; q[tot].b = b ;
q[tot].c = 1 ; q[tot].mode = Inst ;
add(c , tot) ;
tot ++ ;
q[tot].a = a ; q[tot].b = b ;
q[tot].c = -1 ; q[tot].mode = Inst ;
add(data[a][b] , tot) ;
data[a][b] = c ;
}
else {
tot ++ ;
q[tot].mode = Qury ;
scanf("%d%d%d%d%d", &q[tot].a , &q[tot].b , &q[tot].c , &q[tot].d , &v ) ;
exchange(q[tot].a , q[tot].b) ;
exchange(q[tot].c , q[tot].d) ;
q[tot].p = ++ cnt ;
if (!exist[v]) {
ans[cnt] = 0 ;
tot -- ;
}
else add(v , tot) ;
}
}
Bstar.clear() ;
for (i = 1 ; i <= rec[0] ; i ++ ) {
j = rec[i] ;
solve(j) ;
}
for (i = 1 ; i <= cnt ; i ++ ) {
printf("%d\n", ans[i] ) ;
}
#ifdef READ
fclose(stdin ) ;
fclose(stdout) ;
#endif
return 0 ;
}