首页 > 其他分享 >线段树分治小结

线段树分治小结

时间：2024-08-01 10:07:47浏览次数：12  
标签：cnt int 线段 分治 st define 小结 top fo

一般来说，这种题目是给定一些信息，比如说边，然后这些信息会在一个时间段内出现。

一般来说需要离线，然后建立一棵以维护每个时刻信息的线段树，具体来说就是在每个节点维护一个vector。

#121. 「离线可过」动态图连通性
以经典例题来说，我们根据每条边出现的时刻将它插入到线段树上对应时间区间的节点上。

当我们查询时，就从上至下递归，依次加边，用一个并查集维护连通性。
然后需要注意的是，当我们离开一个区间时，我们需要撤销并查集的连边操作，因此不能使用路径压缩，而要使用按秩合并，具体来说就是用一个栈来记录进入这个区间后多连了那些边，然后倒序撤销即可。

#include <bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
#define lc (o<<1)
#define rc ((o<<1)|1)
using namespace std;
typedef long long ll;
typedef double db;
const int N = 5e5 + 5;
const ll mo = 998244353;
struct node {
    int x, y;
};
node s[N];
vector<node> e[N * 4];
struct key {
    int x, y, id;
};
vector<key> q[N * 4];
int n, a[5005][5005], f[N], sz[N], m, x, y, op, f1, f2, top, ans[N];
bool flag;
void del(int now) {
    while (top > now) {
        f1 = s[top].x;
        f2 = s[top].y;
        top--;

        f[f2] = f2;
        sz[f1] -= sz[f2];
    }
}
int find(int x) {
    if (x == f[x])
        return x;

    return find(f[x]);
}
void upd(int o, int l, int r, int x, int y, int u, int v) {
    if (x <= l && r <= y) {
        e[o].push_back((node) {
            u, v
        });
        return;
    }

    int m = (l + r) >> 1;

    if (x <= m)
        upd(lc, l, m, x, y, u, v);

    if (m < y)
        upd(rc, m + 1, r, x, y, u, v);
}
void modify(int o, int l, int r, int x, int u, int v, int t) {
    if (l == r) {
        q[o].push_back((key) {
            u, v, t
        });
        return;
    }

    int m = (l + r) >> 1;

    if (x <= m)
        modify(lc, l, m, x, u, v, t);
    else
        modify(rc, m + 1, r, x, u, v, t);
}
void ask(int o, int l, int r) {
    int now = top;

    for (int i = 0; i < (int)e[o].size(); i++) {
        f1 = find(e[o][i].x);
        f2 = find(e[o][i].y);

        if (f1 == f2)
            continue;

        if (sz[f1] < sz[f2])
            swap(f1, f2);

        sz[f1] += sz[f2];
        f[f2] = f1;
        s[++top] = (node) {
            f1, f2
        };
    }

    if (l == r) {
        for (int i = 0; i < (int)q[o].size(); i++) {
            f1 = find(q[o][i].x);
            f2 = find(q[o][i].y);

            if (f1 == f2)
                ans[q[o][i].id] = 1;
            else
                ans[q[o][i].id] = -1;
        }

        del(now);
        return;
    }

    int m = (l + r) >> 1;

    ask(lc, l, m);
    ask(rc, m + 1, r);

    del(now);
}
int main() {
    //  freopen("data.in","r",stdin);

    scanf("%d %d", &n, &m);
    fo(i, 1, n) f[i] = i, sz[i] = 1;
    fo(i, 1, m) {
        scanf("%d %d %d", &op, &x, &y);

        if (x > y)
            swap(x, y);

        if (!op) {
            a[x][y] = i;
        }

        if (op == 1) {
            upd(1, 1, m, a[x][y], i - 1, x, y);
            a[x][y] = 0;
        }

        if (op == 2) {
            modify(1, 1, m, i, x, y, i);
        }
    }

    fo(i, 1, n) fo(j, i + 1, n) if (a[i][j])
        upd(1, 1, m, a[i][j], m, i, j);


    ask(1, 1, m);

    fo(i, 1, m) if (ans[i] == 1)
        puts("Y");
    else if (ans[i] == -1)
        puts("N");


    return 0;
}

