台州网站建设方案优化,区块链app排名,用ps做美食网站,iis配置wordpress题目链接#xff1a; https://www.nowcoder.com/acm/contest/140/J 思路#xff1a; 都写在代码注释里了#xff0c;非常好懂。。 for_each函数可以去看一下#xff0c;遍历起vector数组比较方便#xff0c;用for(int i 0;i q[i].size();i)的话#xff0c;是会有一…题目链接 https://www.nowcoder.com/acm/contest/140/J 思路 都写在代码注释里了非常好懂。。 for_each函数可以去看一下遍历起vector数组比较方便用for(int i 0;i q[i].size();i)的话是会有一些弊端的虽然对于这道题应该没什么影响但最好规范下。 耗时2072ms 实现代码 #includebits/stdc.h
using namespace std;
const int M 1e65;
vectorintt[M];
int n,m;
vectorintbit[M];
int lowbit(int x){return x-x;
}struct node{int a,b,c,d;node(){}node(int a1,int b1,int c1,int d1):a(a1),b(b1),c(c1),d(d1){}
};struct node1{int i,j;node1(){}node1(int i1,int j1):i(i1),j(j1){}
};vectornode1k[M];
vectornodeq[M];void add(int x,int y,int z){for(int ix;in;ilowbit(i)){for(int jy;jm;jlowbit(j))bit[i][j]z;}
}
void update(int x1,int y1,int x2,int y2,int z){add(x1,y1,z);add(x21,y21,z);add(x1,y21,-z);add(x21,y1,-z);
}
int sum(int x,int y){int res0;for(int ix;i;i-lowbit(i)){for(int jy;j;j-lowbit(j)){resbit[i][j];}}return res;
}template class T
inline void scan_d(T ret)
{char c;ret 0;while ((c getchar()) 0 || c 9);while (c 0 c 9){ret ret * 10 (c - 0), c getchar();}
}template class T
inline void print_d(T x)
{if (x 9){print_d(x / 10);}putchar(x % 10 0);
}void fun1(node now){update(now.a,now.b,now.c,now.d,1);
}void fun2(node now){update(now.a,now.b,now.c,now.d,-1);
}int num;
void fun3(node1 now){if(sum(now.i,now.j)) num;
}int main()
{int t,x,a,b,c,d,z;scan_d(n); scan_d(m); scan_d(t);for(int i 1;i n;i ) bit[i].resize(m1); //预开空间for(int i 1;i n;i ) {for(int j 1;j m;j ){scan_d(x);k[x].push_back(node1(i,j)); //需要x种类药的花的坐标}}for(int i 1;i t;i ){scan_d(a);scan_d(b),scan_d(c),scan_d(d);scan_d(z);update(a,b,c,d,1); //标记代表这个区间被z种类药撒了q[z].push_back(node(a,b,c,d)); //存下z种类药一共撒了哪些区间}num 0;for(int i 1;i n*m;i ){ //遍历所有种类的药if(k[i].size()){ //存在需要ki种类药的花for_each(q[i].begin(),q[i].end(),fun2); //将ki种类药撒的区间造成的影响全部清0for_each(k[i].begin(),k[i].end(),fun3); //遍历需要k种类药的所有花的坐标如果这个坐标依旧为1那么代表撒在它上面的并不是k种类的药这朵花会死亡,num;for_each(q[i].begin(),q[i].end(),fun1); //再将ki种类药撒的区间还原}}print_d(num);printf(\n);return 0;
} 转载于:https://www.cnblogs.com/kls123/p/9350405.html
