基础优化技巧 2

Adelaide_Black · 2023-12-12 08:37:36 · 个人记录

P3740 [HAOI2014] 贴海报

想到倒着来考虑就将题目转化成为了区间染色问题。

一个要注意的点就是如果两个子区间都被染色了，要记得向上传递表示父区间也被染色了。

因为如果一个区间刚好包含父区间的话，它并不会向下查找，而是直接判断该区间是否被染色。

拍到的一组数据：

没有 push_up 操作的输出

True 23 35 23 33//here
True 23 35 34 35
True 31 47 34 43//here
True 31 47 44 46
True 31 47 47 47
True 1 9 1 6
True 1 9 7 9
True 4 26 7 11
True 4 26 12 22
True 31 51 44 49
True 31 51 50 51
True 23 43 23 43//here
True 43 67 44 65
True 43 67 66 67
True 53 83 66 76
True 53 83 77 81
True 53 83 82 83
8

可以看到对于 [23,43] 这个区间，它的两个子区间都被染色过了，但是它本身没有被染色过，此时因为完全包含它，并不会往下查找，所以被误判了。

有 push_up 操作的输出

true 23 35 23 33//here
true 23 35 34 35
true 31 47 34 43//here
true 31 47 44 46
true 31 47 47 47
true 1 9 1 6
true 1 9 7 9
true 4 26 7 11
true 4 26 12 22
true 31 51 44 49
true 31 51 50 51
// 这里就判出来了，所以没有输出
true 43 67 44 65
true 43 67 66 67
true 53 83 66 76
true 53 83 77 81
true 53 83 82 83
7

P6627 [省选联考 2020 B 卷] 幸运数字

能够离散化的前提是根据答案求得的方式得到的，对于一个异或值相同的区间 [L,R]。根据取绝对值最小的答案，有以下三种选择：

R (L<R<0)

0 (L<0<R)

L (0<L<R)

所以对于一个新得到的区间，我们需要加入五个点 L-1,L,0,R,R+1。加入 L-1 和 R+1 是为了考虑答案不在该区间的情况。

P2163 [SHOI2007] 园丁的烦恼

二维数点

引自 \text{OI-Wiki}

二维数点
给一个长为 n 的序列，有 m 次查询，每次查区间 [l,r] 中值在 [x,y] 内的元素个数。

这个问题就叫做二维数点。我们可以发现等价于我们要查询一个二维平面上矩形内的点的数量和。这里讲一下这个问题最简单的处理方法，扫描线 + 树状数组。

很显然，这个问题是一个静态的二维问题，我们通过扫描线可以将静态的二维问题转换为动态的一维问题。维护动态的一维问题就使用数据结构维护序列，这里可以使用树状数组。

先将所有的询问离散化，用树状数组维护权值，对于每次询问的 l 和 r，我们在枚举到 l-1 时统计当前位于区间 [x,y] 内的数的数量 a，继续向后枚举，枚举到 r 时统计当前位于区间 [x,y] 内的数的数量 b，b-a 即为该次询问的答案。

可以用 洛谷 P2163[SHOI2007] 园丁的烦恼 这道题进行练习。

显然，当数据范围小时，可以用二维前缀和做。

当数据范围大时，可以用树状数组加扫描线来做。

将问题抽象成一个列为位置下标，行为元素种类的二维矩阵，每次询问就是询问矩阵中的一个子矩阵。

将子矩阵转化为两条横着的线存起来，通过横着从下往上遍历矩阵，将二维矩阵转化为一维矩阵，这就是扫描线算法。

然后再运用前缀和的思想求解并用树状数组统计个数即可。

code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,t[10000005],rec[500005*2];
struct node{int x,y;}a[500005];
struct A{int h,l,r,num;}line[500005*2];
int cnt_line;
bool cmp1(node aa,node bb){return aa.x<bb.x;};
bool cmp2(A aa,A bb){return aa.h<bb.h;};
void add(int x){
    for(;x<=10000000;x+=(x&-x)) t[x]+=1;
    return;
}
int sum(int x){
    int ans=0;
    for(;x;x-=(x&-x)) ans+=t[x];
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].x++,a[i].y++;
    } 
    for(int i=1;i<=m;i++){
        int x1,x2,y11,y2;
        scanf("%d%d%d%d",&x1,&y11,&x2,&y2);
        line[++cnt_line]={(A){x1,y11+1,y2+1,i*2-1}};
        line[++cnt_line]={(A){x2+1,y11+1,y2+1,i*2}};
    }
    sort(a+1,a+n+1,cmp1);
    sort(line+1,line+cnt_line+1,cmp2);
    int top=1,top_line=1;
    for(int i=0;i<=line[cnt_line].h;i++){
        while(top<=n && i==a[top].x){
            add(a[top].y);
            top++;
        }
        while(top_line<=cnt_line && i==line[top_line].h){
            rec[line[top_line].num]=sum(line[top_line].r)-sum(line[top_line].l-1);
            top_line++;
        }
    }
    for(int i=1;i<=m;i++){
        cout<<rec[i*2]-rec[i*2-1]<<endl;
    }
    return 0;
}