P5787 二分图 /【模板】线段树分治
给一些加边和删边操作，询问每个时刻是不是二分图。

几乎跟上面没有区别，将每个点拆成两个点，i,i+n，给(x,y)连边的时候就合并(x,y+n),(x+n,y)即可。

#include<bits/stdc++.h>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
#define lc (o<<1)
#define rc ((o<<1)|1)
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef long long ll;
typedef double db; 
const int N=5e5+5;
int f[N],s[N],n,x,y,top,m,k,f1,f2,ans[N];
struct node{
	int x,y;
};
node st[N];
vector<node> e[N*4];
int find(int x){
	if (x==f[x]) return x;
	return find(f[x]);
}
void merge(int x,int y){
	f1=find(x); f2=find(y);
	if (s[f1]<s[f2]) swap(f1,f2);
	f[f2]=f1;
	s[f1]+=s[f2];
	st[++top]=(node){f1,f2};
}
void del(int now){
	while (top>now) {
		f1=st[top].x; f2=st[top].y; top--;
		s[f1]-=s[f2];
		f[f2]=f2;
	}
}
void upd(int o,int l,int r,int x,int y,int u,int v){
	if (x>y) return;
	if (x<=l && r<=y) {
		e[o].eb((node){u,v});
		return;
	}
	int m=(l+r)>>1;
	if (x<=m) upd(lc,l,m,x,y,u,v);
	if (m<y) upd(rc,m+1,r,x,y,u,v);
}
void ask(int o,int l,int r){
	int now=top;
	bool flag=1;
	for (int i=0;i<(int)e[o].size();i++) {
		f1=find(e[o][i].x); f2=find(e[o][i].y);
		
		if (f1==f2) {
			flag=0;
			break;
		}
		
		merge(e[o][i].x, e[o][i].y+n);
		merge(e[o][i].x+n, e[o][i].y);
	}
	
	if (flag) {
		if (l==r) {
		ans[l]=1;
		}
		else {
			int m=(l+r)>>1;
			ask(lc,l,m);
			ask(rc,m+1,r);
		}
	}
	
	del(now);
}
int main(){
//	freopen("data.in","r",stdin);
	
	int l,r;
	scanf("%d %d %d",&n,&m,&k);
	fo(i,1,n*2) {
		f[i]=i; s[i]=1;
	}
	fo(i,1,m) {
		scanf("%d %d %d %d",&x,&y,&l,&r);
		upd(1,1,k,l+1,r,x,y);
	}
	
	ask(1,1,k);
	fo(i,1,k) if (ans[i]) A; else B;
	
	return 0;
}

P2056 [ZJOI2007] 捉迷藏
给定一棵树，初始每个点的颜色都是黑色，需要支持两种操作
1 将某个点的颜色翻转
2 询问所有黑点中相距最远的两个点的距离。

首先关于树的直径有一个非常好的结论。
两棵树相连，新直径的两端点一定是原四个端点中的两个。

首先跟上面一样，将每个点打到对应的线段树时间节点上，然后我们用一个栈维护当前的直径，那么每次新加入一个节点，新的直径的端点肯定是这三个点中的两个，比较一下即可。

这里使用欧拉序+st表预处理来求lca。

