CDQ分治
使用cdq分治的条件:
修改操作对询问的贡献独立,修改操作相互不影响 题目可以使用离线算法,不必强制在线(询问次数可以保存在数组)
cdq分治的性质:
cdq分治通过对时间复杂度增加一个log来降维 cdq可以用来代替复杂的数据结构 在cdq分治中,对于划分出来的两个区间,前一个子问题需要用来解决后一个子问题。
cdq使用步骤:
将整个操作序列分为两个长度相等的部分。 递归处理前一部分的子问题(治1) 计算前一部分子问题的修改操作对后一部分子问题的影响(治2) 递归处理后一部分的子问题(治3)
离线,处理点对关系,常用于降维度,
归并排序(合并左右区间,逐级向上):
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
using namespace std;
int temp[500005],a[500005],n;
long long ans;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
void merge(int l,int r)
{
if(l==r) return;
int mid=(l+r)/2;
merge(l,mid);
merge(mid+1,r);
int i=l,j=mid+1,p=l;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j])
temp[p++]=a[i++];
else
ans+=(mid-i+1),//计算逆序数
temp[p++]=a[j++];
}
while(i<=mid)
temp[p++]=a[i++];
while(j<=r)
temp[p++]=a[j++];
for(int k=l;k<=r;k++)
a[k]=temp[k];
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
merge(1,n);
cout<<ans;
return 0;
}
1 |
|
二维偏序
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
using namespace std;
const int N=1e5+10;
int a[N],s[N],n,k;
long long cdq(int l,int r)
{
long long res=0;
if(l==r) return a[l]>=0;
int mid=(l+r)>>1;
res+=cdq(l,mid);
res+=cdq(mid+1,r);
s[mid]=a[mid],s[mid+1]=a[mid+1];
for(int i=mid-1;i>=l;i--) s[i]=s[i+1]+a[i];//左半部分求后缀和
for(int i=mid+2;i<=r;i++) s[i]=s[i-1]+a[i];//右半部分求前缀和
sort(s+l,s+mid+1),sort(s+mid+1,s+r+1);
int p=l,q=r;
while(p<=mid)
{
while(q>=mid+1&&s[p]+s[q]>=0) q--;
res+=r-q;//左端点固定,符合条件的右端点数
p++;
}
return res;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]-=k;
}
cout<<cdq(1,n);
return 0;
}
1 |
|
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
using namespace std;
const int N=1e5+10;
long long a[N];
int n,L,R;
long long cdq(int l,int r)
{
long long res=0;
if(l==r) return a[l]>=L&&a[l]<=R;
int mid=(l+r)>>1;
res+=cdq(l,mid);
res+=cdq(mid+1,r);
int head=l,tail=l-1;
for(int i=mid+1;i<=r;i++)
{
while(tail+1<=mid&&a[i]-a[tail+1]>=L) tail++;//最终a[i]-a[tail]>=L
while(head<=mid&&a[i]-a[head]>R) head++;//最终a[i]-a[head]<=R
res+=tail-head+1;//对于每个区间右端点,可行的左端点个数
}
sort(a+l,a+r+1);
return res;
}
int main()
{
cin>>n>>L>>R;
for(int i=1;i<=n;i++)
scanf("%ld",&a[i]),a[i]+=a[i-1];//前缀和数组
cout<<cdq(1,n);
return 0;
}
1 |
|
三维偏序
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
using namespace std;
struct node
{
int a,b,c,cnt,ans;
}s1[maxn],s2[maxn];
int n,m,k,mx,top,su[maxn];
int c[maxn];//树状数组
bool cmp1(node x,node y)
{
if(x.a==y.a)
{
if(x.b==y.b)return x.c<y.c;
else return x.b<y.b;
}
else return x.a<y.a;
}//第一维排序
bool cmp2(node x,node y)
{
if(x.b==y.b)
return x.c<y.c;
else return x.b<y.b;
}//第二维排序
int lowbit(int x)
{
return x&(-x);
}
void add(int pos,int val)
{
for(int i=pos;i<=mx;i+=lowbit(i))
c[i]+=val;
}
int query(int pos)
{
int tot=0;
for(int i=pos;i;i-=lowbit(i))
tot+=c[i];
return tot;
}
void cdq(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
sort(s2+l,s2+mid+1,cmp2);
sort(s2+mid+1,s2+r+1,cmp2);
int i=l,j;
for(int j=mid+1;j<=r;j++)
{
while(s2[j].b>=s2[i].b&&i<=mid)
{
add(s2[i].c,s2[i].cnt);
i++;
}
s2[j].ans+=query(s2[j].c);
}
for(int p=l;p<i;p++)
add(s2[p].c,-s2[p].cnt);
}
int main()
{
scanf("%d%d",&n,&k);
mx=k;//树状数组的区间
for(int i=1;i<=n;++i)
scanf("%d%d%d",&s1[i].a,&s1[i].b,&s1[i].c);
sort(s1+1,s1+1+n,cmp1);//第一维为关键字排序
for(int i=1;i<=n;++i)
{
top++;
if(s1[i].a!=s1[i+1].a||s1[i].b!=s1[i+1].b||s1[i].c!=s1[i+1].c)
{
s2[++m]=s1[i];
s2[m].cnt=top;
top=0;
}
}//第一维已有序,合并相同节点
cdq(1,m);//cdq分治
for(int i=1;i<=m;++i)
su[s2[i].ans+s2[i].cnt-1]+=s2[i].cnt;
for(int i=0;i<n;++i)
printf("%d\n",su[i]);
return 0;
}
1 |
|
对答案有贡献的点$(i,j)$对满足的条件:
$val_i
那么这个问题就变成了经典的三维偏序问题,可以通过cdq分治来解决。
先对time维排序(不需要额外的处理),在time有序的情况下使得归并区间内的pos有序,将val加到树状数组中。
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
using namespace std;
const int N=2e5+10;
struct Node
{
int val,pos,time,cnt;
}e[N];
bool cmp1(Node x,Node y)
{
return x.pos<y.pos;
}
int pos[N],n,m,tot,c[N];
//树状数组在val维上建
long long ans[N];
int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') ch=='-'&&(f=-1),ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
int lowbit(int x)
{
return x&(-x);
}
void add(int pos,int x)
{
for(int i=pos;i<=n;i+=lowbit(i))
c[i]+=x;
}
int query(int pos)
{
int res=0;
for(int i=pos;i;i-=lowbit(i))
res+=c[i];
return res;
}
void cdq(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
sort(e+l,e+mid+1,cmp1);
sort(e+mid+1,e+r+1,cmp1);//按照pos排序
int i=l,j;//i为左部分指针,j为右部分指针
for(j=mid+1;j<=r;j++)
{
while(i<=mid&&e[i].pos<=e[j].pos)//time_i<=time_j&&pos_i<=pos_j
{
add(e[i].val,e[i].cnt);
i++;
}
ans[e[j].time]+=1ll*e[j].cnt*(query(n)-query(e[j].val));
//(query(n)-query(e[j].val)):pos_i<=pos_j&&val_i>val_j形成的逆序对
}
for(int p=l;p<i;p++)
add(e[p].val,-e[p].cnt);//还原
i=mid;
for(int j=r;j>mid;j--)
{
while(i>=l&&e[i].pos>=e[j].pos)//time_i<=time_j&&pos_i>=pos_j
{
add(e[i].val,e[i].cnt);
i--;
}
ans[e[j].time]+=1ll*e[j].cnt*query(e[j].val-1);
// query(e[j].val-1):pos_i>=pos_j&&val_i<val_j形成的逆序对
}
for(int p=mid;p>i;p--)
add(e[p].val,-e[p].cnt);//还原
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x=read();
pos[x]=i;
e[++tot]={x,i,0,1};
}
for(int i=1;i<=m;i++)
{
int x=read();
e[++tot]={x,pos[x],i,-1};
}
//此时 time维 有序
cdq(1,tot);
//此时ans[0]是原始数列逆序对数,之后的 ans[1]~ans[m]都<=0
for(int i=1;i<=m;i++) ans[i]+=ans[i-1];
for(int i=0;i<m;i++) printf("%lld\n",ans[i]);
return 0;
}
1 |
|
只考虑左下角的所有点,对答案有贡献的点$(i,j)$对满足的条件:
$x_i<x_j, y_i<y_j, t_i<t_j$
那么这个问题就变成了经典的三维偏序问题,可以通过cdq分治来解决。
先对time维排序(不需要额外的处理),在time有序的情况下使得归并区间内的x有序,将(x+y)加到y轴的树状数组中。
1 |
|
将点坐标对称,每次更新答案,可以求出最小值。
1 |
|
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment