数据结构攻略"/>
数据结构攻略
KMP字符串
题目
给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出模式串 P 在字符串 S 中所有出现的位置的起始下标。
思路
先遍历字符串 P，找处 P 中相同对应的字符串，下标 i 从字符串 P 中的第二个字符开始遍历，下标 j 一开始指向 0，不表示任何字符，如果 i 满足 j+1，则字符串 P 中第 i 的字符对应于第 j+1 的字符；如果不满足，则前面没有对应于 i 的字符。连续相同的情况下，j ++，所以后面有一字串满足字符串前面连续的一段字串，则最后一个字符串下标 i 所对应的 j 就是字串的长度。
数组ne表示字符串中每个字符所能对应的前缀最长的长度。
每个循环中 j 表示 i 前面有 j 个字符相同。
-
若不匹配，让j回跳，直到匹配或j=0。
-
若匹配，让j+1，ne[i]=j；
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6+5;
int n,m,ne[N];
char p[N],s[M];
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>p+1>>m>>s+1;for(int j=0,i=2;i<=n;i++){while(j&&p[i]!=p[j+1])j=ne[j];if(p[i]==p[j+1])j++;ne[i]=j;}for(int j=0,i=1;i<=m;i++){while(j&&s[i]!=p[j+1])j=ne[j];if(s[i]==p[j+1])j++; //j表示i前面有j个字符相同if(j==n){cout<<i-j<<' ';j=ne[j];}}return 0;
}
契合匹配
题目
小蓝有很多齿轮，每个齿轮的凸起和凹陷分别用一个字符表示，一个字符串表示一个齿轮。 如果两个齿轮的对应位分别是同一个字母的大小写，我们称这两个齿轮是契合的。 例如：AbCDeFgh 和 aBcdEfGH 就是契合的，但是 abc 和 aBC 不是契合的。 这天，小蓝的弟弟小桥从抽屉里拿来了两个齿轮，小蓝想知道，这俩个齿轮是不是契合的。 特别需要注意的是，齿轮是环形的，所以是可以旋转的（顺时针和逆时针均可），如果是契 合的，小蓝还想让你告诉他，最少将第一个齿轮旋转多少位，两个齿轮可以完全契合在一 起。 例如： AbbCd 与 BcDaB，在将第一个齿轮逆时针旋转两位后，变成 bCdAb ，两个齿轮就完全 契合在一起了。
思路
先将第一个字符串全部转换，存进另一个数组中，存两倍大小，判断第二个字符串是否在这个字符串里面，用到了KMP。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;string a;
char p[N],s[N<<1];
int ne[N];int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n;cin>>n>>a>>p+1;for(int i=0;i<n;i++){if(a[i]>='A'&&a[i]<='Z')a[i]=tolower(a[i]);else a[i]=toupper(a[i]);s[i+1]=s[n+i+1]=a[i];}for(int j=0,i=2;i<=n;i++){while(j&&p[j+1]!=p[i])j=ne[j];if(p[j+1]==p[i])j++;ne[i]=j;}for(int j=0,i=1;i<=2*n;i++){while(j&&s[i]!=p[j+1])j=ne[j];if(s[i]==p[j+1])j++;if(j==n){cout<<"Yes\n";cout<<min(i-j,n-(i-j));return 0;}}cout<<"No";return 0;
}
并查集
食物链
题目
动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。
现有 N 个动物，以 1 ~ N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
- 第一种说法是 1 X Y，表示 X 和 Y 是同类。
- 第二种说法是 2 X Y，表示 X 吃 Y。
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中 X 或 Y 比 N 大，就是假话；
- 当前的话表示 X 吃 X，就是假话。
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
思路
数组ra存储子节点与根节点之间的关系：0表示同类，1表示狩猎，2表示被猎
因为d只能是1或2分表表示同类和狩猎所以要d-1
代码
#include<bits/stdc++.h>
using namespace std;
const int mxn=5e4+5;
int fa[mxn],ra[mxn];
int find(int x){if(x==fa[x])return x;else{int t=fa[x];fa[x]=find(fa[x]);ra[x]=(ra[x]+ra[t])%3;}return fa[x];
}
int n,k,d,x,y,ans;
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++)fa[i]=i;while(k--){cin>>d>>x>>y;if(x>n||y>n||d==2&&x==y)ans++;else{int u=find(x),v=find(y);if(u==v){if((ra[x]-ra[y]+3)%3!=d-1)ans++;}else{fa[u]=v;ra[u]=(ra[y]+d-1-ra[x])%3;}}}cout<<ans;return 0;
}
虫子的生活
题目
霍珀教授正在研究一种稀有虫子的性行为。他假设它们具有两种不同的性别，并且它们只与异性的虫子互动。在他的实验中，单个虫子及其相互作用很容易识别，因为它们的背上印有数字。
给定一个错误交互列表，确定实验是否支持他假设的两种性别没有同性恋错误，或者它是否包含一些伪造它的错误交互。
思路
代码
#include<iostream>
using namespace std;
const int mxn=2005;
int fa[mxn],ra[mxn],tot;
int find(int x){if(x==fa[x])return x;else{int t=fa[x];fa[x]=find(fa[x]);ra[x]=(ra[x]+ra[t])%2;}return fa[x];
}
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t,n,m;cin>>t;while(t--){cout<<"Scenario #"<<++tot<<":\n";cin>>n>>m;int flag=true;for(int i=1;i<=n;i++)fa[i]=i,ra[i]=0;while(m--){int u,v;cin>>u>>v;int x=find(u),y=find(v);if(x!=y){fa[x]=y;ra[x]=(1+ra[v]-ra[u])%2;}else{if(ra[u]==ra[v]){flag=false;}}}if(flag)cout<<"No suspicious bugs found!\n\n";else cout<<"Suspicious bugs found!\n\n";}return 0;
}
树状数组
可以解决大部分基于区间上的更新以及求和问题。
定义一个区间[ l , r ]，其中update左端点，则比 l 大的区间都加 k。求值的时候sum右端点得到的是所有在区间内的和在区间外的，sum左端点得到的是所有在区间外的，减一减即是区间内的值。
树状数组是往小的取值。
一个简单的整数问题
题目
给定长度为 N 的数列 A，然后输入 M 行操作指令。
第一类指令形如 C l r d，表示把数列中第 l∼r 个数都加 d。
第二类指令形如 Q x，表示询问数列中第 x 个数的值。
对于每个询问，输出一个整数表示答案。
思路
给 l 端点update(d)，r 端点update(-d)，查询[l,r]区间内的端点的时候它会加上d，查询区间后的端点的时候它不受影响。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,a[N],c[N];
int lowbit(int x){return x&(-x);
}
void update(int x,int k){while(x<=n){c[x]+=k;x+=lowbit(x);}
}
int sum(int x){int r=a[x];while(x){r+=c[x];x-=lowbit(x);}return r;
}
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int u,v,x;cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];}while(q--){char c;cin>>c;if(c=='Q'){cin>>u;cout<<sum(u)<<'\n';}else{cin>>u>>v>>x;update(u,x);update(v+1,-x);}}return 0;
}
一个简单的整数问题2
题目
给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
- C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
- Q l r，表示询问数列中第 l∼r 个数的和。
对于每个询问，输出一个整数表示答案。
思路
数组b存储 i * d[i]，j，数组c存储 d[i]
设a[i]表示第i个数的值，d[i]为差分数组d等于a[i]-a[i-1]
a[1]=d[1]
a[2]=d[1]+d[2]
······
a[x]=d[1]+d[2]+…+a[x]
则a[1]+a[2]+…+a[x]=x ∗ * ∗d[1]+(x-1) ∗ * ∗d[2]+…+d[x]
=(x+1) ∗ * ∗(d[1]+d[2]+…+d[x])-(1d[1]+2d[2]+…+xd[x])
=(x+1)Σd[i]-Σid[i] (i从1到x)
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int b[N],c[N];
int lowbit(int x){return x&(-x);
}
void update(int x,int k){int p=k*x;while(x<N){c[x]+=k;b[x]+=p;x+=lowbit(x);}
}
int sum(int x){int r=0,p=x+1;while(x){r+=p*c[x]-b[x];x-=lowbit(x);}return r;
}
signed main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;int now,pre=0;for(int i=1;i<=n;i++){cin>>now;update(i,now-pre);pre=now;}while(m--){char c;int u,v,x;cin>>c;if(c=='Q'){cin>>u>>v;cout<<sum(v)-sum(u-1)<<'\n';}else{cin>>u>>v>>x;update(u,x);update(v+1,-x);}}return 0;
}
楼兰图腾
题目
西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 n 个点，经测量发现这 n 个点的水平位置和竖直位置是两两不同的。
西部 314 认为这幅壁画所包含的信息与这 n 个点的相对位置有关，因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn)，其中 y1∼yn 是 1 到 n 的一个排列。
西部 314 打算研究这幅壁画中包含着多少个图腾。
如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n1 且 yi>yj,yj<yk，则称这三个点构成 V 图腾;
如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n1 且 yi<yj,yj>yk，则称这三个点构成 ∧ 图腾;
西部 314 想知道，这 n 个点中两个部落图腾的数目。
因此，你需要编写一个程序来求出 V 的个数和 ∧ 的个数。
思路
先求每个点前后比它小的数量和比它大的数量，前面比它小的数量 * 后面比它小的数量就是 ^ 的个数，反之前面比它大的数量 * 后面比它大的数量就是 V 的个数，这样即可求得答案。
用树状数组的方法，求前面比它小的，先将前面的数存进去；求后面比它小的，先将后面的数存进去。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int l_up[N],l_down[N];
int r_up[N],r_down[N];
int a[N],c[N],n;
int lowbit(int x){return x&(-x);
}
void update(int x){while(x<=n){c[x]++;x+=lowbit(x);}
}
int sum(int x){int r=0;while(x){r+=c[x];x-=lowbit(x);}return r;
}
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];l_down[i]=sum(a[i]); //前面比它小的数l_up[i]=i-1-l_down[i];update(a[i]);}memset(c,0,sizeof c);for(int i=n;i>0;i--){r_down[i]=sum(a[i]);r_up[i]=n-i-r_down[i];update(a[i]);}long long ans1=0,ans2=0;for(int i=1;i<=n;i++){ans1+=l_down[i]*r_down[i];ans2+=l_up[i]*r_up[i];}cout<<ans2<<' '<<ans1;return 0;
}
谜一样的牛(二分)
题目
有 n 头奶牛，已知它们的身高为 1∼n 且各不相同，但不知道每头奶牛的具体身高。
现在这 n 头奶牛站成一列，已知第 i 头牛前面有 Ai 头牛比它低，求每头奶牛的身高。
思路
树状数组 + 二分
因为身高为 1~n 所以一开始每个点都 +1，从后往前，通过二分得出这个点的身高是多少，然后这个点已经被选了，所以这个身高 -1。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],c[N],res[N];
int lowbit(int x){return x&(-x);
}
void update(int x,int k){while(x<=n){c[x]+=k;x+=lowbit(x);}
}
int sum(int x){int r=0;while(x){r+=c[x];x-=lowbit(x);}return r;
}
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=2;i<=n;i++){cin>>a[i];update(i,1);}for(int i=n;i>0;i--){int l=1,r=n,ans;while(l<=r){int mid=l+r>>1;if(sum(mid)>=a[i])ans=mid,r=mid-1;else l=mid+1;}res[i]=ans;update(ans,-1);}for(int i=1;i<=n;i++)cout<<res[i]<<'\n';return 0;
}
苹果树
题目
卡卡家门外有一棵苹果树。每年秋天，树上都会长出很多苹果。卡卡非常喜欢苹果，所以他一直在精心培育大苹果树。
这棵树有N个分叉，由树枝连接。卡卡将叉子编号为 1 到 N，根始终编号为 1。苹果会在叉子上生长，两个苹果不会在同一个叉子上生长。卡卡想知道一个子树中有多少个苹果，用于研究苹果树的生产能力。
麻烦的是，一个新的苹果可能会在空叉子上生长一段时间，卡卡可能会从树上摘下一个苹果作为他的甜点。你能帮助卡卡吗？
思路
从根节点dfs，给节点的起点和终点建立下标（起点一定比终点的下标小，父节点的起点一定小于子节点，父节点的终点一定大于子节点），更新每次从起点开始遍历，输出结果从终点 - 起点前，这个节点的终点一定在所有父节点的前面，起点一定在所有父节点的后面，所以终点sum的值包含父节点和子节点，而起点sum的值只包含父节点，所以见一下就是子节点的值。
代码
#include<iostream>
#include<string.h>
using namespace std;
const int N=1e5+5;
int to[N<<1],from[N<<1],head[N],idx;
int vis[N],tot,d[N][2],b[N],c[N];
int n,m;void add(int u,int v){to[idx]=v,from[idx]=head[u],head[u]=idx++;
}void dfs(int u){d[u][0]=++tot; //根节点开始的tot的值一定比子树的小for(int i=head[u];i!=-1;i=from[i]){int j=to[i];if(vis[j])continue;vis[j]=1;dfs(j);}d[u][1]=tot; //根节点结束的tot的值一定比子树的大
}int lowbit(int x){return x&(-x);
}void update(int x){c[x]*=-1;int k=c[x];x=d[x][0];while(x<=n){b[x]+=k;x+=lowbit(x);}
}int sum(int x){int r=0;while(x){r+=b[x];x-=lowbit(x);}return r;
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;memset(head,-1,sizeof head);for(int i=1;i<n;i++){int u,v;cin>>u>>v;add(u,v);}dfs(1);for(int i=1;i<=n;i++){c[i]=-1;update(i);}cin>>m;while(m--){char c;int x;cin>>c>>x;if(c=='Q')cout<<sum(d[x][1])-sum(d[x][0]-1)<<'\n'; //要输出的是子树，所以根节点的范围最大else update(x);}return 0;
}
奇怪的线段
题目
在一维数轴上，小蓝画了n个闭区间线段，小桥会多次询问你，每次给定两个点a，b，问有多少个区间包含a点，但是不包含b点。
思路
容斥原理，包含a的区间 - 包含[a,b]的区间。右端点后的排前面，这样每次查询区间[a,b]的时候，满足左端在它前面的它右端一定在它后面，所以只要满足左端在它前面的区间的数量==包含该区间的所有闭区间数量，包含a点的区间又一开始就给好了，所以易得结果。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int d[N],res[N],c[N];
struct node{int l,r;int id,op;bool operator<(const node&b)const{if(r!=b.r)return r>b.r; //右端大的排前面if(l!=b.l)return l<b.l; //右端一样大，左端小的排前面return op<b.op; //左右两端都一样大，不是查询区间的排前面}
}nb[N<<1];int lowbit(int x){return x&(-x);
}void add(int x){while(x<N){c[x]++;x+=lowbit(x);}
}int sum(int x){int r=0;while(x){r+=c[x];x-=lowbit(x);}return r;
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,q;cin>>n>>q;int l,r;for(int i=1;i<=n;i++){cin>>l>>r;d[l]++,d[r+1]--;nb[i]={l,r,0,0};}for(int i=1;i<N;i++)d[i]+=d[i-1];for(int i=1;i<=q;i++){cin>>l>>r;res[i]=d[l];if(l>r)swap(l,r);nb[++n]={l,r,i,1};}sort(nb+1,nb+1+n);for(int i=1;i<=n;i++){if(nb[i].op==0){add(nb[i].l);}else{res[nb[i].id]-=sum(nb[i].l);}}for(int i=1;i<=q;i++)cout<<res[i]<<'\n';return 0;
}
逆序对的数量
题目
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
1≤n≤100000，
数列中的元素的取值范围 [1,1e9]。
思路
元素取值过大，但数量少，可以离散化，将元素值用下标表示。
因为树状数组是往小的取值，所以sum所得的是下标小的数量，所以应该将元素值大的排前面，如果值相同，下标大的排前面。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,c[N];
struct node{int a,b;bool operator<(const node&x)const{if(a==x.a)return b>x.b;return a>x.a;}
}nb[N];
int lowbit(int x){return x&(-x);
}
void update(int x){while(x<=n){c[x]++;x+=lowbit(x);}
}
int sum(int x){int r=0;while(x){r+=c[x];x-=lowbit(x);}return r;
}
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>nb[i].a;nb[i].b=i;}sort(nb+1,nb+1+n);long long ans=0;for(int i=1;i<=n;i++){ans+=sum(nb[i].b);update(nb[i].b);}cout<<ans;return 0;
}
矩阵(二维)
题目
给定一个 N*N 矩阵 A，其元素为 0 或 1。A[i， j] 表示第 i 行和第 j 列中的数字。最初我们有 A[i， j] = 0 （1 <= i， j <= N）。
我们可以通过以下方式更改矩阵。给定一个左上角为 （x1， y1） 且右下角为 （x2， y2） 的矩形，我们使用 “not” 操作更改矩形中的所有元素（如果它是 ‘0’ 则将其更改为 ‘1’，否则将其更改为 ‘0’）。为了维护矩阵的信息，要求您编写一个程序来接收和执行两种指令。
- C x1 y1 x2 y2 （1 <= x1 <= x2 <= n， 1 <= y1 <= y2 <= n） 通过使用左上角为 （x1， y1） 且右下角为 （x2， y2） 的矩形更改矩阵。
- Q x y （1 <= x， y <= n） 查询 A[x， y]。
思路
二维看，[ a, b ]到[ c, d ]，一维 a 到 c 跟新的话，应该update(a)再update(c+1,-1)，二维原理一样。
代码
#include<iostream>
#include<string.h>
using namespace std;const int N=1e3+5;
int n,c[N][N];int lowbit(int x){return x&(-x);
}
void update(int x,int y,int k){for(int i=x;i<=n;i+=lowbit(i)){for(int j=y;j<=n;j+=lowbit(j)){c[i][j]+=k;}}
}
int sum(int x,int y){int res=0;for(int i=x;i;i-=lowbit(i)){for(int j=y;j;j-=lowbit(j)){res+=c[i][j];}}return res%2;
}
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t,q;cin>>t;while(t--){memset(c,0,sizeof c);cin>>n>>q;while(q--){char c;cin>>c;if(c=='C'){int xx1,yy1,xx2,yy2;cin>>xx1>>yy1>>xx2>>yy2;update(xx1,yy1,1);update(xx2+1,yy2+1,1);update(xx1,yy2+1,-1);update(xx2+1,yy1,-1);}else{int x,y;cin>>x>>y;cout<<sum(x,y)<<'\n';}}cout<<'\n';}return 0;
}
线段树
线段树存的是一个区间里的值
最大数
题目
给定一个正整数数列 a1,a2,…,an，每一个数都在 0∼p−1 之间。
可以对这列数进行两种操作：
- 添加操作：向序列后添加一个数，序列长度变成 n+1；
- 询问操作：询问这个序列中最后 L 个数中最大的数是多少。
程序运行的最开始，整数序列为空。
一共要对整数序列进行 m 次操作。
写一个程序，读入操作的序列，并输出询问操作的答案。
思路
先建树，因为m次操作，所以树的最大值应该不超过m。每个节点记录左子节点的区间左端和右子节点的区间右端，以及自身所带的值。
因为先添加如果被查询的话，后添加的一定已经被查询了，所以先添加的放前面，找最大的时候，取n-x+1即是找最后 x 个数内的最大值。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;struct node{int l,r,w;
}tr[N<<2];void build(int u,int l,int r){tr[u]={l,r,0};if(l==r)return;int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);
}void pushup(int u){tr[u].w=max(tr[u<<1].w,tr[u<<1|1].w);
}void add(int u,int p,int x){if(tr[u].l==p&&tr[u].r==p)tr[u].w=x;else{int mid=tr[u].l+tr[u].r>>1;if(p<=mid)add(u<<1,p,x);else add(u<<1|1,p,x);pushup(u);}
}int query(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r)return tr[u].w;int mid=tr[u].l+tr[u].r>>1,v=0;if(l<=mid)v=query(u<<1,l,r);if(r>mid)v=max(v,query(u<<1|1,l,r));return v;
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);long long m,p,x,a=0,n=0;cin>>m>>p;build(1,1,m);while(m--){char c;cin>>c>>x;if(c=='A'){x=(x+a)%p;add(1,++n,x);}else{a=query(1,n-x+1,n);cout<<a<<'\n';}}return 0;
}
你能回答这些问题吗
题目
给定长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
1 x y，查询区间 [x,y] 中的最大连续子段和。2 x y，把 A[x] 改成 y。
对于每个查询指令，输出一个整数表示答案。
思路
记录每个节点的从右端开始的最大连续字段和，从左端开始的最大连续字段和，从而进行比较，再通过将左子树的右端开始的最大连续字段和 + 右子树的左端开始的最大连续字段和 的值以及左右子树的区间内最大连续字段和得到父节点的区间内最大连续字段和。
答案
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N];struct node{int l,r,sum; //w表示所有int lmax,rmax,tmax;
}tr[N<<2];void pushup(node &u,node &l,node &r){u.sum=l.sum+r.sum;u.lmax=max(l.lmax,l.sum+r.lmax);u.rmax=max(r.rmax,r.sum+l.rmax);u.tmax=max(l.rmax+r.lmax,max(l.tmax,r.tmax));
}void pushup(int u){pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}void build(int u,int l,int r){tr[u]={l,r,0,0,0,0};if(l==r)tr[u]={l,r,a[l],a[l],a[l],a[l]};else{int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}void modify(int u,int p,int w){if(tr[u].l==p&&tr[u].r==p)tr[u]={p,p,w,w,w,w};else{int mid=tr[u].l+tr[u].r>>1;if(mid>=p)modify(u<<1,p,w);else modify(u<<1|1,p,w);pushup(u);}
}node query(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r)return tr[u];int mid=tr[u].l+tr[u].r>>1;if(mid<l)return query(u<<1|1,l,r);else if(mid>=r)return query(u<<1,l,r);else{auto left=query(u<<1,l,r);auto right=query(u<<1|1,l,r);node res;pushup(res,left,right);return res;}
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,q;cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];build(1,1,n);while(q--){int k,x,y;cin>>k>>x>>y;if(k==1){if(x>y)swap(x,y);auto ans=query(1,x,y);cout<<ans.tmax<<'\n';}else modify(1,x,y);}return 0;
}
敌兵布阵
第一行一个整数T，表示有T组数据。
每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;
每组数据最多有40000条命令
#include<bits/stdc++.h>
using namespace std;
const int mxn=5e4+5;
struct node{int l,r,sum;
}t[mxn*4];
int a[mxn];
int build(int l,int r,int u){t[u].l=l,t[u].r=r;if(l==r)return t[u].sum=a[l]; //区间内只有一个数不能再分return t[u].sum=build(l,l+r>>1,u<<1)+build((l+r>>1)+1,r,(u<<1)+1);
}
void add(int i,int num){int u=1;while(1){t[u].sum+=num; //父节点的值增加if(t[u].l==t[u].r&&t[u].l==i)break; //到达子节点则退出if((t[u].l+t[u].r>>1)>=i)u=u<<1; //判断i节点的位置else u=(u<<1)+1;}
}
void sub(int i,int num){int u=1;while(1){t[u].sum-=num;if(t[u].l==t[u].r&&t[u].l==i)break;if((t[u].l+t[u].r>>1)>=i)u=u<<1;else u=(u<<1)+1;}
}
int query(int l,int r,int u){if(l>r||t[u].l>r||t[u].r<l)return 0; //所选区间不存在或者在这颗树的最大区间外返回0if(t[u].l>=l&&t[u].r<=r)return t[u].sum; //如果所选树区间所找范围内返回它的值return query(l,r,u<<1)+query(l,r,(u<<1)+1); //将所找范围内的所有树区间的值相加
}
int T,n,tot,u,v;
string s;
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>T;while(T--){cin>>n;cout<<"Case "<<++tot<<":\n";for(int i=1;i<=n;i++)cin>>a[i];build(1,n,1); //建树while(1){cin>>s;if(s[0]=='E')break;cin>>u>>v;if(s[0]=='Q')cout<<query(u,v,1)<<'\n';else if(s[0]=='A')add(u,v);else if(s[0]=='S')sub(u,v);}}return 0;
}
区间最大公约数
题目
给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。Q l r，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。
对于每个询问，输出一个整数表示答案。
思路
单点加值好加，所以用前缀和存储
gcd(a−nb,b)=gcd(a,b)
(a,b,c)=((a,b),(b,c))=((a,b−a),(b,c−b))=(a,b−a,b,c−b)
由于(b−a,b)=(a,b−a),所以(a,b,c)=(a,b−a,c−b)
所以要求区间[L,R]的最大公约数只要求出a[L]和(a[L+1]-a[L],a[L+2]-a[L+1],…,a[R]-a[R-1])
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+5;
ll s[N];
struct node{ll l,r,w,d;
}tr[N<<2];ll gcd(ll a,ll b){return b?gcd(b,a%b):a;
}void pushup(node &u,node &l,node &r){u.w=l.w+r.w;u.d=gcd(l.d,r.d);
}void pushup(ll u){pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}void build(ll u,ll l,ll r){tr[u]={l,r,0,0};if(l==r){ll m=s[l]-s[l-1];tr[u]={l,r,m,m};}else{ll mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}void modify(ll u,ll p,ll w){if(tr[u].l==tr[u].r&&tr[u].l==p){ll m=tr[u].w+w;tr[u]={p,p,m,m};}else{ll mid=tr[u].l+tr[u].r>>1;if(p<=mid)modify(u<<1,p,w);else modify(u<<1|1,p,w);pushup(u);}
}node query(ll u,ll l,ll r){if(l>r)return {0,0,0,0};if(tr[u].l>=l&&tr[u].r<=r)return tr[u];ll mid=tr[u].l+tr[u].r>>1;if(mid<l)return query(u<<1|1,l,r);else if(mid>=r)return query(u<<1,l,r);else{auto left=query(u<<1,l,r);auto right=query(u<<1|1,l,r);node res;pushup(res,left,right);return res;}
}int main(){ll n,q;cin>>n>>q;for(ll i=1;i<=n;i++){cin>>s[i];}build(1,1,n);while(q--){char c;ll x,y,d;cin>>c;if(c=='Q'){cin>>x>>y;auto left=query(1,1,x);auto right=query(1,x+1,y);cout<<abs(gcd(left.w,right.d))<<'\n';}else{cin>>x>>y>>d;modify(1,x,d);if(y+1<=n)modify(1,y+1,-d);}}return 0;
}
一个简单的整数问题2
题目
给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。Q l r，表示询问数列中第 l∼r 个数的和。
对于每个询问，输出一个整数表示答案。
思路
懒标记，存储区间内需要加的值，区间内加值，先加到父节点上可以减少运行时间，查询、添加的时候先向下遍历，添加结束后向上遍历将父节点的总和值增加。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int a[N];
struct node{int l,r,w,add;
}tr[N<<2];void pushup(node &u,node &l,node &r){u.w=l.w+r.w;
}void pushup(int u){pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}void pushdown(node &u,node &l,node &r){if(u.add){l.add+=u.add,l.w+=(l.r-l.l+1)*u.add;r.add+=u.add,r.w+=(r.r-r.l+1)*u.add;u.add=0;}
}void pushdown(int u){pushdown(tr[u],tr[u<<1],tr[u<<1|1]);
}void build(int u,int l,int r){if(l==r)tr[u]={l,r,a[l],0};else{tr[u]={l,r,0,0};int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}int query(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r)return tr[u].w;else{pushdown(u);int mid=tr[u].l+tr[u].r>>1,v=0;if(l<=mid)v=query(u<<1,l,r);if(r>mid)v+=query(u<<1|1,l,r);return v;}
}void modify(int u,int l,int r,int d){if(tr[u].l>=l&&tr[u].r<=r){tr[u].w+=(tr[u].r-tr[u].l+1)*d;tr[u].add+=d;}else{pushdown(u);int mid=tr[u].l+tr[u].r>>1;if(l<=mid)modify(u<<1,l,r,d);if(r>mid)modify(u<<1|1,l,r,d);pushup(u);}
}signed main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,q;cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];build(1,1,n);while(q--){char c;int x,y,d;cin>>c;if(c=='Q'){cin>>x>>y;cout<<query(1,x,y)<<'\n';}else{cin>>x>>y>>d;modify(1,x,y,d);}}return 0;
}
扫描线
现在假设我们有一根线，从下往上开始扫描：
- 如图所示，我们可以把整个矩形分成如图各个颜色不同的小矩形，那么这个小矩形的高就是我们扫过的距离，那么剩下了一个变量，那就是矩形的长一直在变化。
- 我们的线段树就是为了维护矩形的长，我们给每一个矩形的上下边进行标记，下面的边标记为 1，上面的边标记为 -1，每遇到一个矩形时，我们知道了标记为 1 的边，我们就加进来这一条矩形的长，等到扫描到 -1 时，证明这一条边需要删除，就删去，利用 1 和 -1 可以轻松的到这种状态。
- 还要注意这里的线段树指的并不是线段的一个端点，而指的是一个区间，所以我们要计算的是 r+1 和 r-1。
- 需要 离散化。
亚特兰蒂斯
题目
有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。
其中一些甚至包括岛屿部分地图。
但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。
您的朋友 Bill 必须知道地图的总面积。
你自告奋勇写了一个计算这个总面积的程序。
思路
用vector离散化给出的所有的y坐标，保证每个坐标都有一个编号。
从x坐标左端向右边遍历，每次添加一条坐标x上的边，如果该边是开始，则高应该等于该边的长度 - 与已经包含在内的边的重叠部分；如果该边是结束，则应该将包含在内的边减去这条边所给的贡献。结果就是这条边与上一条加进去的边的x轴坐标距离 * 高。
线段树存储的是所有加进去的y线段的长度，所以tr[1]保存的就是总长
因为y的范围太大，n总数才100，所以需要离散化，每个节点存储一个长度，所以建树的时候总数应该减1。
代码
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#define ing long long
using namespace std;
const int N=1e5+5;struct node{double x,y1,y2;int d;bool operator<(const node&b)const{return x<b.x;}
}s[N<<1];vector<double>v;struct node2{int l,r;int cnt;double w;
}tr[N<<3];void build(int u,int l,int r){tr[u]={l,r,0,0};if(l==r)return;int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);
}void pushup(int u){if(tr[u]t)tr[u].w=v[tr[u].r+1]-v[tr[u].l];elsetr[u].w=tr[u<<1].w+tr[u<<1|1].w;}void modify(int u,int l,int r,int d){if(tr[u].l>=l&&tr[u].r<=r){tr[u]t+=d;pushup(u);}else{int mid=tr[u].l+tr[u].r>>1;if(l<=mid)modify(u<<1,l,r,d);if(r>mid)modify(u<<1|1,l,r,d);pushup(u);}
}int find(double y){return lower_bound(v.begin(),v.end(),y)-v.begin();
}signed main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,t=0;while(cin>>n,n){cout<<"Test case #"<<++t<<'\n';int tot=0;v.clear();for(int i=1;i<=n;i++){double xx1,yy1,xx2,yy2;cin>>xx1>>yy1>>xx2>>yy2; s[++tot]={xx1,yy1,yy2,1};s[++tot]={xx2,yy1,yy2,-1};v.push_back(yy1);v.push_back(yy2);}sort(s+1,s+tot+1);sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());build(1,0,v.size()-2);double res=0;for(int i=1;i<=tot;i++){if(i>1)res+=(s[i].x-s[i-1].x)*tr[1].w;modify(1,find(s[i].y1),find(s[i].y2)-1,s[i].d);}cout<<"Total explored area: "<<fixed<<setprecision(2)<<res<<'\n'<<'\n';}return 0;
}
更多推荐
数据结构攻略
发布评论