[ 算法竞赛进阶指南 0x40 ] 杂谈

持续跟新

并查集

[NOI2015]程序自动分析
在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设x1,x2,x3…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2,x2=x3,x3=x4,x4≠x1，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

数据标识码在int范围内 <=1e9 显然离散化

先处理相等部分 因相等关系 他们可以传递
最后看不相等 在里面冲突

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
#define int long long
using namespace std;

const int maxn =2e6+5;
int n, m;

int pre[maxn];

void init(int n){
    for(int i=1;i<=n;i++) pre[i]=i;
}

int finds(int x){
    return pre[x]!=x?pre[x]=finds(pre[x]):x;
}

void unions(int x,int y){
    x=finds(x),y=finds(y);
    pre[x]=y;
}

signed main() {
    fastio;
    int t;
    cin>>t;
    while(t--){
        int cnt=0;
        cin>>n;	
        init(n*2);
        int x,y,d;
        map<int,int> id;
        vector<pair<int,int> >b;
        while(n--){
            cin>>x>>y>>d;
            if(!id[x]) id[x]=++cnt;
            if(!id[y]) id[y]=++cnt;
            if(d==1){
                unions(id[x],id[y]);
            }else{
                b.push_back(make_pair(id[x],id[y]));
            }
        }
        int f=1;
        for(int i=0;i<b.size();i++){
            if(finds(b[i].first)==finds(b[i].second)){
                cout<<"NO"<<endl;
                f=0;
                break;
            } 
        }
        if(f){
            cout<<"YES"<<endl;
        }
    }
    return 0;
}

NOI2002 银河系英雄传说

带权并查集（根搭积木很像）：
对于每个点，分别记录所属链的头结点、该点到头结点的距离以及它所在集合的大小。
每次合并将y接在x的尾部，改变y头的权值和所属链的头结点，同时改变x的尾节点。
注意：每次查找的时候也要维护每个节点的权值。
每次查询时计算两点的权值差。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=30000+10;

int pre[maxn],siz[maxn],d[maxn];

void init(int n){
	for(int i=1;i<maxn;i++){
		pre[i]=i,siz[i]=1,d[i]=0;
	}
}

int finds(int x){
	if(x==pre[x]) return x;
	int rt=finds(pre[x]);
	d[x]+=d[pre[x]];
	return pre[x]=rt;
}

void unions(int x,int y){
	x=finds(x),y=finds(y);
	pre[x]=y;
	d[x]+=siz[y];
	siz[y]+=siz[x];
}

int main() {
	int n;
	cin>>n;
	init(n);
	for(int i=1;i<=n;i++){
		string cmd;
		int x,y;
		cin>>cmd>>x>>y;
		if(cmd[0]=='M'){
			unions(x,y);
		}else{
			if(finds(x)!=finds(y)) cout<<-1<<endl;
			else cout<<abs(d[x]-d[y])-1<<endl;
		}
	}
	return 0;
}

树状数组练习

楼兰图腾 统计凹凸个数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define fir first
#define sec second
const int maxn=2*1e5+10;

int c[maxn];
int n;
int lowbit(int x) {
	return x&(-x);
}

int ask(int x) {
	int res=0;
	for(; x; x-=x&(-x)) res+=c[x];
	return res;
}

void add(int x,int y) {
	for(; x<=n; x+=x&(-x)) {
		c[x]+=y;
	}
}

int a[maxn];
int L[maxn],R[maxn];
int l[maxn],r[maxn];

signed main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	add(a[1],1);
	for(int i=2;i<n;i++){
		add(a[i],1);
		l[i]=ask(n)-ask(a[i]);
		L[i]=ask(a[i]-1);
	}
	memset(c,0,sizeof c);
	add(a[n],1);
	for(int i=n-1;i>1;i--){
		add(a[i],1);
		R[i]=ask(a[i]-1);
		r[i]=ask(n)-ask(a[i]);
	}
	ll rs=0,res=0;
	for(int i=2;i<n;i++){
		rs+=1ll*l[i]*r[i];
		res+=1ll*L[i]*R[i]; 
	}
	cout<<rs<<" "<<res<<endl;
	return 0;
}

线段树
Can you answer on these queries III

