专栏文章

离线算法巩固讲解

CCryn_Frog195
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mindexr8
此快照首次捕获于
2025/12/02 00:35
3 个月前
此快照最后确认于
2025/12/02 00:35
3 个月前
查看原文

前言

离线算法是一种相对巧妙的算法，合适的离线算法可以处置操作或询问复杂的问题。
对于非强制在线问题，考虑直接用离线算法，另外对于强制在线，可以考虑提前记录、可持久化等方法。
总之，离线算法十分重要，然而可以发现，很多人（包括博客）对于离线算法停留在套路层面，这在 OI 圈是非常危险的一件事情。
接下来我会抛开套路讨论离线算法，如果在博客中出现了不会的套路，可以考虑查网上百科。

1. 本质

离线算法意味着已经知道了所有操作，可以将询问分类或统一处理，而无需在不知道后续操作的情况下动态按时间顺序解题。
根据题目的性质，我们可以猜出离线的方式，或许能对应上常见思路。

2. 常见思路

1. 灵活调整顺序

原理

离线意味着顺序可变，我们知道现有的顺序并非好做，所以重新定问题的操作顺序。
常见的包括莫队、逆序处理、区间操作按末尾或开头顺序处理。

CF1422F

可以发现在取模的情况下我们几乎不可能直接求最小公倍数。
然而，我们可以发现最小公倍数在素数分解后约等于对每个质因数求最大值，这时候我们如果按区间末尾递增的顺序处理询问，并用线段树试图维护指定末尾下每个开头的答案，就可以枚举每个数的 O⁡(log⁡n)\operatorname{O}(\log n) 个质因子，每此修改时用单调栈维护后缀最大值，出入栈时对相应的区间做区间乘积，就可以得到一个 O⁡(nlog⁡2n)\operatorname{O}(n\log^2 n) 的做法。
原题加了强制在线，但我们可以使用可持久化线段树，在标记永久化的情况下仍然有 O⁡(nlog⁡2n)\operatorname{O}(n\log^2 n) 的解。
CPP
#include<bits/stdc++.h>
using namespace std;
int n,a[100009],x,y,q;
bool isp[200009];
int pr[200009],prcnt;
stack<pair<int,int> >sq[200009];
const int mod = 1000000007;
int fp(int x,int y){
	if(x == 0)
		return 0;
	if(y == 0)
		return 1;
	int t = fp(x,y >> 1);
	t = 1ll * t * t % mod;
	if(y & 1)
		t = 1ll * t * x % mod;
	return t;
}
unsigned rt[100009];
vector<int>tag,lc,rc;
unsigned add(int k,int l,int r,int lq,int rq,int v){
//	printf("%d %d %d %d %d %d\n",k,l,r,lq,rq,tag[k]);
	if(l > rq || r < lq)
		return k;
	unsigned u = tag.size();
	tag.emplace_back(tag[k]);
	lc.emplace_back(lc[k]);
	rc.emplace_back(rc[k]);
	if(l >= lq && r <= rq){
		tag[u] = 1ll * tag[u] * v % mod;
	}
	else{
		int m = (l + r) >> 1;
		int lsc = add(lc[k],l,m,lq,rq,v),rsc = add(rc[k],m + 1,r,lq,rq,v);
		lc[u] = lsc;
		rc[u] = rsc;
	}
	//printf(" %d %d %d %d %d %d\n",u,l,r,lq,rq,tag[u]);
	return u;
}
int query(int k,int l,int r,int pl){
//	printf(" %d %d %d %d %d\n",k,l,r,pl,tag[k]);
	if(l > pl || r < pl || k == 0)
		return 1;
	else if(l == r)
		return tag[k];
	else{
		int m = (l + r) >> 1;
		return 1ll * tag[k] * query(lc[k],l,m,pl) % mod * query(rc[k],m + 1,r,pl) % mod;
	}
}
int main(){
	tag.emplace_back(1);
	lc.emplace_back(0);
	rc.emplace_back(0);
	isp[1] = isp[0] = true;
	for(int i = 2; i <= 200000; i ++){
		if(!isp[i]){
			pr[++prcnt] = i;
		}
		for(int j = 1; j <= prcnt && i * pr[j] <= 200000; j ++){
			isp[i * pr[j]] = true;
			if(i % pr[j] == 0)
				break;
		}
	}
	scanf("%d",&n);
	for(int i = 1; i <= n; i ++){
		scanf("%d",&a[i]);
		int o = a[i];
		rt[i] = rt[i - 1];
		for(int j = 1; j <= prcnt && pr[j] * pr[j] <= o; j ++){
			if(o % pr[j] == 0){
				int cnt = 0;
				while(o % pr[j] == 0){
					cnt ++;
					o = o / pr[j];
				}
				int l = fp(pr[j],cnt);
				int fl = sq[pr[j]].empty() ? 1 : sq[pr[j]].top().first + 1;
				rt[i] = add(rt[i],1,n,fl,i,l);
				while(!sq[pr[j]].empty() && sq[pr[j]].top().second <= cnt){
					pair<int,int>d = sq[pr[j]].top();
					sq[pr[j]].pop();
					pair<int,int>e = sq[pr[j]].empty() ? make_pair(0,0) : sq[pr[j]].top();
					if(d.second < cnt){
						l = fp(pr[j],cnt - d.second);
						rt[i] = add(rt[i],1,n,e.first + 1,d.first,l);
					}
				}
				sq[pr[j]].push(make_pair(i,cnt));
			}
		}
		if(o != 1){
		//	printf("%d\n",o);
			int fl = sq[o].empty() ? 1 : sq[o].top().first + 1;
			//printf("%d %d %d\n",fl,i,o);
			rt[i] = add(rt[i],1,n,fl,i,o);
			while(!sq[o].empty() && sq[o].top().second <= 1){
				sq[o].pop();
			}
			sq[o].push(make_pair(i,1));
		}
	} 
	scanf("%d",&q);
	int ret = 0;
	while(q--){
		scanf("%d %d",&x,&y);
		x = (x + ret) % n + 1,y = (y + ret) % n + 1;
		if(x > y)
			swap(x,y);
		ret = query(rt[y],1,n,x);
		printf("%d\n",ret);
	}
}

