持续跟新
并查集
[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;
}
京公网安备 11010502036488号