感觉cdq分治是一个很有趣的算法 能将很多需要套数据结构的题通过离线来做
目前的一些微小的理解
在一般情况下 就像求三维偏序xyz
就可以先对x排序 然后分治
1 cdq_x(L,M) ;
2 提取出(L,M)中的修改元素 作为修改操作 提取出(M+1,R)中的查询元素 作为查询操作 然后存入数组q 对q按照y排序
这样 在q中 关于y 所有的修改操作 都会在 可能作用到的查询操作前面
似乎可以将这一步 称作"对x维度的剥离" 在对q数组接下来的操作中 不需要考虑x维度
3 cdq_x(M+1,R);
/// 迷之分析
三维偏序 有时间和xyz 一开始 分两半时间 左边时间一定比右边小 然后记录下左边的修改操作与右边的非修改操作 下一步剥离 对新的区间进行sort 保证了这些修改 查询都各自有意义 sort的是x 则下面的操作中 * 所有的操作 对于其后的询问 都有意义 再次剥离出y 因为之前对x进行了sort 所以之后的新区间(只有z存在大小关系的区间) 前面的半个区间(x层面上的) 对于后半个区间 都有明确的先后关系 而降到z一维的时候 直接树状数组就可以
///迷之证明
如何证明 这些修改和查询都有类似时间线的压制力 一开始的时间可以使first唯独 不可逆 之后的查询都有x1<x2 y1<y2 z1<z2 故若x1>x2则没有意义 1 先剥离出时间维度上 * 左边对且仅对右边有value的操作 即 左改右查 这时是剥离时间 2 剥离x 这时的时间已完全剥离 因为时间影响在"左改右查"中已经去掉 所以剥离x也要"左改右查" 3 到只有 yz 因为y已经被sort 所以直接对z使用树状数组
一般需要一个离散化来做树状数组的相关处理
注意下cdq的各个部分该放在哪里
hdu 5324
求最小字典序的最长偏序序列
cdq分治 由于要记录最小字典序 所以倒着做一下 去掉时间的影响 sort y后 就可以直接x 从R->L 直接树状数组维护了
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<iostream>
#include<string>
#include<queue>
#include<vector>
using namespace std;
#define pb push_back
struct node {
int x , y ;
int id ;
int xg ;
}a[50050];
int len[50050] ;
int nex[50050] ;
int c[50050 + 500] ;
int tid[50050 + 500] ;
int n ;
node q1[50050] ;
bool cmpy(node a,node b) {
if(a.y != b.y) return a.y < b.y ;
return a.x > b.x ;
}
int lowbit(int x) {return (x & (-x)) ; } ;
void cdq_x(int L , int R) {
for(int i = R ; i >= L ; i -- ) {
if(q1[i].xg == 1) {
int lenn = len[q1[i].id] ;
int nexx = nex[q1[i].id] ;
for(int j = q1[i].x ; j <= 50050 ; j += lowbit(j)) {
if(c[j] < lenn) {
c[j] = lenn ;
tid[j] = q1[i].id ;
}
else if(c[j] == lenn) {
if(tid[j] > q1[i].id) {
tid[j] = q1[i].id ;
}
}
}
}
else {
int lenn = len[q1[i].id] ;
int nexx = nex[q1[i].id] ;
for(int j = q1[i].x ; j > 0 ; j -= lowbit(j)) {
if(c[j] == 0) continue ;
if(c[j] + 1 > lenn) {
len[q1[i].id] = c[j]+1 ; lenn = len[q1[i].id] ;
nex[q1[i].id] = tid[j] ; nexx = nex[q1[i].id] ;
}
else if(c[j] + 1 == lenn) {
if(tid[j] < nexx) {
len[q1[i].id] = c[j]+1 ; lenn = len[q1[i].id] ;
nex[q1[i].id] = tid[j] ; nexx = nex[q1[i].id] ;
}
}
}
}
}
for(int i = L ; i <= R ; i ++ ) {
if(q1[i].xg == 1) {
for(int j = q1[i].x ; j <= 50050 ; j += lowbit(j)) {
tid[j] = 0 ; c[j] = 0 ;
}
}
}
}
void cdq_time(int L , int R) {
if(L >= R) return ;
int M = (L + R) / 2 ;
cdq_time(M+1 , R) ;
int num = L ;
for(int i = M+1 ; i <= R ; i ++ ) {
q1[num] = a[i] ;
q1[num++].xg = 1 ;
}
for(int i = L ; i <= M ; i ++ ) {
q1[num] = a[i] ;
q1[num++].xg = 0 ;
}
sort(q1+L , q1+num , cmpy) ;
cdq_x(L , num-1) ;
cdq_time(L , M) ;
}
int main () {
while(scanf("%d",&n) != EOF) {
vector<int >ls ;
ls.clear() ;
for(int i=1;i<=n;i++)scanf("%d",&a[i].x) ; /// down
for(int i=1;i<=n;i++)scanf("%d",&a[i].y) ;
for(int i=1;i<=n;i++){
nex[i] = i ;
len[i] = 1 ;
a[i].id = i ;
ls.pb(a[i].x) ;
}
sort(ls.begin() , ls.end()) ;
ls.erase(unique(ls.begin() , ls.end()) , ls.end()) ;
for(int i = 1 ; i <= n ; i ++ ) {
int where = lower_bound(ls.begin() , ls.end() , a[i].x) - ls.begin() + 3 ;
a[i].x = where ;
}
cdq_time(1 , n) ;
int ans = 0 ;
int le = 0 ;
for(int i = 1 ; i <= n ; i ++ ) {
if(len[i] > le) {
le = len[i] ;
ans = i ;
}
}
printf("%d
",le) ;
printf("%d",ans) ;
while(true) {
if(nex[ans] == ans) break ;
ans = nex[ans] ;
printf(" %d",ans) ;
}
printf("
") ;
}
}
hdu 4742
记录最长三维偏序的方案数
和上一个题类似 但是求得是方案 于是把与c数组并列的tid数组改为次数数组 这个正着做就可以了
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<vector>
using namespace std;
const int mod = (1<<30) ;
struct node {
int x , y , z;
int ansid ;
int xg ;
}a[100050];
int ans[100050] ;
int len[100050] ;
int n ;
int c[100050+500] ;
int cishu[100050+500] ;
int maxx ;
node q1[100050] , q2[100050] ;
bool cmpx(node a,node b) {
if(a.x == b.x) {
if(a.y == b.y) return a.z < b.z ;
else return a.y < b.y ;
}
else return a.x < b.x ;
}
bool cmpy(node a,node b) {
if(a.y == b.y) {
return a.z < b.z ;
}
else return a.y < b.y ;
}
int lowbit(int x) {return (x & (-x)) ; } ;
void cdq_y(int L , int R) {
///printf("-
") ;
for(int i = L ; i <= R ; i ++ ) {
if(q2[i].xg == 1) {
for(int j = q2[i].z ; j <= maxx ; j += lowbit(j) ) {
if(c[j] < len[q2[i].ansid]) {
c[j] = len[q2[i].ansid ] ;
cishu[j] = ans[q2[i].ansid] ;
}
else if(c[j] == len[q2[i].ansid]) {
cishu[j] += ans[q2[i].ansid] ;
cishu[j] %= mod ;
}
}
}
else {
for(int j = q2[i].z ; j > 0 ; j -= lowbit(j)) {
if(c[j]+1 > len[q2[i].ansid]) {
len[q2[i].ansid] = c[j]+1 ;
ans[q2[i].ansid] = cishu[j] ;
}
else if(c[j] + 1 == len[q2[i].ansid]) {
ans[q2[i].ansid] += cishu[j] ;
ans[q2[i].ansid] %= mod ;
}
}
}
}
for(int i = L ; i <= R ; i ++ ) {
if(q2[i].xg == 1) {
for(int j = q2[i].z ; j <= maxx ; j += lowbit(j)) {
//if(c[j] == 0) continue ;
c[j] = 0 ;
cishu[j] = 0 ;
}
}
}
}
void cdq_x(int L , int R) {
if(L >= R) return ;
int M = (L + R) / 2 ;
cdq_x(L , M) ;
int num = L ;
for(int i = L ; i <= M ; i ++ ) {
q2[num ++ ] = a[i] ;
q2[num-1].xg = 1 ;
}
for(int i = M + 1 ; i <= R ; i ++ ) {
q2[num ++ ] = a[i] ;
q2[num-1].xg = 0 ;
}
sort(q2+L , q2+num , cmpy) ;
cdq_y(L , num-1) ;
cdq_x(M + 1 , R) ;
}
/*void cdq_time(int L , int R) {
if(L >= R) return ;
int M = (L + R) / 2 ;
cdq_time(L , M) ;
sort(a+L , a+R+1 , cmpx) ;
cdq_x(L,R) ;
cdq_time(M+1 , R) ;
}*/
vector<int >ls ;
int main () {
int T ;
scanf("%d",&T) ;
while(T--) {
scanf("%d",&n) ;
ls.clear() ;
memset(c,0,sizeof(c)) ;
memset(cishu,0,sizeof(cishu)) ;
for(int i = 1 ; i <= n ; i ++ ) {
ans[i] = 1 ;
len[i] = 1 ;
scanf("%d%d%d",&a[i].x , &a[i].y , &a[i].z) ;
a[i].ansid = i ;
ls.push_back(a[i].z) ;
}
sort(ls.begin() , ls.end()) ;
ls.erase(unique(ls.begin() , ls.end()) , ls.end()) ;
maxx = ls.size() + 20 ;
for(int i = 1 ; i <= n ; i ++ ) {
int where = lower_bound(ls.begin() , ls.end() , a[i].z) - ls.begin() + 5 ;
a[i].z = where ;
}
sort(a+1,a+1+n,cmpx) ;
cdq_x(1 , n) ;
int realans = 0 ;
int realcishu = 0 ;
for(int i = 1 ; i <= n ; i ++ ) {
if(len[i] > realans) {
realcishu = ans[i] ;
realans = len[i] ;
}
else if(len[i] == realans) {
realcishu += ans[i] ;
realcishu %= mod ;
}
}
printf("%d %d
",realans , realcishu) ;
}
}
hdu 5126 & bzoj 1935
动态的三维和二维空间询问有多少点
其实是可以直接kd上的...但是也可以cdq 并且省去了写数据结构的麻烦
其实就是把 一个空间的询问 拆分成多个空间->原点的询问 这个就可以用树状数组做一个前缀和的处理 并且记录下每个询问的ansid 随时更新
一个询问操作当然可以被查询很多次 但是可以看出 因为二分 每个之前的修改操作都只会在一个区域被访问一次
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<iostream>
#include<string>
#include<queue>
#include<vector>
using namespace std;
#define pb push_back
int cnt ;
int maxx ;
struct node {
int x , y , z ;
int idx ;
int tp ;
}a[50050 * 10] , q1[50000 * 10] , q2[50000 * 10];
int c[500500] ;
int lowbit(int x) {return (x&(-x)) ; }
void add(int x , int val) {
while(x <= maxx + 20) {
c[x] += val ;
x += lowbit(x) ;
}
}
int sum(int x) {
int res = 0 ;
while(x) {
res += c[x] ; x -= lowbit(x) ;
}
return res ;
}
int n ;
int ans[50050] ;
struct ls{
int x , id;
int idx ;
}lss[50050 * 10];
bool cmpls(ls a , ls b) {
return a.x < b.x ;
}
bool cmpx(node a,node b) {
if(a.x == b.x) return a.tp < b.tp ;
else return a.x < b.x ;
}
bool cmpy(node a,node b) {
if(a.y == b.y) return a.tp < b.tp ;
else return a.y < b.y ;
}
void cdq_y(int L , int R) { /// 其实这个时候 y 已经被排好序了 所以直接按照z 进行树状数组就可以了 这时候的z已经离散化了
for(int i = L ; i <= R ; i ++ ){
if(q2[i].tp == 0) {
add(q2[i].z , 1) ;
}
else {
int res = sum(q2[i].z) ;
if(q2[i].tp == 1) {
ans[q2[i].idx] += res ;
}
else {
ans[q2[i].idx] -= res ;
}
}
}
for(int i = L ; i <= R ; i ++ ) {
if(q2[i].tp == 0) {
add(q2[i].z , -1) ;
}
}
}
void cdq_x(int L , int R) { /// 只要还没有剥离到可以直接利用数据结构得出答案 就应该一直分治
if(L >= R) return ;
int M = (L + R) / 2 ;
cdq_x(L , M) ; cdq_x(M+1 , R) ;
int num = L ;
for(int i = L ; i <= M ; i ++ ) if(q1[i].tp == 0) q2[num ++ ] = q1[i] ;
for(int i = M + 1 ; i <= R ; i ++ ) if(q1[i].tp != 0) q2[num ++ ] = q1[i] ;
sort(q2 + L , q2 + num , cmpy) ;
cdq_y(L , num-1) ;
}
void cdq_time(int L , int R) {
if(L >= R) return ;
int M = (L + R) / 2 ;
cdq_time(L , M) ; cdq_time(M+1 , R) ;
int num = L ;
for(int i = L ; i <= M ; i ++ ) if(a[i].tp == 0) q1[num ++ ] = a[i] ;
for(int i = M + 1 ; i <= R ; i ++ ) if(a[i].tp != 0) q1[num ++ ] = a[i] ;
sort(q1 + L , q1 + num , cmpx) ; /// 上面两行 其实就已经剥离出时间了 所以这个时候应该按照x排序 便于剥离x
cdq_x(L , num-1) ;
}
int main (){
int T;
scanf("%d" , &T) ;
while(T -- ) {
memset(c , 0 , sizeof(c)) ;
scanf("%d" , &n) ;
memset(ans , 0 , sizeof(ans)) ;
cnt = 0 ;
int now = 0 ;
for(int i = 1 ; i <= n ; i ++ ) {
int tp ;
scanf("%d" , &tp) ;
if(tp == 1) {
int x,y,z;
scanf("%d%d%d" , &x , &y , &z) ;
cnt ++ ;
a[cnt].tp = 0 ;
a[cnt].x = x ; a[cnt].y = y ; a[cnt].z = z ;
a[cnt].idx = i ;
ans[i] = -1 ;
now ++ ;
lss[now].id = cnt ;
lss[now].x = z ;
}
else {
int x,y,z,x2,y2,z2 ;
scanf("%d%d%d%d%d%d" , &x , &y , &z , &x2 , &y2 , &z2) ;
cnt ++ ; a[cnt] = {x2 , y2 , z2 , i , 1} ;
now ++ ; lss[now].id = cnt ; lss[now].x = z2 ;
cnt ++ ; a[cnt] = {x-1 , y2 , z2 , i , 2} ;
now ++ ; lss[now].id = cnt ; lss[now].x = z2 ;
cnt ++ ; a[cnt] = {x2 , y-1 , z2 , i , 2} ;
now ++ ; lss[now].id = cnt ; lss[now].x = z2 ;
cnt ++ ; a[cnt] = {x2 , y2 , z-1 , i , 2} ;
now ++ ; lss[now].id = cnt ; lss[now].x = z-1 ;
cnt ++ ; a[cnt] = {x-1 , y-1 , z2 , i , 1} ;
now ++ ; lss[now].id = cnt ; lss[now].x = z2 ;
cnt ++ ; a[cnt] = {x-1 , y2 , z-1 , i , 1} ;
now ++ ; lss[now].id = cnt ; lss[now].x = z-1 ;
cnt ++ ; a[cnt] = {x2 , y-1 , z-1 , i , 1} ;
now ++ ; lss[now].id = cnt ; lss[now].x = z-1 ;
cnt ++ ; a[cnt] = {x-1 , y-1 , z-1 , i , 2} ;
now ++ ; lss[now].id = cnt ; lss[now].x = z-1 ;
}
}
sort(lss+1 , lss+1+now , cmpls) ;
int res = 0 ;
lss[0].x = -97989 ;
for(int i=1;i<=now;i++) {
if(lss[i].x == lss[i-1].x) {
a[lss[i].id].z = lss[i-1].idx;
lss[i].idx = lss[i-1].idx;
}
else {
res ++ ;
lss[i].idx = res ;
a[lss[i].id].z = res ;
}
}
maxx = res ;
cdq_time(1 , cnt) ;
for(int i = 1 ; i <= n ; i ++ ) {
if(ans[i] != -1) printf("%d
",ans[i]) ;
}
}
}
虽然..看起来还是挺长的...
被打哭 意识到自己其实还不会cdq 于是再次学习
发现过去写的 逐渐剥离出维度 有点暴力了
算法的正确性是没有问题的 但是每次都sort 会多一个log 可以模仿归并排序
如果我先进行了cdq(L,M) cdq(M+1,R) 那么两边的数组都是排序好了的 就可以双指针排序这个数组 省去一个sort的时间
bzoj1935
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
#define L long long
#define pb push_back
#define lala printf("--------
");
#define ph push
#define rep(i, a, b) for (int i=a;i<=b;++i)
#define dow(i, b, a) for (int i=b;i>=a;--i)
#define fmt(i,n) if(i==n)printf("
");else printf(" ") ;
#define fi first
#define se second
template<class T> inline void flc(T &A, int x){memset(A, x, sizeof(A));}
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-'0';ch=getchar();}return x*f;}
int num;
struct node {
int x,y;
int time ;
int xw;
int id;
}q[500050 * 5],tmp[500050 * 5];
int c[10000050] ;
int lowbit(int x){return (x&(-x));}
void add(int x,int val) {while(x<=10000000) {c[x]+=val;x+=lowbit(x);}}
int sum(int x) {int res = 0 ; while(x) {res+=c[x];x-=lowbit(x);} return res ;}
int n , m ;
int ans[500050] ;
bool cmp(node a, node b) {
if(a.x == b.x) return a.time < b.time ;
return a.x < b.x ;
}
void cdq(int LL , int RR) {
if(RR-LL <= 0) return ;
int M = (LL+RR)/2 ;
int pl = LL ;
int pr = M+1 ;
int pp = LL ;
cdq(LL , M) ; cdq(M+1,RR) ; /// 在这里 先对两边进行递归 这样可以模仿一下归并排序 省去一个sort x的复杂度
while(pl <= M && pr <= RR) {
if(q[pl].x < q[pr].x || (q[pl].x == q[pr].x && q[pl].time < q[pr].time)) { /// 还是一个归并排序 左边的时间一定早于右边的时间 所以左边的修改可能对右边的查询有影响 但是不一定
/// 但是由于两边的x其实都已经归并排序好了 所以模仿归并的过程 面对的实际上是一个sort好的数组
if(q[pl].xw == 0) {
add(q[pl].y , 1) ;
}
tmp[pp ++ ] = q[pl ++ ] ;
}
else {
if(q[pr].xw == 1) {
ans[q[pr].id] += sum(q[pr].y) ;
}
else if(q[pr].xw == 2) {
ans[q[pr].id] -= sum(q[pr].y) ;
}
tmp[pp ++ ] = q[pr ++ ] ;
}
}
while(pl <= M) {
if(q[pl].xw == 0) add(q[pl].y , 1) ;
tmp[pp ++ ] = q[pl ++ ] ;
}
while(pr <= RR) {
if(q[pr].xw == 1)
ans[q[pr].id] += sum(q[pr].y) ;
else if(q[pr].xw == 2)
ans[q[pr].id] -= sum(q[pr].y) ;
tmp[pp ++ ] = q[pr ++ ] ;
}
for(int i = LL ; i <= M ; i ++ ) { /// 得消除掉c的操作 保持为0
if(q[i].xw == 0)
add(q[i].y , -1) ;
}
for(int i = LL ; i <= RR ; i ++ ) q[i] = tmp[i] ; /// 归并排序 数组复制
}
int main () {
n=read();m=read();
flc(c,0);
num=0;
rep(i,1,n) {
int x=read();int y=read();
x ++ ; y ++ ;
num++;
q[num]={x,y,num,0,0} ;
}
rep(i,1,m) {
int x1=read();int y1=read();int x2=read();int y2=read();
x1 ++ ; y1 ++ ; x2 ++ ; y2 ++ ;
q[++num]={x2,y2,num,1,i};
q[++num]={x1-1,y1-1,num,1,i};
q[++num]={x1-1,y2,num,2,i};
q[++num]={x2,y1-1,num,2,i};
}
flc(ans,0);
cdq(1,num) ;
rep(i,1,m) {
printf("%d
" , ans[i]) ;
}
}
cdq的复杂度是每层一个logn 如果直接sort的话其实也是这个复杂度 归并排序会省去一个常数