P2521

单题题解；
我们发现原题只有询问和删除，但一些数据结构，如并查集和凸包，对删除不友好，这时考虑反向处理，将删除转化为加入。
这道题是经典的对于凸包的情况，删点需要枚举凸包内的点，而加点可以总体 O⁡(n)\operatorname{O}(n) 次凸包上删除来更新，于是我们换成逆序处理，这样原先的删除就可以当作加入处理。
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,q,tp[200009],id[200009],x,y,a[100009],b[100009];
bool vis[200009];
set<pair<int,int> >p;
double ans,prt[200009];
double dis(int x1,int y1,int x2,int y2){
	return __builtin_sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
void delnode(set<pair<int,int> > :: iterator x){
	auto y = x,z = x;
	//printf("d %d %d\n",x -> first,x -> second);
	y ++,z --;
	ans -= dis(y -> first,y -> second,x -> first,x -> second);
	ans -= dis(z -> first,z -> second,x -> first,x -> second);
	ans += dis(y -> first,y -> second,z -> first,z -> second);
	p.erase(x);
//	printf("%.2lf\n",ans);
}
void addnode(int x,int y){
	//printf("a %d %d\n",x,y);
	auto fx = p.insert(make_pair(x,y)).first;
	auto fy = fx,z = fx;
	fy ++,z --;
	//printf("%d %d %d %d\n",fy -> first,fy -> second,z -> first,z -> second);
	ans += dis(fy -> first,fy -> second,fx -> first,fx -> second);
	ans += dis(z -> first,z -> second,fx -> first,fx -> second);
	ans -= dis(fy -> first,fy -> second,z -> first,z -> second);
}
void pop(int x,int y){
	auto o = p.lower_bound(make_pair(x,y)),fp = o;
	if(o == p.end())
		return;
	fp ++;
	while(p.end() != fp && (o -> second - y) * (fp -> first - o -> first) <= (o -> first - x) * (fp -> second - o -> second))
		delnode(o),o = fp,fp ++;
	o --;
	fp = o;
	if(o == p.begin())
		return;
		fp --;
	while((y - o -> second) * (o -> first - fp -> first) >= (x - o -> first) * (o -> second - fp -> second)){
		delnode(o);
		o = fp;
		if(o != p.begin())
			fp --;
		else
			break;
	}
}
void ins(int x,int y){
	auto o = p.lower_bound(make_pair(x,y));
	auto fp = o;
	fp --;
	if(o -> first == x)
		return;
	else if(fp -> first == x){
		delnode(fp);
		pop(x,y);
		addnode(x,y);
	}
	else if((o -> second - y) * (x - fp -> first) < (o -> first - x) * (y - fp -> second))
		pop(x,y),addnode(x,y);
}
int main(){
	scanf("%d %d %d",&n,&x,&y);
	ans = __builtin_sqrt(x * x + y * y) + __builtin_sqrt((n - x) * (n - x) + y * y);
	p.insert(make_pair(0,0)),p.insert(make_pair(n,0)),p.insert(make_pair(x,y));
	scanf("%d",&m);
	for(int i = 1; i <= m; i ++){
		scanf("%d %d",&a[i],&b[i]);
	}
	scanf("%d",&q);
	for(int i = 1; i <= q; i ++){
		scanf("%d",&tp[i]);
		if(tp[i] == 1){
			scanf("%d",&id[i]);
			if(vis[id[i]])
				id[i] = 0;
			vis[id[i]] = true;
		}
	}
	for(int i = 1; i <= m; i ++)
		if(!vis[i])
			ins(a[i],b[i]);
	for(int i = q; i > 0; i --){
		if(id[i] != 0)
			ins(a[id[i]],b[id[i]]);
		else if(tp[i] == 2)
			prt[i] = ans;
		//printf("%.2lf\n",ans);
	}
	for(int i = 1; i <= q; i ++)
		if(tp[i] == 2)
			printf("%.2lf\n",prt[i]);
	return 0;
}

P9531

这道题中按 xx 大小从小到大处理，会变成最大生成树问题。而两条边的交换时间就是边权在数轴上形成的线段的中点代表的整数，接下来就可以迅速处理了。
CPP
//暴力维护最大生成树
//记得处理区间
//用离散化+差分解决问题
//对于任意问题，询问+差分为宜 
//为了卡常，先不引用std 
#include<cstdio>
#include<map>
#include<algorithm>
#include<cstring>
int n,m,q,x,l[100005],r[100005],s3[200005],s4[200005];
long long s1[200005],s2[200005];//i号边出现在[l_i,r_i),预计2m个中转点 

struct edge1{//第一种存边方式，处理每条边出现空间 
	int u,v,w;
	bool operator<(const edge1 &b)const{
		return w < b.w;
	}
}e1[100009];

struct edge2{
	int to,id,nxt,prev,ssp;
}e2[200009];
int cnt,st[509];
void add(int x,int y,int id){//链式加边 
	cnt++;
	e2[cnt].to = y;
	e2[cnt].id = id;
	e2[cnt].nxt = st[x];
	e2[st[x]].prev = cnt;
	st[x] = cnt;
	e2[cnt].ssp = x;
	
	cnt++;
	e2[cnt].to = x;
	e2[cnt].id = id;
	e2[cnt].nxt = st[y];
	e2[st[y]].prev = cnt;
	st[y] = cnt;
	e2[cnt].ssp = y;
}
void del(int id){//链式删边
	int did = (id << 1) - 1;//实际删边编号 
	if(e2[did].prev == 0){
		st[e2[did].ssp] = e2[did].nxt;
	}
	else{
		e2[e2[did].prev].nxt = e2[did].nxt;
	}
	
	if(e2[did].nxt != 0){
		e2[e2[did].nxt].prev = e2[did].prev;
	}
	
	
	did = (id << 1);//实际删边编号 
	if(e2[did].prev == 0){
		st[e2[did].ssp] = e2[did].nxt;
	}
	else{
		e2[e2[did].prev].nxt = e2[did].nxt;
	}
	
	if(e2[did].nxt != 0){
		e2[e2[did].nxt].prev = e2[did].prev;
	}
}

int minid[509];
void srh(int nk,int l,int mid){
	minid[nk] = mid;
	for(int i = st[nk]; i != 0; i = e2[i].nxt){
		if(e2[i].to == l)//不走父节点 
			continue;
		
		srh(e2[i].to,nk,std :: min(mid,e2[i].id));
	}
}
void get_qj(){
	std :: sort(e1 + 1,e1 + m + 1);
	for(int i = 1; i <= m; i ++){
		for(int j = 1; j <= n; j ++){
			minid[j] = 1919810;
		}
		l[i] = 1,r[i] = 1e9 + 7;//初值 
		
		srh(e1[i].u,0,1919810);//没有变的编号大于1919810
		
		if(minid[e1[i].v] < 1919810) {//删边
			r[minid[e1[i].v]] = l[i] = ((e1[i].w + e1[minid[e1[i].v]].w) >> 1) + 1;
			del(minid[e1[i].v]);
		}
		
		add(e1[i].u,e1[i].v,i);
	}
}

int vp[300009],cntv,cntm,bk[300009];
std :: map<int,int>mp;
void lsh(){//离散化 
	cntv = 1;
	vp[1] = 1e9 + 7;
	for(int i = 1; i <= m; i ++){
		vp[++cntv] = l[i];
		vp[++cntv] = e1[i].w;
		vp[++cntv] = r[i];
	}
	std :: sort(vp + 1, vp + cntv + 1);
	for(int i = 1; i <= cntv; i ++){
		if(i == 1 || vp[i] != vp[i - 1]){
			mp[vp[i]] = ++ cntm;
			bk[cntm] = vp[i];
		}
	}
}

void rcl(){//预处理差分
	for(int i = 1; i <= m; i ++){
		int lf = mp[l[i]],rt = mp[r[i]],ws = mp[e1[i].w];
		//printf("%d %d %d %d %d\n",i,lf,ws,rt,e1[i].w);
		s1[lf] += e1[i].w;
		s3[lf] ++;
		s1[ws] -= e1[i].w;
		s3[ws] --;
		
		s2[ws] += e1[i].w;
		s4[ws] ++;
		s2[rt] -= e1[i].w;
		s4[rt] --;
	} 
	for(int i = 1; i <= cntm; i ++){
		s1[i] += s1[i - 1];
		s2[i] += s2[i - 1];
		s3[i] += s3[i - 1];
		s4[i] += s4[i - 1];
	}
}
char read_char(){//光速度字符 
	static const unsigned int read_len = 99967;
	static char buf[read_len],*p1,*p2;
	return (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,read_len,stdin),p1 == p2)) ? EOF : *p1++;
}
template<typename T>
T read_int(){//光速读整形 
	T x = 0,f = 1;
	char c = ' ';
	while((c > '9' || c < '0') && c != '-')
	    c = read_char();
	if(c == '-'){
		f = -1;
		c = read_char();
	}
	while(c <= '9' && c >= '0'){
		x = x * 10 + c - '0';
		c = read_char(); 
	}
	return x * f;
}
int main(){
	n = read_int<int>(),m = read_int<int>();
	for(int i = 1; i <= m; i ++){
		e1[i].u = read_int<int>(),e1[i].v = read_int<int>(),e1[i].w = read_int<int>();
	}
	
	get_qj();
	lsh();
	rcl();
	
	q = read_int<int>();
	while(q--){
		x = read_int<int>();
		int lp = 1,rp = cntm + 1;
		while(lp + 1 < rp){
			int mid = (lp + rp) >> 1;
			if(bk[mid] <= x)lp = mid;
			else rp = mid;
		}
		long long ans = (long long) 1ll * x * s4[lp] - s2[lp] + s1[lp] - 1ll * x * s3[lp];
		printf("%lld\n",ans);
	}
	return 0;
}

