CDQ分治

1 【bzoj 3262】 陌上花开

#include <algorithm>
#include <cstdio>
const int N=100005;
struct node{ int x,y,z,num,ans; }a[N];
int n,m,tot,ans[N],sum[N<<1];
inline bool cmp2(node a,node b)
{
	if(a.y!=b.y) return a.y<b.y;
	return a.z<b.z;
}
inline bool cmp1(node a,node b)
{
	if(a.x!=b.x) return a.x<b.x;
	return cmp2(a,b);
}
inline void Add(int x,int y)
{
	for(;x<=m;x+=x&(-x)) sum[x]+=y;
}
inline int Quary(int x)
{
	int ans=0;
	for(;x;x-=x&(-x)) ans+=sum[x];
	return ans;
}
inline void Calc(int l,int r)
{
	if(l==r) return;
	int mid=l+r>>1;
	Calc(l,mid);Calc(mid+1,r);
	std::sort(a+l,a+mid+1,cmp2);
	std::sort(a+mid+1,a+r+1,cmp2);
	for(int i=mid+1,j=l;i<=r;i++)
	{
		while(j<=mid&&a[j].y<=a[i].y) Add(a[j].z,a[j].num),j++;
		a[i].ans+=Quary(a[i].z);
	}
	for(int i=l,max=a[r].y;i<=mid&&a[i].y<=max;i++) Add(a[i].z,-a[i].num);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
	std::sort(a+1,a+n+1,cmp1);
	for(int i=1;i<=n;i++,a[tot].num++)
		if(a[i].x!=a[tot].x||a[i].y!=a[tot].y||a[i].z!=a[tot].z)
			a[++tot]=a[i];
	Calc(1,tot);
	for(int i=1;i<=tot;i++)
		ans[a[i].ans+a[i].num-1]+=a[i].num;
	for(int i=0;i<n;i++)
		printf("%d\n",ans[i]);
}

2 【bzoj 1176】 [Balkan2007]Mokia

#include <algorithm>
#include <cstdio>
struct node { int x,y,id,num,ans; } a[200005],b[200005];
int n,m,c[2000005];
inline bool cmpxy(const node &a,const node &b)
{
	if(a.x!=b.x) return a.x<b.x;
	if(a.y!=b.y) return a.y<b.y;
	return a.id<b.id;
}
inline bool cmpid(const node &a,const node &b)
{
	return a.id<b.id;
}
inline void Add(int x,int y)
{
	for(;x<=m;x+=x&(-x)) c[x]+=y;
}
inline int Quary(int x)
{
	int y=0;
	for(;x;x-=x&(-x)) y+=c[x];
	return y;
}
inline void Calc(int l,int r)
{
	if(l==r) return;
	int mid=l+r>>1;
	for(int i=l;i<=r;i++)
	{
		if(a[i].id<=mid&&a[i].num) Add(a[i].y,a[i].num);
		else if(a[i].id>mid&&!a[i].num) a[i].ans+=Quary(a[i].y);
	}
	for(int i=l;i<=r;i++) 
		if(a[i].id<=mid&&a[i].num) Add(a[i].y,-a[i].num);
	for(int i=l,x=l,y=mid+1;i<=r;i++)
		if(a[i].id<=mid) b[x++]=a[i];
		else b[y++]=a[i];
	for(int i=l;i<=r;i++) a[i]=b[i];
	Calc(l,mid);Calc(mid+1,r);
}
int main()
{
	scanf("%d%d",&m,&m);
	int opt,x1,y1,x2,y2;
	while(scanf("%d",&opt)&&opt!=3)
	{
		if(opt==1)
		{
			a[++n].id=n;
			scanf("%d%d%d",&a[n].x,&a[n].y,&a[n].num);
			if(!a[n].num) n--;
		}
		else
		{
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			a[++n].id=n; a[n].x=x1-1; a[n].y=y1-1;
			a[++n].id=n; a[n].x=x2;   a[n].y=y2;
			a[++n].id=n; a[n].x=x1-1; a[n].y=y2;
			a[++n].id=n; a[n].x=x2;   a[n].y=y1-1;
		}
	}
	std::sort(a+1,a+n+1,cmpxy);
	Calc(1,n);
	std::sort(a+1,a+n+1,cmpid);
	for(int i=1;i<=n;i++)
		if(!a[i].num)
			printf("%d\n",a[i].ans+a[i+1].ans-a[i+2].ans-a[i+3].ans),i+=3;
}

3 【bzoj 3295】 [Cqoi2011]动态逆序对

