首页 > 代码库 > POJ2155 Matrix
POJ2155 Matrix
题解:
二维IUPQ题目
注意1点,不是直接在add时不是直接^=1,而是统计转换次数,这样在计算才能sum
代码:
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>#include<set>using namespace std;using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)typedef pair<int,int> P;const double eps=1e-9;const int maxn=100010;const int N=1000+10;const int mod=9901;ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}//-----------------------------------------------------------------------------int a[N][N],c[N][N];int n,m,x1,y1,x2,y2;char op;int lowbit(int x){return x&-x;}void add(int x,int y){ for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j)) c[i][j]++;}int sum(int x,int y){ int cnt=0; for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j)) cnt+=c[i][j]; return cnt;}int main(){ int T; scanf("%d",&T); while(T--){ CLR(c);CLR(a); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf(" %c",&op); if(op==‘C‘){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); add(x1,y1); add(x1,y2+1); add(x2+1,y1); add(x2+1,y2+1); } if(op==‘Q‘){ scanf("%d%d",&x1,&y1); printf("%d\n",sum(x1,y1)%2); } } if(T) printf("\n"); } return 0;}
POJ2155 Matrix
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。