单独杂谈外链 ： https://blog.csdn.net/qq_40831340/article/details/90726050
关于 这个线段树的相似的题

#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(0)
const int maxn = 5e5+10;
int n, m;

int sum[maxn << 2], lmax[maxn << 2], rmax[maxn << 2], lrmax[maxn << 2];

void push_up(int rt) {
	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	lmax[rt] = max(lmax[rt << 1], sum[rt << 1] + lmax[rt << 1 | 1]);
	rmax[rt] = max(rmax[rt << 1 | 1], sum[rt << 1 | 1] + rmax[rt << 1]);
	lrmax[rt] = max( max(lrmax[rt << 1], lrmax[rt << 1 | 1]), rmax[rt << 1] + lmax[rt << 1 | 1]);
}

void update(int L, int l, int r, int rt, int c) {
	if(l == r) {
		lrmax[rt] = lmax[rt] = rmax[rt] = sum[rt] = c;
		return ;
	}
	int mid = l + r >> 1;
	if(L <= mid) update(L, l, mid, rt << 1, c);
	else update(L, mid + 1, r, rt << 1 | 1, c);
	push_up(rt);
}

//int query(int L, int R, int l, int r, int rt) {
// if(L <= l && r <= R) {
// return lrmax[rt];
// }
// int mid = l + r >> 1;
// int res = -0x3f3f3f3f;
// if(L <= mid) res = max(res, query(L, R, l, mid, rt << 1));
// if(R > mid) res = max(res, query(L, R, mid + 1, r, rt << 1 | 1));
// return res;
//}

struct node {
	int sum;
	int lmax, rmax, lrmax;
};

node query(int L, int R, int l, int r, int rt) {
	if(L <= l && r <= R) {
		return node {sum[rt], lmax[rt], rmax[rt], lrmax[rt]};
	}
	//if(l == r) return node {sum[rt], lmax[rt], rmax[rt], lrmax[rt]};
	int mid = l + r >> 1;
	if (R <= mid) return query(L, R, l, mid, rt << 1);
	else if (L > mid) return query(L, R, mid + 1, r, rt << 1 | 1);
	else {
		node res;
		node re1 = query (L, R, l, mid, rt << 1);
		node re2 = query (L, R, mid + 1, r, rt << 1 | 1);
		res.sum = re1.sum + re2.sum;
		res.lmax = max(re1.lmax, re1.sum + re2.lmax);
		res.rmax = max(re2.rmax, re2.sum + re1.rmax);
		res.lrmax = max( max(re1.lrmax, re2.lrmax), re1.rmax + re2.lmax);
		return res;
	}
}

int main() {
	fastio;
	cin >> n >> m;
	int k;
	for(int i = 1; i <= n; i ++) {
		cin >> k;
		update(i, 1, n, 1, k);
	}
	while(m--) {
		int cmd, x ,y;
		cin >> cmd >> x >> y;
		if(cmd == 1) {
			if(x > y) swap (x, y);
			cout << query(x, y, 1, n, 1).lrmax << endl;
		} else {
			update(x, 1, n, 1, y);
		}
	}
	return 0;
}

维护差分 变成区间修改单点查
这样不能直接修改某区间变成b 复杂度有点搞人

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define fir first
#define sec second
const int maxn=2*1e5+10;

int c[maxn];
int n;
int lowbit(int x) {
	return x&(-x);
}

int ask(int x) {
	int res=0;
	for(; x; x-=x&(-x)) res+=c[x];
	return res;
}

void add(int x,int y) {
	for(; x<=n; x+=x&(-x)) {
		c[x]+=y;
	}
}

int a[maxn];

signed main() {
	int m;
	cin>>n>>m;
	string cmd;
	int l,r,d;
	
	for(int i=1;i<=n;i++) cin>>a[i];
	
	for(int i=1;i<=m;i++){
		cin>>cmd;
		if(cmd[0]=='Q'){
			cin>>l;
			cout<<ask(l)+a[l]<<endl;
		}else{
			cin>>l>>r>>d;
			add(l,d);
			add(r+1,-d);
		}
	}
	return 0;
}

poj lost cows
这题说什么 二分树状数组什么的 完全没有看懂。。。
书堆大法好啊
反正都是倒着找 k大 而且这个k大不能与后面重复 倒着删就好了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define fir first
#define sec second
const int maxn=1e5+10;

