rt。
st表
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
using namespace std;
int read(){
int res=0,fs=1; char c=getchar();
while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res*fs;
}
void print(int x){
if(x<0) { putchar('-'); x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int n,cnt,m,a[100010],ans,tmp,lg[101001],st[101011][40];
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++){
// cin>>a[i];
a[i]=read();
}
lg[1]=0;
for(int i=2;i<=n;i++){
lg[i]=lg[i/2]+1;
}
for(int i=n;i>=1;i--){
for(int j=0;j<=log2(n);j++){
if(i+(1<<j-1)>n) break;
if(j==0) st[i][0]=a[i];
else{
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
while(m--){
int l,r;
l=read(),r=read();
int x=lg[r-l+1];
cout<<max(st[l][x],st[r-(1<<x)+1][x])<<'\n';
}
return 0;
}
01背包
/*writer:houpingze 绿√*/
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
using namespace std;
int read(){
int res=0,fs=1; char c=getchar();
while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res*fs;
}
void print(int x){
if(x<0) { putchar('-'); x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int n,cnt,m,a,ans,tmp,w[101],v[101],f[111][1111];
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
else f[i][j]=f[i-1][j];
}
}
cout<<f[n][m];
return 0;
}
快速排序
#include<iostream>
#include<bits/stdc++.h>
#include <ctime>
typedef unsigned long long ull;
using namespace std;
int n,cnt,m;
short a[5000*8000];
bool cmp(int x,int y){return x<y;}
void akioi(short a[],int l,int r){
int i=l,j=r,mid=a[(l+r)/2];
while(i<=j){
while(cmp(a[i],mid)) i++;
while(cmp(mid,a[j])) j--;
if(i<=j) swap(a[i],a[j]),i++,j--;
}
if(l<j) akioi(a,l,j);
if(i<r) akioi(a,i,r);
}
int main(){
cin>>n;
// for(int i=1;i<=n;i++) a[i]=rand()%3892,srand(time(0)+i);
// cout<<"OK!\n";
akioi(a,1,n);
for(int i=1;i<=n;i++) cout<<a[i]<<' ';
}
线段树单点修改区间查询：
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
#define int long long
using namespace std;
int read(){
int res=0,fs=1; char c=getchar();
while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res*fs;
}
void print(int x){
if(x<0) { putchar('-'); x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int n,cnt,m,a[100010],ans,tmp;
struct node{
int ans,x,y;
}t[100005*4];
void build(int p,int l,int r){
if(l==r){
t[p].ans=a[l];
return ;
}
t[p].x=l,t[p].y=r;
t[p*2].x=l,t[p*2].y=(l+r)/2;
t[p*2+1].x=(l+r)/2+1,t[p*2+1].y=r;
build(p*2,l,(l+r)/2);
build(p*2+1,(l+r)/2+1,r);
t[p].ans=t[p*2].ans+t[p*2+1].ans;
}
void update(int p,int x,int l,int r,int id){
if(id<l||id>r) return ;
if(l==r){
t[p].ans+=x;
return ;
}
update(p*2,x,l,(l+r)/2,id);
update(p*2+1,x,(l+r)/2+1,r,id);
t[p].ans=t[p*2].ans+t[p*2+1].ans;
}
int query(int p,int l,int r,int x,int y){
if(r<x||l>y) return 0;
if(x<=l&&r<=y){
return t[p].ans;
}
int m=(l+r)/2;
return query(p*2,l,m,x,y)+query(p*2+1,m+1,r,x,y);
}
signed main() {
cin>>n>>m;
build(1,1,n);
while(m--){
int x=read();
if(x==0){
int i=read(),xx=read();
update(1,xx,1,n,i);
}else{
int l=read(),r=read();
cout<<query(1,1,n,l,r)<<'\n';
}
}
return 0;
}
快速幂：
#include<iostream>
typedef unsigned long long ull;
using namespace std;
ull n,cnt,m;
int main(){
ull b,p,k;
ull x=1;
cin>>b>>p>>k;
cout<<b<<"^"<<p<<" mod "<<k<<"=";
while(p){
if(p%2==0){
p/=2;
b=b*b%k;
}else{
p/=2;
x*=(b%k);
x%=k;
b=b*b%k;
}
}
cout<<x%k;
}