复健计划(4)并查集
因为前段时间刚刚复习了几道并查集题目，还算比较熟悉，就先放在这里：
板子题(程序自动分析，NOI)
带边权的并查集1(POJ 1733)
带边权的并查集2(银河英雄传说，NOI2002)
带扩展域的并查集(POJ 1733)
复健计划(5)树状数组
树状数组是一个好用，好写但是代码比较抽象的数据结构，总之记住 c[x]c[x]c[x] 表示 aaa 数组[x−lowbit(x)+1,x][x-lowbit(x)+1,x][x−lowbit(x)+1,x]的和，其中 lowbit(x)lowbit(x)lowbit(x) 表示二进制表示下从右往左第一个1和末位的0所构成的数值.
1、最基础的题 acwing 242
题目大意：区间修改，单点查询
思路：用树状数组维护原序列的差分序列,注意修改时要保证r+1~n部分的数字不变.
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=100010;int a[N],n,m;int b[N];int c[N];int lowbit(int x){return x&-x;}void add(int x,int y){for(;x<=n;x+=lowbit(x)) c[x]+=y; }int sum(int x){int ans=0;for(;x;x-=lowbit(x)) ans+=c[x];return ans;}int main(){cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]-a[i-1];for(int i=1;i<=n;i++) add(i,b[i]);for(int i=1;i<=m;i++){int l,r,d,x;char op[2];scanf("%s",op);if(op[0]=='Q'){scanf("%d",&x);printf("%d\n",sum(x));}else{scanf("%d%d%d",&l,&r,&d);add(l,d);add(r+1,-d);}}return 0;}
2、需要提取模型的题目 acwing 241
题目大意：给一个1~n的排列，求三元组(a,b,c)(a,b,c)(a,b,c)满足条件a<b,b>ca<b,b>ca<b,b>c的个数；
思路：针对该排列中任意一个位置 iii ，其高度为 yiy_iyi ，则要求找到 1i−11~i-11i−1 位置中比 yiy_iyi 大的数的个数和 i+1ni+1~ni+1n 位置中比 yiy_iyi 大的个数，相乘即可；具体实现时，求前者时循环从1到n，这样不会算入i后满足条件的高度数量，求后者时同理；并且此题以高度为原数组，这就是转换，也是难点.
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=200010;typedef long long ll;int a[N],n;int c[N];ll gr[N],le[N];ll ans1,ans2;int lowbit(int x){return x&-x;}void add(int x,int y){for(;x<=n;x+=lowbit(x)) c[x]+=y;}ll sum(int x){ll ans=0;for(;x;x-=lowbit(x)) ans+=(ll)c[x];return ans;}int main(){cin>>n;for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++){add(a[i],1);gr[i]=sum(n)-sum(a[i]);le[i]=sum(a[i]-1);}memset(c,0,sizeof(c));for(int i=n;i;i--){add(a[i],1);ans1+=gr[i]*(sum(n)-sum(a[i]));ans2+=le[i]*sum(a[i]-1);}cout<<ans1<<" "<<ans2<<endl;return 0;}
3、更加有技巧的两道题目：
区间修改区间求和
二分+树状数组
如果觉得《复健4+5》对你有帮助，请点赞、收藏，并留下你的观点哦！