int siz[maxn];
int s[maxn][3];
int w[maxn],pos[maxn];
int tot;

void up(int i) {
	siz[i]=siz[s[i][0]]+siz[s[i][1]]+1;
}

void spin(int &i,int p) {
	int t=s[i][p];
	s[i][p]=s[t][!p],s[t][!p]=i,up(i),up(t),i=t;
}

void ins(int x,int &i) {
	if(!i) {
		i=++tot,siz[i]=1,w[i]=x,pos[i]=rand();
		return;
	}
	siz[i]++;
	if(x<=w[i]) {
		ins(x,s[i][0]);
		if(pos[s[i][0]]<pos[i])spin(i,0);
	} else {
		ins(x,s[i][1]);
		if(pos[s[i][1]]<pos[i])spin(i,1);
	}
}

void del(int x,int &i) {
	if(w[i]==x) {
		if(s[i][0]*s[i][1]==0) {
			i=s[i][0]+s[i][1];
			return;
		}
		if(pos[s[i][0]]>pos[s[i][1]]) {
			spin(i,1);
			del(x,s[i][0]);
		} else {
			spin(i,0);
			del(x,s[i][1]);
		}
	} else if(w[i]>x)del(x,s[i][0]);
	else del(x,s[i][1]);
	up(i);
}

int find(int x,int i) {
	if(!i)return 1;
	if(w[i]>=x)return find(x,s[i][0]);
	return find(x,s[i][1])+siz[s[i][0]]+1;
}

int ask(int x,int i) {
	if(siz[s[i][0]]==x-1)return w[i];
	if(siz[s[i][0]]>=x)return ask(x,s[i][0]);
	return ask(x-siz[s[i][0]]-1,s[i][1]);
}

int ans[maxn];
int a[maxn];
signed main() {
	int n;
	cin>>n;
	int root=0;

	ins(1,root);
	for(int i=2; i<=n; i++) cin>>a[i],ins(i,root),a[i]++;


	for(int i=n; i>1; i--) {
		ans[i]=ask(a[i],root);
		del(ans[i],root);
	}

	cout<<ask(1,root)<<endl;
	for(int i=2; i<=n; i++) {
		cout<<ans[i]<<endl;
	}
	return 0;
}

这里在补个 权值线段树水果区的代码orz

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

const int maxn = 1e5 + 5;

int n, m;

int b[maxn << 2];

void push_up(int rt) {
	b[rt] = b[rt << 1] + b[rt << 1 | 1] ;
}

void update(int L, int l, int r, int rt, int c) {
	if(l == r) {
		b[rt] += c;
		return ;
	}
	int mid = l + r >> 1;
	if(L <= mid) update(L, l, mid, rt << 1, c);
	else update(L, mid + 1, r, rt << 1 | 1, c);
	push_up(rt);
}

void query(int L, int l, int r, int rt) {
	if(l == r) {
		cout << l << " " << b[rt] << endl; 
		return ;
	}
	int mid = l + r >> 1;
	if(L <= mid) query(L, l, mid, rt << 1);
	else query(L, mid + 1, r, rt << 1 | 1);
}

int find_k(int l, int r, int rt, int k) {
	if(l == r) {
		return l;
	}
	int mid = l + r >> 1;
	if(k <= b[rt << 1]) return find_k(l, mid, rt << 1, k);
	else return find_k(mid + 1, r, rt << 1 | 1, k - b[rt << 1]);
}

int a[maxn];
int ans[maxn];
int main() {
	fastio;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		update(i, 1, n, 1, 1);
	}
	
	for(int i = 2; i <= n; i ++) {
		cin >> a[i];
	}
	a[1] = 0;
	int k = n;
	for(int i = n; i >= 1; i --) {
		ans[i] = find_k(1, n, 1, a[i] + 1);
	// cout << find_k(1, n, 1, a[i] + 1) << endl;
	// cout << "\\\\" << ans[i] << endl;
		update(ans[i], 1, n, 1, -1);
	// query(ans[i], 1, n, 1);
	}
	
	for(int i = 1; i <= n; i ++)
		cout << ans[i] << endl; 
	
	return 0;
}
全部评论