关于虚树另写了一篇博客

会了以上两个知识点，我们就可以写这一题啦！

P8339 [AHOI2022] 钥匙

由于题目给出的图为树，因此两点之间的路径是唯一的，不需要考虑最短路。也为之后能够用 dfn \times dfn 矩阵解决问题提供了先决条件。

考虑到每个钥匙 \le 5 把这个条件，因为两点之间的路径是固定的，且题目给出的操作具有强制性（指不能选择的），所以对于每把钥匙，它能开的锁也是固定的，每把钥匙对应的锁的集合为固定的，各个锁之间代表着钥匙走不同的方向能够得到开的锁，因此对于每个路径 (key,lock)，能够对所有包含它的路径贡献价值为 1 的金币，一把钥匙不可能对于同一条路径贡献两次，因为方向是确定的。

由于钥匙的个数很少，因此枚举每个钥匙所能到达的锁的集合是可接受的。对于每种颜色，建立虚树再去遍历来优化时间复杂度。使得时间复杂度与每种颜色的个数相挂钩，而不需要每次都将整棵树遍历。

接下来只需要一个数据结构，用来计算每个 (key,lock) 路径对于所有覆盖它的路径的贡献之和。

用 dfn \times dfn 的二维数点进行操作。

纵轴表示 s，横轴表示 e。对于 (key,lock) 路径，包含它的路径需要进行分类讨论。

当 key 是 lock 的祖先节点时

对于所有包含它的路径，其起点 st 应满足 st \notin subtree(key_{son})(key_{son} 表示从 lock 到 key 方向的 key 的子节点，而不是 key 的整棵子树)，其终点 end 应满足 end \in subtree(lock)。

反应到二维矩阵上就是子树补 \times 子树，子树补在 dfn 顺序上就是除了子树那一段之外另外的两端区域，子树代表的则是子树在 dfn 序上被遍历所代表的那一段。所以就是两个矩阵。

另外两种情况类似，不再赘述。

于是我们就将所有对答案有价值的路径的贡献转化到了二维数点上用矩阵表示，对于每个点对，其所代表的路径的答案就是被矩阵覆盖的次数。

由于整个二维数点是二维的，为了维护答案，我们可以将问题离线，然后排序，通过规定次序将矩阵降到一维的（扫描线思想），然后对于每一行，用树状数组动态维护答案即可。