2. 将时间视作一个变量

原理

当时间成为了一个变量而非一个顺序时，我们其实可以转化问题，进一步找出更好解决的等价问题。

P3157

这道题是一个逆序对问题，然而删除操作使得题目变得复杂。
这时将删除时间视作一维，计算删除一个元素的贡献，会变成经典的三维偏序问题。
CPP
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,n_,ads[100001];
struct value{
    int a,b,c,id;
}p[100001],t[100001];
int lp[(1<<19)],_n;
inline void cin(int &x){
    x=0;
    bool f=false;
    char c;
    while((c<'0'||c>'9')&&c!='-')c=getchar();
    if(c=='-'){
        f=true;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=x*10+c-'0';
        c=getchar();
    }
    if(f)x=-x;
}
inline void cout(long long f){
    if(f<0){
    putchar('-');
    f=-f;
   }
   if(f>=10)cout(f/10);
   putchar(f%10+'0');
}
inline void add(int pl,int val){
    for(int i=pl;i<=n_;i+=(-i)&i)
        lp[i]+=val;
}
inline int query(int pl){
    int s=0;
    for(int i=pl;i>0;i&=i-1){s+=lp[i];}
    return s;
}
inline bool cmp(value x,value y){
    return x.a<y.a;
}
inline bool cmp1(value x,value y){
    return x.id<y.id;
}
inline void solve(int l,int r){
    if(l==r)return ;
    int mid=(l+r)>>1;
    solve(l,mid),solve(mid+1,r);
    for(int i=l-1,j=mid+1;j<=r;j++){
        while(i<mid&&p[i+1].b<p[j].b){i++;add(p[i].c,1);}
        ads[p[j].id]+=query(p[j].c-1);
    }
    for(int i=l;i<=mid&&p[i].b<p[r].b;i++)add(p[i].c,-1);
    int lp=l,rp=mid+1,cnt=0;
    while(lp<=mid||rp<=r){
        if(lp>mid||(rp<=r&&p[lp].b>p[rp].b)){
            t[++cnt]=p[rp++];
        }
        else 
            t[++cnt]=p[lp++];
    }
    for(int i=1;i<=cnt;i++){
        p[i+l-1]=t[i];
    }
}
inline long long solve1(int l,int r){
    if(l==r)return 0ll;
    int mid=(l+r)>>1;
    long long ans=solve1(l,mid)+solve1(mid+1,r);
    int lp=l,rp=mid+1,cnt=0;
    while(lp<=mid||rp<=r){
        if(lp>mid||(rp<=r&&p[lp].a<p[rp].a)){
            ans+=mid-lp+1;
            t[++cnt]=p[rp++];
        }
        else 
            t[++cnt]=p[lp++];
    }
    for(int i=1;i<=cnt;i++){
        p[i+l-1]=t[i];
    }
    return ans;
}
int s[100001],kp[50001];
int main(){
    cin(n),cin(k);
    n_=1;
    while(n_<=k)n_*=2;
    for(int i=1;i<=n;i++){
        cin(p[i].a);
        p[i].id=i;
        p[i].b=n+1-i;
        s[p[i].a]=i;
        p[i].c=1;
    }
    for(int i=1;i<=k;i++){
        cin(kp[i]);
        p[s[kp[i]]].c=k+2-i;
    }
    sort(p+1,p+n+1,cmp);
    solve(1,n);
    sort(p+1,p+n+1,cmp1);
    for(int i=1;i<=n;i++){
        p[i].a=n+1-p[i].a;
        p[i].b=i;
    }
    sort(p+1,p+n+1,cmp);
    solve(1,n);
    sort(p+1,p+n+1,cmp1);
    long long sum=solve1(1,n);
    for(int i=1;i<=k;i++){
        cout(sum);
        putchar('\n');
        sum-=ads[s[kp[i]]];
    }
    return 0;
}