#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
#define pi pair<ll,ll>
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
const ll mo1 = 1e9 + 7;
const ll mo2 = 1e9 + 9;
const ll P = 131;
const ll Q = 13331;
const ll mo = 998244353;
const ll inf = 1ll << 60;
const int N = 1e6 + 100;
vector<int> e[N], p[N], v[N * 4];
int n, x, y, deep[N], d[N * 2], seq[N * 2], f[N * 2][21], g[N * 2], cnt, first[N];
int bz[N], top;
pi st[N];
void dfs(int x, int y) {
	seq[++cnt] = x;
	d[cnt] = deep[x];
	f[cnt][0] = cnt;
	first[x] = cnt;
	for (int v : e[x]) {
		if (v == y) continue;
		deep[v] = deep[x] + 1;
		dfs(v, x);
		seq[++cnt] = x;
		d[cnt] = deep[x];
		f[cnt][0] = cnt;
	}
}
int l, r, k;
int ask(int x, int y) {
	l = first[x];
	r = first[y];

	if (l > r) swap(l, r);

	k = g[r - l + 1];
	if (d[f[l][k]] < d[f[r - (1 << k) + 1][k]])
		return seq[f[l][k]];
	return
		seq[f[r - (1 << k) + 1][k]];
}
void upd(int o, int l, int r, int tl, int tr, int x) {
	if (tl > tr) return;
	if (tl <= l && r <= tr) {
		v[o].eb(x);
		return;
	}
	int m = (l + r) >> 1;
	if (tl <= m) upd(lc, l, m, tl, tr, x);
	if (m < tr) upd(rc, m + 1, r, tl, tr, x);
}
int dis(int x, int y) {
	return deep[x] + deep[y] - 2 * deep[ask(x, y)];
}
void ask(int o, int l, int r) {
	int now = top;
	for (int x : v[o]) {
		if (!top) st[++top] = mk(x, x);
		else {
			if (dis(x, st[top].fi) > dis(x, st[top].se)) {
				if (dis(x, st[top].fi) > dis(st[top].fi, st[top].se)) {
					++top;
					st[top] = mk(x, st[top - 1].fi);
				}
			}
			else {
				if (dis(x, st[top].se) > dis(st[top].fi, st[top].se)) {
					++top;
					st[top] = mk(x, st[top - 1].se);
				}
			}
		}
	}

	if (l == r) {
		if (bz[l] != 0) {
			if (top) {
				printf("%d\n", dis(st[top].fi, st[top].se));
			}
			else puts("-1");
		}
	}
	else {
		int m = (l + r) >> 1;
		ask(lc, l, m);
		ask(rc, m + 1, r);
	}

	top = now;
}
int main() {
	//    freopen("data.in", "r", stdin);
	//	freopen("data.out", "w", stdout);

	scanf("%d", &n);
	fo(i, 1, n - 1) {
		scanf("%d %d", &x, &y);
		e[x].eb(y);
		e[y].eb(x);
	}

	dfs(1, 0);
	fo(j, 1, 20) fo(i, 1, cnt) {
		if (d[f[i][j - 1]] < d[f[min((ll)cnt, i + (1 << (j - 1)))][j - 1]]) f[i][j] = f[i][j - 1];
		else f[i][j] = f[min((ll)cnt, i + (1 << (j - 1)))][j - 1];
	}
	g[1] = 0;
	fo(i, 2, cnt) g[i] = g[i / 2] + 1;


	int q;
	scanf("%d", &q);
	char s[20];
	fo(i, 1, q) {
		scanf("%s", s + 1);
		if (s[1] == 'C') {
			scanf("%d", &x);
			p[x].eb(i);
		}
		else {
			bz[i] = 1;
		}
	}

	fo(i, 1, n) {
		if (!p[i].size()) {
			upd(1, 1, q, 1, q, i);

		}
		else {
			upd(1, 1, q, 1, p[i][0] - 1, i);
			for (int j = 0;j < (int)p[i].size();j++) {
				if (j & 1) {
					if (j == (int)p[i].size() - 1) upd(1, 1, q, p[i][j], q, i);
					else upd(1, 1, q, p[i][j], p[i][j + 1] - 1, i);
				}
			}
		}
	}

	ask(1, 1, q);

	return 0;

}

P4219 [BJOI2014] 大融合
小强要在 N 个孤立的星球上建立起一套通信系统。这套通信系统就是连接 N 个点的一个树。
这个树的边是一条一条添加上去的。
在某个时刻，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。

现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。

