【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;

}