3. 分治

原理

这里是广义上的分治思想，包括线段树分治、整体二分、树分治、CDQ 分治。
分治是当在某一层面上出现原问题可分为子问题的同时是子问题合并时，考虑分治，常见的分治对象包括答案（整体二分），树上问题的所在树（树分治），时间轴。对时间轴的区间修改可以用类似于线段树的处理方法（线段树分治）。

P5311

这道题由于连通块中颜色不好处理，考虑转化为能到达的点的颜色数并考虑树分治，而在树分治中又可以按保留点的最大标号顺序离线，这样就得到了解法。
CPP
//18:50-19:48
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,x;
struct line{
	int l,r,t,c;
	line(int _l = 0,int _r = 0,int _t = 0,int _c = 0):
		l(_l),r(_r),t(_t),c(_c)
	{}
	bool operator<(const line &b)const{
		return r < b.r || (r == b.r && t > b.t);
	}
};
vector<line>l1,l2,q[100009];
vector<int>e[100009];
int bit[100009];
void add(int p,int v){
	for(int i = p; i <= n; i += i & (-i))
		bit[i] += v;
}
int query(int p){
	int ans = 0;
	for(int i = p; i > 0; i &= i - 1)
		ans += bit[i];
	return ans;
}
int sz[100009],col[100009],las[100009],ans[100009];
bool c[100009];
void srh1(int v,int fa){
	sz[v] = 1;
	for(int i = 0; i < e[v].size(); i ++)
		if(e[v][i] != fa && !c[e[v][i]])
			srh1(e[v][i],v),sz[v] += sz[e[v][i]];
}
void srh2(int v,int fa,int mx,int mn){
	mx = max(mx,v);
	mn = min(mn,v);
	l1.emplace_back(line(mn,mx,1,col[v]));
	l2.emplace_back(line(mn,mx,1,col[v]));
	for(int i = 0; i < q[v].size(); i ++)
		if(mx <= q[v][i].r && mn >= q[v][i].l)
			l1.emplace_back(q[v][i]),l2.emplace_back(q[v][i]);
	for(int i = 0; i < e[v].size(); i ++)
		if(e[v][i] != fa && !c[e[v][i]])
			srh2(e[v][i],v,mx,mn);
}
int srh3(int v,int fa,int tot){
	int o = tot - sz[v];
	for(int i = 0; i < e[v].size(); i ++)
		if(e[v][i] != fa && !c[e[v][i]])
			o = max(o,sz[e[v][i]]);
	if(o * 2 <= tot)
		return v;
	for(int i = 0; i < e[v].size(); i ++)
		if(e[v][i] != fa && !c[e[v][i]]){
			int o = srh3(e[v][i],v,tot);
			if(o != -1)
				return o;
		}
	return -1;
}
void slv(int x){
	srh1(x,0);
	int v = srh3(x,0,sz[x]);
	c[v] = true;
	for(int i = 0; i < q[v].size(); i ++)
		l1.emplace_back(q[v][i]);
	l1.emplace_back(line(v,v,1,col[v]));
	for(int i = 0; i < e[v].size(); i ++){
		if(!c[e[v][i]]){
			srh2(e[v][i],v,v,v);
			sort(l2.begin(),l2.end());
			int cst = 0;
			for(int j = 0; j < l2.size(); j ++){
				if(l2[j].t == 1){
					if(las[l2[j].c] >= l2[j].l)
						continue;
					if(las[l2[j].c] > 0)
						add(las[l2[j].c],-1);
					else
						cst ++;
					las[l2[j].c] = l2[j].l;
					add(las[l2[j].c],1);
				}
				else{
					//printf("%d %d %d %d %d\n",v,e[v][i],l2[j].c,query(l2[j].l - 1),cst);
					ans[l2[j].c] += query(l2[j].l - 1) - cst;
				}
			}
			for(int j = 0; j < l2.size(); j ++){
				if(l2[j].t == 1){
					if(las[l2[j].c] > 0)
						add(las[l2[j].c],-1),las[l2[j].c] = 0;
				}
			}
			l2.clear();
		}
	}
	sort(l1.begin(),l1.end());
	int cst = 0;
	for(int j = 0; j < l1.size(); j ++){
		//printf(" %d %d %d %d %d\n",l1[j].l,l1[j].r,l1[j].t,l1[j].c,las[l1[j].c]);
		if(l1[j].t == 1){
			if(las[l1[j].c] >= l1[j].l)
				continue;
			if(las[l1[j].c] > 0)
				add(las[l1[j].c],-1);
			else
				cst ++;
			las[l1[j].c] = l1[j].l;
			add(las[l1[j].c],1);
		}
		else{
		//	printf("%d %d %d %d\n",v,l1[j].c,cst,query(l1[j].l - 1));
			ans[l1[j].c] += cst - query(l1[j].l - 1);
		}
	}
	for(int j = 0; j < l1.size(); j ++){
		if(l1[j].t == 1){
			if(las[l1[j].c] > 0)
				add(las[l1[j].c],-1),las[l1[j].c] = 0;
		}
	}
	l1.clear();
	for(int i = 0; i < e[v].size(); i ++)
		if(!c[e[v][i]])
			slv(e[v][i]);
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; i ++){
		scanf("%d",&col[i]);
	}
	for(int i = 1; i < n; i ++){
		int u,v;
		scanf("%d %d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i= 1; i <= m; i ++){
		scanf("%d %d %d",&a,&b,&x);
		q[x].push_back(line(a,b,-1,i)); 
	}
	slv(1);
	for(int i = 1; i <= m; i ++)
		printf("%d\n",ans[i]);
	return 0;
}