相关推荐

11-28 15:49
北京理工大学 机械结构工程师
校招两方/三方违约模板
被黑心运营压榨了，是谁我不说，上班摸鱼，还要被压榨，万恶的资本家给大家提供几个我去年用到过的违约模板，三方模板只有一个，因为学校只给一次毁约三方的机会违约通用模板1：您好!我叫，是来自于XX大学XX专业的学生，已与贵公司签署了就业三方协议，目前由于个人原因而与贵公司违约，感到非常的惭愧与歉疚，望各位领导谅解!作为一名还未踏出校园的大学生，我便失信于贵公司，是我的巨大损失，也是我终身的遗憾，做出这个决定，我也非常的不舍，同时也望贵单位领导谅解。我深知我的违约行为将会给贵单位的招聘工作带来极大的不便，在此对我没有处理好个人事情而给贵公司带来的不便表示深深的歉意!另外此次违约实属个人行为在此再次向贵...
牛客刘北：黑心运营来了
点赞 评论 收藏
分享
11-24 14:20
北京大学 Java
秋招offer比较，头部大厂or明星初创
决赛圈了，希望各位前辈能帮忙斟酌一下，n∈[32k，35k]，m∈[10w，13w]&nbsp;字节：n×15&nbsp;+&nbsp;m期权&nbsp;+&nbsp;15w签字费&nbsp;初创：(n+7k)×16&nbsp;+&nbsp;2m期权&nbsp;+&nbsp;15w签字费&nbsp;1优点，字节算挺有诚意，本来确定要去了，但下面的初创给了个大的。毫无疑问title对未来跳槽帮助大&nbsp;1缺点，这个组的人才密度比较大，有一半多是top2的，晋升感觉无望，但跟着大佬多学点东西也还行。&nbsp;2优点:给的钱多，明星初创有一定前景?(几率很小)&nbsp;2缺点:加班比字节还严重。以及这类型公司跳槽，&nbsp;title的...
CoderEcho：虽然我没去大厂，但是待过俩家初创，我的感觉是厉害的初创很舍得给钱，也很看你的产出，产出不行直接把你开了。当然大厂也可能有这个问题。建议还是去大厂，如果被裁员了最起码还有大厂的title，这年头不确定的事儿太多了。
字节求职进展汇总 软开人，秋招你打算投哪些公司呢
点赞 评论 收藏
分享
11-05 07:29
贵州大学 Java
点赞 评论 收藏
分享
10-11 09:34
郑州大学 算法工程师
211硕，0offer，求指导
猪扒已出闸：方向不够聚焦，看不出来是想找什么方向的工作
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
233780次浏览 2032人参与
# 在职场上，你最讨厌什么样的同事 #
5796次浏览 81人参与
# 北方华创开奖 #
66111次浏览 549人参与
# 25届秋招总结 #
398291次浏览 3987人参与
# 哪些公司校招卡第一学历 #
32945次浏览 106人参与
# 地方国企笔面经互助 #
6593次浏览 16人参与
# 阿里云管培生offer #
59421次浏览 1749人参与
# ai智能作图 #
21994次浏览 264人参与
# 硬件兄弟们 甩出你的华为奖状 #
78006次浏览 625人参与
# 实习，投递多份简历没人回复怎么办 #
2436431次浏览 34705人参与
# 工作中，你有没有遇到非常爱骂人的领导？ #
4751次浏览 47人参与
# 实习与准备秋招该如何平衡 #
723009次浏览 8551人参与
# 我的实习求职记录 #
6123236次浏览 83960人参与
# 如果再来一次，你还会选择这个工作吗？ #
111085次浏览 1116人参与
# 25届机械人为了秋招做了哪些准备？ #
25231次浏览 357人参与
# 签了三方后想毁约怎么办 #
18578次浏览 111人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
10024次浏览 216人参与
# 机械求职避坑tips #
22420次浏览 242人参与
# 游戏求职进展汇总 #
52842次浏览 344人参与
# 夸夸我的求职搭子 #
132061次浏览 1360人参与
# 腾讯求职进展汇总 #
207690次浏览 1694人参与
# 实习想申请秋招offer，能不能argue薪资 #
35809次浏览 308人参与
牛客网
牛客企业服务