DAY01-DAY03 模板记录
2025-08-04 13:27:39
发布于：上海
3阅读
0回复
0点赞
DAY01 ST表：链接描述
ST表主要用于求区间最值。
代码（用时7-8min,过长)：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int m,n;
int a[N];
int dp_min[N][25];
int main(){
cin>>m>>n;
for(int i=1;i<=m;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
dp_min[i][0]=a[i];
}
for(int k=1;k<=log2(m);k++){
for(int s=1;s<=m;s++){
if(s+(1<<(k-1))>m)break;
dp_min[s][k]=min(dp_min[s][k-1],dp_min[s+(1<<(k-1))][k-1]);
}
}
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
int k=log2(y-x+1);
cout<<min(dp_min[x][k],dp_min[y-(1<<k)+1][k])<<" ";
}
return 0;
}
DAY02 归并排序&快速排序。
归并排序（纯模板）：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
long long a[N],b[N];
void p(int ll,int mm,int rr){
int i=ll,j=mm+1,t=0;
while(i<=mm&&j<=rr){
if(a[i]>a[j])b[t++]=a[j++];
else b[t++]=a[i++];
}
while(i<=mm)b[t++]=a[i++];
while(j<=mm)b[t++]=a[j++];
for(int i=0;i<t;i++)a[i+ll]=b[i];
}
void c(int l,int r){
if(l<r){
int mid=l+r>>1;
c(l,mid);
c(mid+1,r);
p(l,mid,r);
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
c(1,n);
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
return 0;
}
归并排序（逆序对）：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n;
int a[N],b[N];
long long cnt;
void p(int ll,int mm,int rr){
int i=ll,j=mm+1,t=0;
while(i<=mm&&j<=rr){
if(a[i]>a[j]){
cnt+=mm-i+1;
b[t++]=a[j++];
}else b[t++]=a[i++];
}
while(i<=mm)b[t++]=a[i++];
while(j<=rr)b[t++]=a[j++];
for(int i=0;i<t;i++)a[i+ll]=b[i];
}
void c(int l,int r){
if(l>=r)return;
int mid=l+r>>1;
c(l,mid);
c(mid+1,r);
p(l,mid,r);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
c(1,n);
cout<<cnt;
return 0;
}
快速排序：(需要重默）
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
int a[N];
void c(int l,int r){
if(l>=r)return;
int zhun=a[l];
int i=l;
int j=r;
while(i<j){
while(i<j&&a[j]>=zhun)j--;
while(i<j&&a[i]<=zhun)i++;
swap(a[i],a[j]);
}
swap(a[l],a[i]);
c(l,i-1);
c(i+1,r);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
c(1,n);
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
return 0;
}
DAY03 ：树状数组。
树状数组（单点操作，输出区间和）：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5;
int n,m,s,y,z;
int a[N],c[N];
int lowbit(int x){
return x&-x;
}
void add(int x,int pos){
for(;x<=n;x+=lowbit(x))c[x]+=pos;
}
int sum(int x){
int ans=0;
for(;x>0;x-=lowbit(x))ans+=c[x];
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,a[i]);
}
for(int i=1;i<=m;i++){
cin>>s>>y>>z;
if(s==1)add(y,z);
else cout<<sum(z)-sum(y-1)<<'\n';
}
return 0;
}
树状数组（区间操作，输出单点）：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,s;
int a[N],d[N],c[N];
int lowbit(int x){
return x&-x;
}
void add(int x,int pos){
for(;x<=n;x+=lowbit(x))c[x]+=pos;
}
int sum(int x){
int ans=0;
for(;x>0;x-=lowbit(x))ans+=c[x];
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
d[i]=a[i]-a[i-1];
add(i,d[i]);
}
for(int i=1;i<=m;i++){
cin>>s;
if(s==1){
int y,z,k;
cin>>y>>z>>k;
add(y,k);
add(z+1,-k);
}else{
int y;
cin>>y;
cout<<sum(y)<<'\n';
}
}
return 0;
}
这里空空如也
有帮助，赞一个