CF576E

我们发现询问间有边涂色，拆点后相当于增删便，而增删边不好处理（你可以用 LCT，但 LCT 有多难路人皆知），考虑用线段树分治。
这个时候出现了询问间有依赖的问题，但依赖关系总是从左向右的，这个时候可以先递归左边，同时动态做区间加边，用可持久化并查集处理图是否为二分图的问题。
对于拆点过多的情况，由于我们是离线算法，可以只保留操作涉及的 O⁡(m)\operatorname{O}(m) 个点，从而得到答案。
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,k,q,prv[500009],nxt[500009],idfe[500009],ad[500009];
struct edge{
	int u,v;
}e[500009],e2[500009];
struct chl{
	int e,c;
}c[500009];
vector<int>v[59],st[59];
int sum,fa[2000009],sz[2000009],stk[2000009],top;
bool ans[500009];
int fnd(int x){
	return fa[x] == x ? x : fnd(fa[x]);
}
bool Union(int x,int y){
	int u = fnd(x),v = fnd(y);
	if(u == v)
		return false;
	if(sz[u] > sz[v])
		swap(u,v);
	fa[u] = v;
	sz[v] += sz[u];
	stk[++top] = u;
	return true;
}
void undo(){
	int o = stk[top];
	top --;
	sz[fa[o]] -= sz[o];
	fa[o] = o;
}
vector<int>et[2000009];
void add(int k,int l,int r,int lq,int rq,int id){
	if(l > rq || r < lq)
		return;
	if(l >= lq && r <= rq){
	//	printf(" %d %d %d %d\n",l,r,lq,rq);
		et[k].emplace_back(id);
	}
	else{
		int m = (l + r) >> 1;
		add(k << 1,l,m,lq,rq,id);
		add((k << 1) | 1,m + 1,r,lq,rq,id);
	}
}
void query(int k,int l,int r){
	int s = 0;
	for(int i = 0; i < et[k].size(); i ++){
		s += Union(e2[et[k][i]].u << 1,e2[et[k][i]].v * 2 - 1);
		s += Union(e2[et[k][i]].u * 2 - 1,e2[et[k][i]].v << 1);
	}
	if(l == r){
	//	printf("%d %d %d %d %d %d\n",e2[l].u,e2[l].v,fnd(e2[l].u << 1),fnd(e2[l].v << 1),prv[l],nxt[l]);
		if(fnd(e2[l].u << 1) != fnd(e2[l].v << 1)){
			ans[l] = true;
			ad[l] = l;
			add(1,1,q,l + 1,nxt[l] - 1,l);
		}
		else if(ad[prv[l]] != 0){
			ad[l] = ad[prv[l]];
			add(1,1,q,l + 1,nxt[l] - 1,ad[prv[l]]);
		}
	}
	else{
		int m = (l + r) >> 1;
		query(k << 1,l,m);
		query((k << 1) | 1,m + 1,r);
	} 
	while(s--)
		undo();
}
int main(){
	scanf("%d %d %d %d",&n,&m,&k,&q);
	for(int i = 1; i <= m; i ++){
		scanf("%d %d",&e[i].u,&e[i].v);
	}
	for(int i = 1; i <= q; i ++){
		scanf("%d %d",&c[i].e,&c[i].c);
		v[c[i].c].emplace_back(e[c[i].e].u);
		v[c[i].c].emplace_back(e[c[i].e].v);
		st[c[i].c].emplace_back(i);
		if(idfe[c[i].e]){
			//printf("%d %d\n",idfe[c[i].e],i);
			prv[i] = idfe[c[i].e];
			nxt[idfe[c[i].e]] = i;
		}
		idfe[c[i].e] = i;
		nxt[i] = q + 1;
	}
	//for(int i = 1; i <= q; i ++)
	//	printf(" %d %d %d\n",i,prv[i],nxt[i]);
	for(int i = 1; i <= k; i ++){
		sort(v[i].begin(),v[i].end());
		unsigned o = unique(v[i].begin(),v[i].end()) - v[i].begin();
		v[i].resize(o);
		for(unsigned i = 0; i < o; i ++){
			fa[(i + sum + 1 << 1) - 1] = (i + sum + 1 << 1) - 1;
			sz[(i + sum << 1) | 1] = 1;
			fa[(i + sum + 1 << 1)] = (i + sum + 1 << 1);
			sz[(i + sum + 1 << 1)] = 1;
		}
		for(int j = 0; j < st[i].size(); j ++){
			unsigned pt1 = lower_bound(v[i].begin(),v[i].end(),e[c[st[i][j]].e].u) - v[i].begin();
			e2[st[i][j]].u = pt1 + sum + 1;
			pt1 = lower_bound(v[i].begin(),v[i].end(),e[c[st[i][j]].e].v) - v[i].begin();
			e2[st[i][j]].v = pt1 + sum + 1;
		}
		sum += o;
	}
	//for(int i = 1; i <= q; i ++)
	//	printf(" %d %d %d\n",i,prv[i],nxt[i]);
	query(1,1,q);
	for(int i = 1; i <= q; i ++)
		puts(ans[i] ? "YES" : "NO");
}

