首页 > 代码库 > 【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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。