首页 > 代码库 > 【COGS1752】 BOI2007—摩基亚Mokia

【COGS1752】 BOI2007—摩基亚Mokia

http://cogs.pro/cogs/problem/problem.php?pid=1752 (题目链接)

题意

  给出$n*n$的棋盘,单点修改,矩阵查询。

Solution

  离线以后CDQ分治。每一层按照$Y$排序,然后询问用前缀和拆成$4$个,树状数组维护一下就可以了。

细节

  ?

代码

// cogs1752#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf (1ll<<30)#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=200010,maxd=2000010;int c[maxd],ans[maxn],n,m;struct data {int x,y,k,id,op;}q[maxn<<2],nq[maxn<<2];int lowbit(int x) {	return x&-x;}void add(int x,int val) {	for (int i=x;i<=n;i+=lowbit(i)) c[i]+=val;}int query(int x) {	int res=0;	for (int i=x;i;i-=lowbit(i)) res+=c[i];	return res;}void solve(int l,int r) {	if (l==r) return;	int mid=(l+r)>>1,l1=l,l2=mid+1;	for (int i=l;i<=r;i++) q[i].id<=mid ? nq[l1++]=q[i] : nq[l2++]=q[i];	for (int i=l;i<=r;i++) q[i]=nq[i];	solve(l,mid);solve(mid+1,r);	for (int i=l,j=mid+1,k=l;i<=mid || j<=r;) {		if (j>r || (i<=mid && q[i].y<=q[j].y)) {			if (q[i].k>0) add(q[i].x,q[i].k);			nq[k++]=q[i++];		}		else {			if (q[j].k<0) ans[-q[j].k]+=q[j].op*query(q[j].x);			nq[k++]=q[j++];		}	}	for (int i=l;i<=mid;i++) if (q[i].k>0) add(q[i].x,-q[i].k);	for (int i=l;i<=r;i++) q[i]=nq[i];}int main() {	free("mokia");	int T,tot=0;	while (scanf("%d",&T)!=EOF) {		if (T==0) scanf("%d",&n);		if (T==1) {			int x,y,k;			scanf("%d%d%d",&x,&y,&k);			m++,q[m]=(data){x,y,k,m,0};		}		if (T==2) {			int x1,y1,x2,y2;tot++;			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);			m++,q[m]=(data){x1-1,y1-1,-tot,m,1};			m++,q[m]=(data){x1-1,y2,-tot,m,-1};			m++,q[m]=(data){x2,y1-1,-tot,m,-1};			m++,q[m]=(data){x2,y2,-tot,m,1};		}		if (T==3) break;	}	solve(1,m);	for (int i=1;i<=tot;i++) printf("%d\n",ans[i]);	return 0;}

 

【COGS1752】 BOI2007—摩基亚Mokia