4. 数据结构维护询问

在部分问题中，将询问用数据结构维护，并遍历元素来更新相应的询问可以做到更优。这件事情在ACAM题中异常常见，可以说也是相对常见的离线类型。

CF44G

单题题解
相比于找包含指定点的方形，我们更倾向于找指定方形包含的点，后者是K-D树或的长项，于是我们反过来找到每个“靶子”的矩形包含的最早射出的“子弹”，然后把子弹删掉，被删掉的子弹的答案即为靶子的编号。
CPP
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100009,M = 100009;
struct tar{
	int xmn,xmx,ymx,ymn,z,id;
	bool operator<(const tar &b)const{
		return z < b.z;
	} 
}t[N];
int sid[M];
struct kdtree{
	int x,y,xmn = 0x3f3f3f3f,ymn = 0x3f3f3f3f,xmx = -1,ymx = -1,t = 0x3f3f3f3f,mid;
	int lc,rc;
	bool dt;
}nd[M];
bool cmp1(kdtree tx,kdtree ty){
	return tx.x < ty.x;
}
bool cmp2(kdtree tx,kdtree ty){
	return tx.y < ty.y;
}
int build(int l,int r,int k){
	if(l > r)
		return 0;
	if(l == r){
		nd[l].xmn = nd[l].x;
		nd[l].ymn = nd[l].y;
		nd[l].xmx = nd[l].x;
		nd[l].ymx = nd[l].y;
		nd[l].mid = l;
		return l;
	}
	int u = (l + r) >> 1;
	nth_element(nd + l,nd + u,nd + r + 1,k == 0 ? cmp1 : cmp2);
	//printf(" %d %d\n",l,r); 
	nd[u].lc = build(l,u - 1,k ^ 1);
	nd[u].rc = build(u + 1,r,k ^ 1);
	//printf("%d %d\n",nd[u].x,nd[u].y);
	nd[u].xmn = min(nd[u].x,min(nd[nd[u].lc].xmn,nd[nd[u].rc].xmn));
	nd[u].ymn = min(nd[u].y,min(nd[nd[u].lc].ymn,nd[nd[u].rc].ymn));
	nd[u].xmx = max(nd[u].x,max(nd[nd[u].lc].xmx,nd[nd[u].rc].xmx));
	nd[u].ymx = max(nd[u].y,max(nd[nd[u].lc].ymx,nd[nd[u].rc].ymx));
	nd[u].mid = u;
	if(nd[nd[u].mid].t > nd[nd[nd[u].lc].mid].t)
		nd[u].mid = nd[nd[u].lc].mid;
	if(nd[nd[u].mid].t > nd[nd[nd[u].rc].mid].t)
		nd[u].mid = nd[nd[u].rc].mid;
	//printf("%d %d %d %d\n",nd[u].xmn,nd[u].ymn,nd[u].xmx,nd[u].ymx);
	return u;
}
void kill(int k,int px,int py,int pt){
	if(nd[k].xmn > px || nd[k].xmx < px || nd[k].ymn > py || nd[k].ymx < py)
		return;
	if(nd[k].x == px && nd[k].y == py && nd[k].t == pt){
		nd[k].dt = true;
		nd[k].x = 0x3f3f3f3f,nd[k].y = 0x3f3f3f3f,nd[k].t = 0x3f3f3f3f;
		nd[k].xmn = min(nd[k].dt ? 0x3f3f3f3f : nd[k].x,min(nd[nd[k].lc].xmn,nd[nd[k].rc].xmn));
		nd[k].ymn = min(nd[k].dt ? 0x3f3f3f3f : nd[k].y,min(nd[nd[k].lc].ymn,nd[nd[k].rc].ymn));
		nd[k].xmx = max(nd[k].dt ? -1 : nd[k].x,max(nd[nd[k].lc].xmx,nd[nd[k].rc].xmx));
		nd[k].ymx = max(nd[k].dt ? -1 : nd[k].y,max(nd[nd[k].lc].ymx,nd[nd[k].rc].ymx));
		nd[k].mid = 0;
		if(nd[nd[k].mid].t > nd[nd[nd[k].lc].mid].t)
			nd[k].mid = nd[nd[k].lc].mid;
		if(nd[nd[k].mid].t > nd[nd[nd[k].rc].mid].t)
			nd[k].mid = nd[nd[k].rc].mid;
		return;
	}
	kill(nd[k].lc,px,py,pt);
	kill(nd[k].rc,px,py,pt);
	nd[k].xmn = min(nd[k].dt ? 0x3f3f3f3f : nd[k].x,min(nd[nd[k].lc].xmn,nd[nd[k].rc].xmn));
	nd[k].ymn = min(nd[k].dt ? 0x3f3f3f3f : nd[k].y,min(nd[nd[k].lc].ymn,nd[nd[k].rc].ymn));
	nd[k].xmx = max(nd[k].dt ? 0 : nd[k].x,max(nd[nd[k].lc].xmx,nd[nd[k].rc].xmx));
	nd[k].ymx = max(nd[k].dt ? 0 : nd[k].y,max(nd[nd[k].lc].ymx,nd[nd[k].rc].ymx));
	nd[k].mid = k;
	if(nd[nd[k].mid].t > nd[nd[nd[k].lc].mid].t)
		nd[k].mid = nd[nd[k].lc].mid;
	if(nd[nd[k].mid].t > nd[nd[nd[k].rc].mid].t)
		nd[k].mid = nd[nd[k].rc].mid;
	return;
}
int kid;
void fnd(int k,int qs){
	//printf("%d %d %d %d %d %d %d %d\n",t[qs].xmn,t[qs].ymn,t[qs].xmx,t[qs].ymx,nd[k].xmn,nd[k].ymn,nd[k].xmx,nd[k].ymx);
	if(t[qs].xmn > nd[k].xmx || t[qs].xmx < nd[k].xmn || t[qs].ymn > nd[k].ymx || t[qs].ymx < nd[k].ymn || nd[k].mid == 0)
		return;
	if(t[qs].xmx >= nd[k].xmx && t[qs].xmn <= nd[k].xmn && t[qs].ymx >= nd[k].ymx && t[qs].ymn <= nd[k].ymn){
		if(nd[kid].t > nd[nd[k].mid].t)
			kid = nd[k].mid;
		return;
	}
	else if(t[qs].xmx >= nd[k].x && t[qs].xmn <= nd[k].x && t[qs].ymx >= nd[k].y && t[qs].ymn <= nd[k].y){
		if(nd[kid].t > nd[k].t)
			kid = k;
	}
	fnd(nd[k].lc,qs);
	fnd(nd[k].rc,qs);
}
int n,m;
int main(){
	scanf("%d",&n);
	for(int i = 1; i <= n; i ++){
		scanf("%d %d %d %d %d",&t[i].xmn,&t[i].xmx,&t[i].ymn,&t[i].ymx,&t[i].z);
		t[i].id = i;
	}
	sort(t + 1,t + n + 1);
	scanf("%d",&m);
	for(int i = 1; i <= m; i ++){
		scanf("%d %d",&nd[i].x,&nd[i].y);
		nd[i].t = i;
	}
	int rt = build(1,m,0);
	for(int i = 1; i <= n; i ++){
		kid = 0;
		fnd(rt,i);
		//printf("%d\n",nd[kid].t);
		if(kid != 0){
			sid[nd[kid].t] = t[i].id;
			kill(rt,nd[kid].x,nd[kid].y,nd[kid].t);
		}
	}
	for(int i = 1; i <= m; i ++)
		printf("%d\n",sid[i]);
	return 0;
}