code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m;
int color[5000005],type[5000005],k[55],num_k;
vector< vector<int> > t(5000005),c(5000005);
int head[500005*10],nex[500005*10],to[500005*10],cnt;
struct node{
    int high,l,r,val;
}line[500005*100];
int num_line;
void add(int x,int y){
    nex[++cnt]=head[x],head[x]=cnt,to[cnt]=y;
    nex[++cnt]=head[y],head[y]=cnt,to[cnt]=x;
}
int dfn[5000005],deep[5000005],dfn_num,f[500005][21],size[5000005];
void dfs(int x,int d,int fa){
    dfn[x]=++dfn_num,deep[x]=d,size[x]=1;
    c[color[x]].push_back(x);
    f[x][0]=fa;
    for(int i=1;i<=20;i++) f[x][i]=f[f[x][i-1]][i-1];
    for(int i=0;i<t[x].size();i++){
        int y=t[x][i];
        if(y==fa) continue;
        dfs(y,d+1,x);
        size[x]+=size[y];
    }
    return;
}
bool cmp(int aa,int bb){return dfn[aa]<dfn[bb];}
int sta[500005],top;
int LCA(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--)
        if(deep[f[x][i]]>=deep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
void virtual_tree(int x){
    head[1]=0,sta[top=1]=1;
    //cout<<"ZXX "<<x<<" "<<c[x][0]<<endl;
    int beg=(c[x][0]==1);
    if(c[x][0]==1&&type[1]==1) k[++num_k]=1;
    for(int i=beg;i<c[x].size();i++){
        int y=c[x][i];
        if(type[y]==1) k[++num_k]=y;
        int lca=LCA(y,sta[top]);
        if(lca!=sta[top]){
            while(dfn[sta[top-1]]>dfn[lca]){
                add(sta[top-1],sta[top]);
                top--;
            }
            if(sta[top-1]==lca){
                add(lca,sta[top]);
                top--;
            }
            else{
                //要注意这个加的顺序！要有逻辑！ 
                head[lca]=0;
                add(lca,sta[top]);
                sta[top]=lca;
            }
        }
        head[y]=0,sta[++top]=y;
    }
    for(int i=1;i<top;i++) add(sta[i],sta[i+1]);
    return;
}
int find(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--)
        if(deep[f[x][i]]>deep[y]) x=f[x][i];
    return x;
}
void add_line(int x,int y){
    int lca=LCA(x,y);
    if(lca==x){
    //子树补 * 子树
        int w=find(x,y);
        //matrix dfn[1] dfn[w]-1 dfn[y] dfn[y]+size[y]-1;
        line[++num_line]={(node){1,dfn[y],dfn[y]+size[y]-1,1}};
        line[++num_line]={(node){dfn[w]-1+1,dfn[y],dfn[y]+size[y]-1,-1}};
        //matrix dfn[w]+size[w],n,dfn[y] dfn[y]+size[y]-1;
        line[++num_line]={(node){dfn[w]+size[w],dfn[y],dfn[y]+size[y]-1,1}};
        line[++num_line]={(node){n+1,dfn[y],dfn[y]+size[y]-1,-1}};
    }
    else if(lca==y){
    //子树 * 子树补 
        int w=find(x,y);
        //matrix dfn[x] dfn[x]+size[x]-1 1 dfn[w]-1
        line[++num_line]={(node){dfn[x],1,dfn[w]-1,1}};
        line[++num_line]={(node){dfn[x]+size[x]-1+1,1,dfn[w]-1,-1}};
        //matrix dfn[x] dfn[x]+size[x]-1 dfn[w]+size[w] n
        line[++num_line]={(node){dfn[x],dfn[w]+size[w],n,1}};
        line[++num_line]={(node){dfn[x]+size[x]-1+1,dfn[w]+size[w],n,-1}};
    }
    else{
        //matrix dfn[x] dfn[x]+size[x]-1 dfn[y] dfn[y]+size[y]-1
        line[++num_line]={(node){dfn[x],dfn[y],dfn[y]+size[y]-1,1}};
        line[++num_line]={(node){dfn[x]+size[x]-1+1,dfn[y],dfn[y]+size[y]-1,-1}};
    }
    return;

}
struct A{int number,key,father;};
queue<A> q;
void BFS(int beg,int col){
    q.push((A){beg,1,beg});
    while(!q.empty()){
        A vv=q.front();
        q.pop();
        for(int i=head[vv.number];i;i=nex[i]){
            int y=to[i];
            if(y==vv.father) continue;
            if(color[y]==col){
                if(type[y]==1){
                    q.push((A){y,vv.key+1,vv.number});
                }
                else{
                    if(vv.key==1) add_line(beg,y);
                    else q.push((A){y,vv.key-1,vv.number});
                }
            }
            else q.push((A){y,vv.key,vv.number});
        }
    }
}
struct kkk{int st,en,num;}qu[1000005];
int tree[5000005];
void add_tree(int x,int va){
    for(;x<=n;x+=(x&-x)) tree[x]+=va;
    return;
}
int sum_tree(int x){
    int sum=0;
    for(;x;x-=(x&-x)) sum+=tree[x];
    return sum;
}
bool cmp2(node aa,node bb){return aa.high<bb.high;}
int ans[1000005]; 
bool cmp1(kkk aa,kkk bb){return dfn[aa.st]<dfn[bb.st];}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&type[i],&color[i]);
    }
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        t[u].push_back(v);
        t[v].push_back(u);
    }
    dfs(1,1,1);
    for(int i=1;i<=n;i++){
        if(!c[i].empty()){
            cnt=0;
            num_k=0;
            virtual_tree(i);
            for(int j=1;j<=num_k;j++) BFS(k[j],i);
        }
    }
    sort(line+1,line+num_line+1,cmp2);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&qu[i].st,&qu[i].en);
        qu[i].num=i;
    }
    sort(qu,qu+m+1,cmp1);
    int use_line=1,use_qu=1;
    for(int i=1;i<=n;i++){
        while(line[use_line].high==i){
            if(line[use_line].val==1){
                add_tree(line[use_line].l,1);
                add_tree(line[use_line].r+1,-1);
            }
            else{
                add_tree(line[use_line].l,-1);
                add_tree(line[use_line].r+1,1);
            }
            use_line++;
        }
        while(dfn[qu[use_qu].st]==i){
            ans[qu[use_qu].num]=sum_tree(dfn[qu[use_qu].en]);
            use_qu++;
        }
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}