[BZOJ1176][Balkan2007]Mokia（cdq分治+bit）

[BZOJ1176][Balkan2007]Mokia（cdq分治+bit）

题目描述

传送门
S不用管它…

题解

cdq分治板子题T_T
感觉所有讲cdq分治的资料都是“从cash谈起”，然而我感觉这题比较裸，可以先做这道题明白了cdq是干什么的再去想那些神dp

感觉cdq分治的做法就是将一个区间(l,r)分成(l,mid)和(mid+1,r)，然后处理(l,mid)对(mid+1,r)的影响，然后递归处理(l,mid)和(mid+1,r)
关键就是如何处理(l,mid)对(mid+1,r)的影响

这道题的做法是，将查询操作拆成4个，其中有两个矩形加到答案中，两个矩形在答案中减去
按照时间顺序修改和查询形成了一个序列，对于每一次修改操作，即修改这个点，对于每一个查询操作，就是查询某一个点的二维前缀和（然后在答案里加加减减）
二维bit是不行的（MLE+TLE），不过既然是前缀和，可以考虑如何用一维bit来解决这个问题
我们要处理(l,mid)对(mid+1,r)的影响，就是首先进行(l,mid)中的修改，然后对于(mid+1,r)里的每一个询问来查询
对于某一个查询(x,y)，显然所有的修改中只有横纵坐标都小于等于x,y的才是有价值的
于是做法就明了了
将(l,mid)和(mid+1,r)分别按照x坐标排序，两个指针，对于一个询问将横坐标小于它的点都在bit里修改，然后查询它纵坐标的前缀和就可以了

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 200005int T,s,n,opt,x,y,p,q,v,cnt,acnt,bcnt,pa,pb,tot;
struct hp{int x,y,ty,id,v;}opr[N*4],a[N*4],b[N*4],ch[N*4];
int C[N*10],ans[N];
bool flag[N];int cmp(hp a,hp b)
{return a.x<b.x;
}
void add(int loc,int val)
{if (!loc) return;for (int i=loc;i<=n;i+=i&(-i))C[i]+=val;
}
int query(int loc)
{int ans=0;for (int i=loc;i>=1;i-=i&(-i))ans+=C[i];return ans;
}
void cdq(int l,int r)
{if (l>=r) return;int mid=(l+r)>>1;cdq(l,mid);acnt=0;for (int i=l;i<=mid;++i) a[++acnt]=opr[i];sort(a+1,a+acnt+1,cmp);bcnt=0;for (int i=mid+1;i<=r;++i) b[++bcnt]=opr[i];sort(b+1,b+bcnt+1,cmp);pa=pb=1;tot=0;while (pb<=bcnt){while (pa<=acnt&&a[pa].x<=b[pb].x){if (!a[pa].ty){add(a[pa].y,a[pa].v);ch[++tot].x=a[pa].y,ch[tot].v=a[pa].v;}++pa;}ans[b[pb].id]+=query(b[pb].y)*b[pb].ty;++pb;}for (int i=1;i<=tot;++i)add(ch[i].x,-ch[i].v);cdq(mid+1,r);
}
int main()
{scanf("%d%d",&s,&n);while (~scanf("%d",&opt)){++T;if (opt==3) break;if (opt==1){scanf("%d%d%d",&x,&y,&v);opr[++cnt].x=x,opr[cnt].y=y,opr[cnt].ty=0,opr[cnt].v=v,opr[cnt].id=T;}else{flag[T]=true;scanf("%d%d%d%d",&x,&y,&p,&q);opr[++cnt].x=x-1,opr[cnt].y=y-1,opr[cnt].ty=1,opr[cnt].id=T;opr[++cnt].x=p,opr[cnt].y=q,opr[cnt].ty=1,opr[cnt].id=T;opr[++cnt].x=x-1,opr[cnt].y=q,opr[cnt].ty=-1,opr[cnt].id=T;opr[++cnt].x=p,opr[cnt].y=y-1,opr[cnt].ty=-1,opr[cnt].id=T;}}cdq(1,cnt);for (int i=1;i<=T;++i)if (flag[i]) printf("%dn",ans[i]);
}