P6257

首先将字符串都倒过来，可以把询问从前缀匹配改为后缀匹配，皇后名字的延伸从向前扩展到向后扩展，将询问用 ACAM 维护，跑一遍皇后名字对应的字典树来更新 ACAM，最后通过 ACAM 的 fail 树子树和即可得到答案。
CPP
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ch[2000009][26],ret[2000009],fail[2000009],cnt = 1,q[1000009];
char c[1000009];
int add(int cur,int v){
	if(c[v] == '\0')
		return cur;
	if(ch[cur][c[v] - 'A'] == 0)
		ch[cur][c[v] - 'A'] = ++cnt;
	return add(ch[cur][c[v] - 'A'],v + 1);
}
int qu[2000009],head,tail;
vector<int>e[2000009];
void gt_fail(){
	fail[1] = 1;
	head = 1,tail = 0;
	for(int i = 0; i < 26; i ++){
		if(ch[1][i] != 0){
			fail[ch[1][i]] = 1;
			qu[++tail] = ch[1][i];
		}
		else
			ch[1][i] = -1;
	}
	while(head <= tail){
		int d = qu[head];
		head ++;
		e[fail[d]].push_back(d);
		for(int i = 0; i < 26; i ++){
			if(ch[d][i] != 0){
				fail[ch[d][i]] = abs(ch[fail[d]][i]);
				qu[++tail] = ch[d][i];
			}
			else
				ch[d][i] = -abs(ch[fail[d]][i]);
		}
	}
}
int srh(int v){
	for(int i = 0; i < e[v].size(); i ++)
		ret[v] += srh(e[v][i]);
	return ret[v];
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; i ++){
		int p;
		scanf(" %c %d",&c[0],&p);
		cnt ++;
		ch[p + 1][c[0] - 'A'] = i + 1;
		ret[i + 1] = 1;
	}
	for(int i = 1; i <= m; i ++){
		scanf(" %s",c);
		int o = strlen(c);
		reverse(c,c + o);
		q[i] = add(1,0);
	}
	gt_fail();
	srh(1);
	for(int i = 1; i <= m; i ++){
		printf("%d\n",ret[q[i]]);
	} 
	return 0;
}

5. 离线的嵌套

虽然是离线算法，但以离线后的处理顺序处理时仍然可能有一部分时相对在线更新的，这些部分可以再次离线，即离线嵌套离线。
目前离线嵌套离线的实际运用并不多，比较知名的是莫队二次离线。

P5047