跟前面的维护连通性一样，假设我们现在要查询在t时刻(x,y)这条边的负载，那么假如我们在t时刻这里撤销了(x,y)这条边，那么答案就是两个并查集的大小相乘。
那么实际操作的话就是将这条边在的查询时刻的状态看作是不连通。

例如这条边是在a时刻连上的，我们在b时刻查询，那么我们就在[a,b-1],[b+1,Q]这两个区间插入这条边，这样既保证了在b时刻这条边不存在，也不会影响其它的时刻。

#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
#define pi pair<ll,ll>
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
const ll mo1=1e9+7;
const ll mo2=1e9+9;
const ll P=131;
const ll Q=13331;
const ll mo=998244353;
const int N=2e5+5;
const ll inf=1ll<<60;
struct node{
	ll x,y;
};
node c[N];
int n,q,f[N],tot;
ll sz[N];
char s[N];
vector<pi> e[N*4];
map<pi,int> h;
vector<int> v[N];
pi st[N];
int top;
void upd(int o,int l,int r,int tl,int tr,int u,int v){
	if (tl>tr) return;
	if (tl<=l && r<=tr) {
		e[o].eb(mk(u,v));
		return;
	}
	int m=(l+r)>>1;
	if (tl<=m) upd(lc,l,m,tl,tr,u,v);
	if (m<tr) upd(rc,m+1,r,tl,tr,u,v);
}
int x,y,f1,f2;
int find(int x){
	if (x==f[x]) return x;
	return find(f[x]);
}
void merge(int x,int y){
	f1=find(x); f2=find(y);
	if (f1==f2) return;
	if (sz[f1]<sz[f2]) swap(f1,f2);
	f[f2]=f1;
	sz[f1]+=sz[f2];
	st[++top]=mk(f1,f2);
}
void ask(int o,int l,int r){
	int now=top;
	for (auto it:e[o]) {
		merge(it.fi, it.se);
	}
	if (l==r) {
		if (c[l].x) {
			printf("%lld\n",sz[find(c[l].x)]*sz[find(c[l].y)]);	
		}
		
//		return;
	}
	else {
		int m=(l+r)>>1;
		ask(lc,l,m);
		ask(rc,m+1,r);
	}
	
	while (top>now) {
		x=st[top].fi; y=st[top].se;
		sz[x]-=sz[y];
		f[y]=y;
		top--;
	}
}
int main() {
//    freopen("data.in", "r", stdin);
//	freopen("data.out", "w", stdout);
	
	int x,y;
	scanf("%d %d",&n,&q);
	fo(i,1,n) f[i]=i,sz[i]=1;
	
	fo(i,1,q) {
		scanf("%s %d %d",s+1,&x,&y);
		if (x>y) swap(x,y);
		if (s[1]=='A') {
			h[mk(x,y)]=i;
		}
		else{
			c[i]=(node){x,y};
			v[h[mk(x,y)]].push_back(i);
		}
	}
	
	for (auto it:h) {
		int id=it.second,x=it.first.first,y=it.first.second;
		if (!v[id].size()) {
//			printf("%d %d %d\n",id,x,y);
			upd(1,1,q,id,q,x,y);
		}
		else {
			upd(1,1,q,id,v[id][0]-1,x,y);
//			printf("%d %d %d %d\n",id,v[id][0]-1,x,y);
			for (int i=0;i<(int)v[id].size();i++) {
				if (i!=(int)v[id].size()-1) {
					upd(1,1,q,v[id][i]+1,v[id][i+1]-1,x,y);
//					printf("%d %d %d %d\n",v[id][i]+1,v[id][i+1]-1,x,y);
				}
				else upd(1,1,q,v[id][i]+1,q,x,y);
			}
		}
	}
	ask(1,1,q);
	

    return 0;
    
}

标签：cnt,int,线段,分治,st,define,小结,top,fo
From： https://www.cnblogs.com/ganking/p/18336072

