zcmimi's blog

arrow_back离线共19篇文章

avatar
zcmimi
2020-04-16 22:39:00

核心思想: 把一个修改看成一个区间,每个询问是一个叶子,修改在线段树上打标记

avatar
zcmimi
2020-03-25 17:13:00

整体二分是离线算法

顾名思义就是将所有答案一起二分

solve(l,r,st,ed)表示答案在[l,r],解决第sted个询问或操作

以静态区间第k小为例,[LG P3834 【模板】可持久化线段树 1(主席树)](https://www.luogu.com.cn/pro

avatar
zcmimi
2020-03-20 20:36:00

二维偏序

先按 第一维 排序, 第二维 用数据结构维护

例题: [SHOI2007]园丁的烦恼

离线操作

先将每个询问拆成4个点查询

(1,1)(x,y)中点数为s(x,y).

avatar
zc
2020-10-29 07:02:30

查看原题

点击跳转

考虑离线

把所有数排序后,可以发现经过4种操作后所有数还是有序的

这样我们维护区间加,区间乘,区间加变形,区间覆盖

avatar
zc
2020-10-07 20:03:39

查看原题

点击跳转

题意:

n个节点的树,有r种属性,每个点属于一种属性.有q次询问,每次询问给r_1,r_2,问有多少对点(e_1, e_2)满足e_1属性为 r_1,e_2属性为r_2,且e_1e_2的祖先. (n,q \le 2 \times 10^5, r \le 25000,时限5s)

首先将询问离线

不管枚举e_1统计子树中e_2的数量

还是枚举e_2统计到根节点路径上e_1的数量

都是\mathcal O(nr)

可以考虑将两种方法结合,使用根号分治

r_2的总数目为S

S\ge \sqrt n,枚举e_2,统计e_1(不超过\sqrt n个),复杂度\mathcal O(q\sqrt n)

否则枚举e_1,统计e_2(子树中的r_2不会超过\sqrt n个),复杂度\mathcal O(n\sqrt n)

具体看代码

avatar
zc
2020-09-27 14:05:00

查看原题

点击跳转

统计方法类似扫描线

lp排序,按顺序枚举

l的时候更新,在r之后还原(p已经不在区间[l,r]中了,不受影响)

以时间为下标,维护某个时间段内大于等于y的数个数

需要一个数据结构维护区间中大于等于某个数的个数(带修改),可以想到分块

avatar
zc
2020-09-21 21:09:00

查看原题

点击跳转

解法

记录每个点i前一个与它一样的位置pre_i,

那么区间[l,r]内不同的个数也就是[l,r]pre_i<l的个数

主席树

#include<bits/stdc++.h>
const int N=1000011;
int n,q,lst[N],RT[N],sz,s[N*20],ls[N*20],rs[N*20];
void build(int&x,int l,int r){
    x=++sz;
    if(l==r)return;
    int m=l+r>>1;
    build(ls[x],l,m);build(rs[x],m+1,r);
}
void ins(int&x,int pre,int p,int l,int r){
    s[x=++sz]=s[pre]+1;
    if(l==r)return;
    ls[x]=ls[pre],rs[x]=rs[pre];
    int m=l+r>>1;
    if(p<=m)ins(ls[x],ls[pre],p,l,m);
    else ins(rs[x],rs[pre],p,m+1,r);
}
int ask(int x,int y,int R,int l,int r){
    if(r<=R)return s[y]-s[x];
    int m=l+r>>1;
    return ask(ls[x],ls[y],R,l,m)+(R>m?ask(rs[x],rs[y],R,m+1,r):0);
}
void read(int&x){
    x=0;char c=getchar();
    for(;c<'0'||'9'<c;c=getchar());
    for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-48;
}
int main(){
    read(n);
    int x,l,r;
    build(RT[0],1,n);
    for(int i=1;i<=n;++i)
        read(x),
        ins(RT[i],RT[i-1],lst[x]+1,1,n),
        lst[x]=i;
    read(q);
    while(q--)
        read(l),read(r),
        printf("%d\n",ask(RT[l-1],RT[r],l,1,n));
}

主席树理论上是可以过的,可是为了卡莫队,主席树也TLE了

R.I.P

树状数组

还是求[l,r]pre_i<l的个数

离线处理

询问按右端点从小到大排序

枚举区间,将[1,r]中的点,i位置+1,pre_i位置-1(i之前pre_i已经贡献过了)

那么r减去l-1的前缀和就是答案

avatar
zc
2020-09-07 16:56:00
查看原题

点击跳转

可以离线处理,按照左右端点排序

考虑每个点的贡献?

记录左边(L_i)/右边(R_i)第一个比它大的地方

  1. 对于区间[L_i,R_i],它有p_1的贡献
  2. 对于区间[l,R_i],l\in [L_i+1,i-1],它有p_2的贡献
  3. 对于区间[L_i,r],r\in [i+1,R_i-1],它有p_2的贡献

每个询问[l,r]可以转化为r的答案减去l-1的答案

把转化后的询问和每个点的贡献区间按位置排序

对于1,我们在扫到R_i时,更新点L_i的贡献

对于2,我们在扫到R_i时,更新区间L_i+1i-1的贡献

对于3,我们在扫到L_i时,更新区间i+1到R_i-1的贡献

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

题意:

给出n个点m条边的无向图,每条边u\leftrightarrow v有两个权值a,b

q个询问,给出u,v,A,Bu,v间是否存在路径\max\{a\}=A\max\{b\}=B

先考虑最暴力的做法:

把所有符合条件的边(a\le A,b\le B)添加到并查集,

然后判断最大值是不是A,Bu,v是否连通

接着对边排序、回滚莫队,使用按秩合并并查集(可撤销并查集)

m条边按a进行排序

对询问按b进行排序

m条边进行分块

对每个块处理符合a大于等于该块\max\{a\}的询问

把当前块前面的点按照b排序(使b单调递增)

开始处理询问:

当前块前面的点的b是单调递增的,而a一定符合条件 ,所以可以一直右移指针添加符合条件的边

然后枚举块中的边,添加符合当前询问的边,得到当前询问答案,回滚,删掉当前询问添加的边

下一个询问

处理完当前块后,暴力清空并查集

分块大小为\sqrt{m\log n}时复杂度最优

avatar
zc
2020-07-18 11:27:00
查看原题

点击跳转

1/2
Search
search