这道题多次询问逆序对不好做，考虑莫队，然而莫队的更新也不好处理。
当一次离线不好处理，考虑将第一次离线动态更新的部分再次离线，这里二次离线时每次修改求贡献是，可以发现修改呈现为一个修改区间和另一个相邻的保有区间（即删除后或加入前的莫队处理到的区间）。考虑改变时改变量可以以修改区间与保有区间的分界点顺序分块处理，这样我们就有了二次离线做法。
CPP
//50 - 80 min E
#include<cstdio>
#include<map>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int n,m,a[100009],v[100009],bl[100009],B,l[509],r[509],cnt[100009],zcnt[509],cntv,qB;
map<int,int>mp;
struct query{
	int l,r,id,val;
	query(int _l = 0,int _r = 0,int _i = 0,int _v = 0){
		l = _l,r = _r,id = _i,val = _v;
	}
	bool operator<(const query &b)const{
		return (l + qB - 1) / qB < (b.l + qB - 1) / qB || ((l + qB - 1) / qB == (b.l + qB - 1) / qB && r < b.r);
	}
}q[100009];
vector<query>v1[100009],v2[100009];
long long ans[100009],dt1[100009],dt2[100009];
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n; i ++){
		scanf("%d",&a[i]);
		v[i] = a[i]; 
	}
	sort(v + 1,v + n + 1);
	cntv = unique(v + 1,v + n + 1) - (v + 1);
	for(int i = 1; i <= cntv; i ++){
		mp[v[i]] = i;
	}
	for(int i = 1; i <= n; i ++)
		a[i] = mp[a[i]];
	qB = sqrt(n) + 0.5;
	B = sqrt(cntv);
	for(int i = 1; i <= m; i ++){
		scanf("%d %d",&q[i].l,&q[i].r);
		q[i].id = i;
	}
	sort(q + 1,q + m + 1);
	for(int i = 1; r[i - 1] < n; i ++){
		l[i] = r[i - 1] + 1;
		r[i] = min(n,r[i - 1] + B);
		for(int j = l[i]; j <= r[i]; j ++){
			bl[j] = i;
		}
	}
	v1[q[1].l - 1].push_back(query(q[1].l,q[1].r,q[1].id,-1));
	int nl = q[1].l,nr = q[1].r;
	for(int i = 2; i <= m; i ++){
		if(q[i].r > nr){
			v1[nl - 1].push_back(query(nr + 1,q[i].r,q[i].id,-1));
			nr = q[i].r;
		}
		if(nl > q[i].l){
			v2[nr + 1].push_back(query(q[i].l,nl - 1,q[i].id,-1));
			nl = q[i].l;
		}
		if(nr > q[i].r){
			v1[nl - 1].push_back(query(q[i].r + 1,nr,q[i].id,1));
			nr = q[i].r;
		}
		if(nl < q[i].l){
			v2[nr + 1].push_back(query(nl,q[i].l - 1,q[i].id,1));
			nl = q[i].l;
		}
	}
	for(int i = 1; i <= n; i ++){
		dt1[i] = dt1[i - 1] + cnt[a[i]] + zcnt[bl[a[i]]];
	//	printf("%lld\n",dt1[i]);
		for(int j = 1; j < bl[a[i]]; j ++)
			zcnt[j]++;
		for(int j = l[bl[a[i]]]; j < a[i]; j ++)
			cnt[j] ++;
		for(int j = 0; j < v1[i].size(); j ++){
			for(int k = v1[i][j].l; k <= v1[i][j].r; k ++){
				ans[v1[i][j].id] += (cnt[a[k]] + zcnt[bl[a[k]]]) * v1[i][j].val;
			}
		}
	} 
	for(int i = 1; i <= cntv; i ++)
		cnt[i] = 0;
	for(int i = 1; i <= bl[cntv]; i ++)
		zcnt[i] = 0;
	for(int i = n; i > 0; i --){
		dt2[i] = dt2[i + 1] + cnt[a[i]] + zcnt[bl[a[i]]];
		for(int j = bl[a[i]] + 1; j <= bl[cntv]; j ++)
			zcnt[j]++;
		for(int j = a[i] + 1; j <= r[bl[a[i]]]; j ++)
			cnt[j] ++;
		for(int j = 0; j < v2[i].size(); j ++){
			for(int k = v2[i][j].l; k <= v2[i][j].r; k ++){
				ans[v2[i][j].id] += (cnt[a[k]] + zcnt[bl[a[k]]]) * v2[i][j].val;
			}
		}
	} 
	for(int i = 1; i <= cntv; i ++)
		cnt[i] = 0;
	for(int i = 1; i <= bl[cntv]; i ++)
		zcnt[i] = 0;
	ans[q[1].id] += dt1[q[1].r] - dt1[q[1].l - 1];
//	printf("%d %d %d\n",q[1].id,q[1].r,q[1].l);
	nl = q[1].l,nr = q[1].r;
	for(int i = 2; i <= m; i ++){
		ans[q[i].id] += ans[q[i - 1].id];
		if(q[i].r > nr){
			ans[q[i].id] += dt1[q[i].r] - dt1[nr];
			nr = q[i].r;
		}
		if(nl > q[i].l){
			ans[q[i].id] += dt2[q[i].l] - dt2[nl];
			nl = q[i].l;
		}
		if(nr > q[i].r){
			ans[q[i].id] += dt1[q[i].r] - dt1[nr];
			nr = q[i].r;
		}
		if(nl < q[i].l){
			ans[q[i].id] += dt2[q[i].l] - dt2[nl];
			nl = q[i].l;
		}
	}
	for(int i = 1; i <= m; i ++)
		printf("%lld\n",ans[i]);
	return 0;
}

3. 关于离散化

离散化并非离线算法的核心思想，但是是离线算法中较为重要的锦上添花的内容。
在离线情况下，我们可以将询问出现的端点保留，其余点合并处理或甚至无需处理，从而减小维护的元素，是算法更优。

4. 总结

离线算法是指将所有操作全部读完后在处理，利用与在线算法之间的信息差，可以更灵活地对问题作分类或统一处理。
通过可持久化和提前记录等方法，可以形成基于离线算法的在线算法，应对强制在线问题。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...