bzoj1176 [Balkan2007]Mokia

本文主要是介绍bzoj1176 [Balkan2007]Mokia，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
hzwerの题解

CDQ分治

CODE：

#include<cstdio>
#include<algorithm>
using namespace std;
#define lowbit(x) x&(-x)
const int N=2e5+10;
struct node
{int x,y,z,Case,id,wh,f;inline bool operator <(const node &other)const{if(x==other.x)if(y==other.y) return id<other.id;else return y<other.y;else return x<other.x;}
}q[N],tmp[N];
int a[N*10],t[N*10],ans[N];
int s,w,n,opt,Time,tot;
inline void read(int &n)
{n=0;char c=getchar();while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9') n=(n<<3)+(n<<1)+c-48,c=getchar();
}
inline void Add(int x,int y,int wh,int f)
{q[++n].x=x,q[n].y=y,q[n].Case=2,q[n].id=n,q[n].wh=wh,q[n].f=f;
}
inline void add(int x,int num)
{for(int i=x;i<=w;i+=lowbit(i))if(t[i]!=Time) t[i]=Time,a[i]=num;else a[i]+=num;
}
inline int ask(int x)
{int ans=0;for(int i=x;i;i-=lowbit(i))if(t[i]==Time) ans+=a[i];return ans;
}
void solve(int l,int r)
{if(l==r) return;int mid=(l+r)>>1;Time++;for(int i=l;i<=r;i++)if(q[i].id<=mid&&q[i].Case==1) add(q[i].y,q[i].z);else if(q[i].id>mid&&q[i].Case==2) ans[q[i].wh]+=q[i].f*ask(q[i].y);int tmp1=l,tmp2=mid+1;for(int i=l;i<=r;i++)if(q[i].id<=mid) tmp[tmp1++]=q[i];else tmp[tmp2++]=q[i];for(int i=l;i<=r;i++)q[i]=tmp[i];solve(l,mid),solve(mid+1,r);
}
int main()
{read(s),read(w);while(1){read(opt);if(opt==3) break;if(opt==2){int x,y,z,w;read(x),read(y),read(z),read(w);Add(x-1,y-1,++tot,1),Add(z,w,tot,1),Add(x-1,w,tot,-1),Add(z,y-1,tot,-1);}else n++,read(q[n].x),read(q[n].y),read(q[n].z),q[n].Case=1,q[n].id=n;}sort(q+1,q+n+1);solve(1,n);for(int i=1;i<=tot;i++)printf("%d\n",ans[i]+s);return 0;
}

这篇关于bzoj1176 [Balkan2007]Mokia的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---