码蹄集部分题目（2024OJ赛7.31-8.4；树状数组+并查集）
1🐋🐋奇偶性（星耀；树状数组）
时间限制：1秒
占用内存：128M
🐟题目思路
【MT3059 奇偶性】MT3059 奇偶性_哔哩哔哩_bilibili
🐟代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int a[N],tmp[N],c[N],n,m,l,r;
long long ans;
//树状数组模板
int lb(int x) { return x & -x; }
void update(int i,int x)
{for(;i<=n;i+=lb(i)) c[i]+=x;
}
int sum(int i)
{int ans=0;for(;i>0;i-=lb(i)) ans+=c[i];return ans;
}
int sum(int l,int r) {return sum(r)-sum(l-1);}
int main( )
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];//离散化for(int i=1;i<=n;i++) tmp[i]=a[i];sort(tmp+1,tmp+1+n);int len=unique(tmp+1,tmp+1+n)-(tmp+1);for(int i=1;i<=n;i++) a[i]=lower_bound(tmp+1,tmp+len+1,a[i])-tmp;//求逆序对个数for(int i=1;i<=n;i++){update(a[i],1);ans+=sum(a[i]+1,n);}//进入到本题计算ans%=2;cin>>m;while(m--){cin>>l>>r;if(((r-l+1)/2)%2) ans^=1;if(ans) cout<<"1"<<endl;else cout<<"0"<<endl;}return 0;
}2🐋🐋左移后的逆序对（钻石；树状数组）
时间限制：1秒
占用内存：128M
🐟题目思路
【MT3060 左移后的逆序对】MT3060 左移后的逆序对_哔哩哔哩_bilibili
🐟代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7;
int a[N],c[N],n;
long long ans;
int lb(int x) { return x & -x; }
void update(int i,int x)
{for(;i<=n;i+=lb(i)) c[i]+=x;
}
int sum(int i)
{int ans=0;for(;i>0;i-=lb(i)) ans+=c[i];return ans;
}
int sum(int l,int r) { return sum(r)-sum(l-1); }
int main( )
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];a[i]++;} for(int i=1;i<=n;i++){update(a[i],1);ans+=sum(a[i]+1,n);}cout<<ans<<endl;for(int i=1;i<=n-1;i++){ans+=n-a[i]*2+1;cout<<ans<<endl;}return 0;
}3🐋🐋区间异或和（钻石；树状数组）
时间限制：1秒
占用内存：128M
🐟题目思路
【MT3061 区间异或和】MT3061 区间异或和_哔哩哔哩_bilibili
🐟代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7;
int n,m,flag,x,y,a[N],c[N];
int lb(int x) { return x & -x; }
void update(int i,int x)
{for(;i<=n;i+=lb(i)) c[i]^=x;
}
int sum(int i)
{int ans=0;for(;i>0;i-=lb(i)) ans^=c[i];return ans;
}
int sum(int l,int r) { return sum(r)^sum(l-1); }
int main( )
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];update(i,a[i]);}while(m--){cin>>flag>>x>>y;if(flag==1){a[x]^=y;update(x,y);}else cout<<sum(x,y)<<endl;}return 0;
}4🐋🐋农场（王者；并查集）
时间限制：3秒
占用内存：128M
🐟题目思路
【MT3057 农场】MT3057 农场_哔哩哔哩_bilibili
🐟代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
struct node
{double x,y;int id;
}a[N],b[N];
struct edge
{int u,v;double w;
}e[2*N];
int n,m,fa[N];
double k;
bool cmp1(node x,node y) { return x.x<y.x; }
bool cmp2(node x,node y) { return x.y<y.y; }
bool cmp3(edge x,edge y) { return x.w<y.w; }
int find(int x)
{if(fa[x]==x) return x;return fa[x]=find(fa[x]);
}
void merge(int i,int j)
{int x=find(i),y=find(j);if(x!=y) fa[x]=y;
}
bool sol(int l,int r)
{if(l>=r) return 1;int mid=(l+r)/2,cnt=0;if(!sol(l,mid)||!sol(mid+1,r)) return false;while(a[l].x+k<a[mid].x) l++;while(a[r].x-k>a[mid].x) r--;for(int i=l;i<=r;i++) b[++cnt]=a[i];sort(b+1,b+1+cnt,cmp2);for(int i=1;i<=cnt;i++){for(int j=i+1;j<=cnt;j++){if(b[j].y-b[i].y>k) break;if(fabs(b[j].x-b[i].x)<=k&&find(b[i].id)!=find(b[j].id)) return false;}}return true;
}
bool check(int x)
{for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=m;i++){if(e[i].w>e[x].w) break;merge(e[i].u,e[i].v);}return sol(1,n);
}
int main( )
{cin>>n>>m>>k;for(int i=1;i<=n;i++) {cin>>a[i].x>>a[i].y;a[i].id=i;}for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;sort(a+1,a+1+n,cmp1);sort(e+1,e+1+m,cmp3);int l=0,r=m,mid,ans=0;while(l<=r){mid=(l+r)/2;if(check(mid)) {r=mid-1;ans=mid;}else l=mid+1;}printf("%.3lf",e[ans].w);return 0;
}5🐋🐋方块染色（星耀；并查集）
时间限制：1秒
占用内存：250M
🐟题目思路
【MT3053 方块染色】MT3053 方块染色_哔哩哔哩_bilibili
🐟代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int n,m,fa[2*N];
set<int> s;
int find(int x)
{if(x==fa[x]) return x;return fa[x]=find(fa[x]);
}
void merge(int i,int j)
{int x=find(i),y=find(j);if(x!=y) fa[x]=y;
}
int main( )
{cin>>n>>m;for(int i=1;i<=2*n;i++) fa[i]=i;for(int i=1;i<=m;i++){char opt;int x,y;cin>>opt>>x>>y;if(opt=='S'){merge(x,y);merge(x+n,y+n);}else{merge(x+n,y);merge(x,y+n);}}for(int i=1;i<=n;i++){if(find(i)==find(i+n)){cout<<0;return 0;}}for(int i=1;i<=2*n;i++) s.insert(find(i));cout<<1;for(int i=1;i<=(s.size()/2);i++) cout<<0;return 0;
}6🐋🐋删除序列（星耀；并查集）
时间限制：1秒
占用内存：256M
🐟题目思路
【MT3058 删除序列】MT3058 删除序列_哔哩哔哩_bilibili
🐟代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+7;
int fa[N],a[N],b[N],flag[N],n,ans,maxn;
int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int i,int j)
{int x=find(i),y=find(j);if(x!=y) {fa[x]=y;a[y]+=a[x];}
}
signed main( )
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];fa[i]=i;}for(int i=1;i<=n;i++) cin>>b[i];for(int i=n;i>=2;i--){flag[b[i]]=1;if(flag[b[i]-1]&&!flag[b[i]+1]) merge(b[i]-1,b[i]);if(!flag[b[i]-1]&&flag[b[i]+1]) merge(b[i]+1,b[i]);if(flag[b[i]-1]&&flag[b[i]+1]) {merge(b[i]-1,b[i]);merge(b[i]+1,b[i]);}maxn=max(maxn,a[find(b[i])]);ans+=maxn;}cout<<ans;return 0;
}⭐这周有点不太舒服，就没有写题解，需要的宝子看下链接里的视频讲解~
⭐创作不易，点个赞吧~
⭐点赞收藏不迷路~