#include <cstdio>
const int N=100005;
struct node { int time,pos,val; } a[N],b[N];
int n,m,del[N],c[N];
long long ans[N];
inline void Add(int x,int y)
{
	for(;x<=n;x+=x&(-x)) c[x]+=y;
}
inline int Quary(int x)
{
	int y=0;
	for(;x;x-=x&(-x)) y+=c[x];
	return y;
}
inline void CDQ(int l,int r)
{
	if(l==r) return;
	int mid=l+r>>1;
	for(int i=l;i<=r;i++)
		if(a[i].time<=mid) Add(n-a[i].val+1,1);
		else ans[a[i].time]+=Quary(n-a[i].val+1);
	for(int i=l;i<=r;i++) 
		if(a[i].time<=mid) Add(n-a[i].val+1,-1);
	for(int i=r;i>=l;i--)
		if(a[i].time<=mid) Add(a[i].val,1);
		else ans[a[i].time]+=Quary(a[i].val);
	for(int i=r;i>=l;i--)
		if(a[i].time<=mid) Add(a[i].val,-1);
	for(int i=l,x=l,y=mid+1;i<=r;i++)
		if(a[i].time<=mid) b[x++]=a[i];
		else b[y++]=a[i];
	for(int i=l;i<=r;i++) a[i]=b[i];
	CDQ(l,mid);CDQ(mid+1,r);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i].val);
	for(int i=1,x;i<=m;i++)
		scanf("%d",&x),del[x]=n-i+1;
	for(int i=1,j=0;i<=n;i++)
		a[i].pos=i,a[i].time=del[a[i].val]?del[a[i].val]:++j;
	CDQ(1,n);
	for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
	for(int i=n;i>n-m;i--) printf("%lld\n",ans[i]);
}

4 【bzoj 2961】 共点圆

吐槽一句。。。
这题我写了一天才调出来，原因是除法精度太低!!! QAQ
而且A掉的程序和force拍还是有很多错的。。。
不过在调试的过程中有一点收获：在double意义下
\[ n\div 0 = \begin{cases} inf & \text{(n>0)} \\ NaN & \text{(n=0)} \\ -inf & \text{(n<0)} \\ \end{cases} \]

#include <algorithm>
#include <cstdio>
const int N=500005;
int n,ans[N];
struct Dot { double x,y; } st[N],qu[N];
struct node { int id,f; double k; Dot d; } a[N],b[N];
bool cmpx (const node &a,const node &b) { return a.d.x!=b.d.x?a.d.x<b.d.x:a.d.y<b.d.y; }
bool cmpk (const node &a,const node &b) { return a.k<b.k; }
bool OK (Dot a,Dot b) { return b.x*b.x+b.y*b.y-2*b.x*a.x-2*b.y*a.y>=0; }
void CDQ(int l,int r,int m)
{
	if(l==r||m==r||m<l) return;
	int mid=l+r>>1;
	for(int i=l,head=l,tail=mid+1;i<=r;i++)
		if(a[i].id<=mid) b[head++]=a[i];
		else b[tail++]=a[i];
	for(int i=l;i<=r;i++) a[i]=b[i];

	int tot=0,head=1,tail=0,top=0;
	for(int i=l;i<=mid&&!a[i].f;i++)
	{
		tot++;
		while(tail>1&&(a[i].d.y-qu[tail].y)*(qu[tail].x-qu[tail-1].x)<=(qu[tail].y-qu[tail-1].y)*(a[i].d.x-qu[tail].x)) tail--;
		while(top>1&&(a[i].d.y-st[top].y)*(st[top].x-st[top-1].x)>=(st[top].y-st[top-1].y)*(a[i].d.x-st[top].x)) top--;
		qu[++tail]=st[++top]=a[i].d;
	}
	if(tot)
	for(int i=m+mid-l-tot+2;i<=r;i++)
		if(ans[a[i].f])
		{
			if(a[i].d.x==0&&a[i].d.y==0) continue;
			if(a[i].d.y>=0)
			{
				while(head<tail&&qu[head+1].y-qu[head].y<=a[i].k*(qu[head+1].x-qu[head].x)) head++;
				if(OK(qu[head],a[i].d)) ans[a[i].f]=0;
			}
			else
			{
				while(top>1&&st[top].y-st[top-1].y<=a[i].k*(st[top].x-st[top-1].x)) top--;
				if(OK(st[top],a[i].d)) ans[a[i].f]=0;
			}
		}
	CDQ(l,mid,l+tot-1);CDQ(mid+1,r,m+mid-l-tot+1);
}
int main()
{
	scanf("%d",&n);
	int head=1,tail=n;
	for(int i=1,f,x;i<=n;i++)
	{
		scanf("%d",&f);
		if(!f) x=head++;else x=tail--;
		a[x].id=i;
		scanf("%lf%lf",&a[x].d.x,&a[x].d.y);
		if(f) 
		{
			a[x].f=n-tail;
			ans[n-tail]=(head>1);
			a[x].k=-a[x].d.x/a[x].d.y;
		}
	}
	std::sort(a+1,a+head,cmpx);
	std::sort(a+head,a+n+1,cmpk);
	CDQ(1,n,head-1);
	for(int i=1;i<=n-tail;i++) puts(ans[i]?"Yes":"No");
}