相关文章

  • 线段树题单记录
    线段树题单记录线段树的题都很板的，模板敲上去再改改就行有的题你用的线段树可能都可以删除一部分并正常使用TODO【模板】线段树1【模板】线段树2[JSOI2008]最大数[ABC357F]TwoSequenceQueries方差[COCI2010-2011#6]STEP贪婪大陆全村最......
  • 【数据结构】之线段树理解与基础模板
    什么是线段树线段树是一种通过类似二分来实现的一种二叉树结构，方便区间的修改与性质的查询，是一种非常节约时间的数据结构。为什么使用线段树比如我们给你NNN......
  • [动态开点の线段树]
    动态开点の线段树因为静态建点线段树消耗的空间太大了，需要开四倍空间，但是动态开点就可以大大降低所使用的空间，远小于四倍具体思想和线段树没有区别只是将\(k<<1\)换成了\(LS(k)\)，将\(k<<1|1\)换成了\(RS(k)\)，（具体开多少空间不是很能确定#include<cstdio>#include<iostream>......
  • 李超线段树
    李超线段树用途:在平面上插入一个线段或直线，求出与\(x=a\)相交的线段中纵坐标最大的线段编号。【模板】李超线段树/[HEOI2013]Segment将任务转化成插入一个定义域为\([l,r]\)的一次函数给定\(k\)，求定义域包含\(k\)的所有一次函数中，在\(x=k\)处取值最大的那个，如果有多个......
  • G73 线段树+线性基合并 P5607 [Ynoi2013] 无力回天 NOI2017
    视频链接：G73线段树+线性基合并P5607[Ynoi2013]无力回天NOI2017_哔哩哔哩_bilibili   P5607[Ynoi2013]无力回天NOI2017-洛谷|计算机科学教育新生态(luogu.com.cn)//线段树+线性基合并O(n*logn*logv*logv)#include<iostream>#include<cstring>#incl......
  • 浅谈简单的数据结构1（树状数组 、线段树）（c++）
    *_*课间休息后的知识点轰炸树状数组引入给定长为n的序列a，q次操作，每次查询一段区间的和，或修改一个数的权值。1≤n,q≤5×10^5,0≤a_i≤10^9。分析如果没有修改操作，这是一道非常简单的前缀和题。假如我们修改前缀和数组，查询就还是O(1)的，是否可行呢？当然不行。考虑......
  • C++题解(17) 狐猬编程: 640.线段覆盖
    题目描述在一条数轴上，有N条线段，第i条线段的左端点是s[i]，右端点是e[i]。如果线段有重叠（即使是端点重叠也算是重叠），则输出“impossible”，如果没有重叠则输出“possible”。输入格式输入文件名：640.in多组测试数据。第一行，一个整数G，表示有G组测试数据。1<=G<=10。每组......
  • 通配连续性题目解法小结
    把所有经常写到的连续力扣罗列在这，对这种看上去比较复杂的题目总结一个普适性强的解法LeetCode603连续空余座位连续可用座位查找电影院所有连续可用座位，返回值按seat_id升序排列思路：WITHcinema_valid_seatAS(SELECTseat_id,seat_id+1ASnext_num,--5的......
  • 【HW系列】事前准备(10)：事前阶段小结
    本章为该系列的第10篇，也是事前准备阶段的第10篇，通过本章做个小结，来结束事前准备阶段的介绍，从下一篇开始，将正式进入事中迎战阶段。有幸观摩过一场线下沙龙，在讨论过程中，我发现不同性质的企业，安全的建设方案完全不一样。当时在讨论邮件安全的议题，一位互联网公司的小伙直接打趣金融行......
  • 树分治、动态树分治学习笔记
    点分治点分治适合处理大规模的树上路径信息问题，选取重心，将当前的树拆分为几颗子树，然后递归子树求解问题，但是今天的重点不在这里边分治与点分治类似，选取一条边，均匀地将树分成两个部分，但是对于一个点有多个儿子时，时间复杂度就会非常大，于是我们可以将其转化，这里有两种方法\(1.\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99