CDQ分治

  1. 1 【bzoj 3262】 陌上花开
  2. 2 【bzoj 1176】 [Balkan2007]Mokia
  3. 3 【bzoj 3295】 [Cqoi2011]动态逆序对
  4. 4 【bzoj 2961】 共点圆

CDQ分治|ZYK1997
以下题解去看学长博客吧,我就发一下代码

1 【bzoj 3262】 陌上花开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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]动态逆序对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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意义下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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");
}