template2
2025-01-06 20:28:23
发布于：广东
22阅读
0回复
0点赞
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
typedef long long ll;
namespace Algorithm{
template<class t>
t min(t a,t b){
return a<b?a:b;
}
template<class t>
t max(t a,t b){
return a>b?a:b;
}
template<class t>
void swap(t& a,t& b){
t temp=a;
a=b;
b=temp;
return;
}
ll quicklypow(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans+=a;
a*=a;
b>>=1;
}
return ans;
}
ll qmod(ll a,ll b,const ll& mod){
ll ans=1;
a%=mod;
b%=mod;
while(b){
if(b&1) ans=(ans+a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
void sum(const std::vector<std::vector<int>>&a,std::vector<std::vector<int>>&pre,int n,int m){
for(int i=1;i<=n;++i) pre[i][0]=0;//init
for(int j=1;j<=m;++j) pre[0][j]=0;//init
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
}
}
}
void sum(const std::vector<int>&a,std::vector<int>&pre,int n){
pre[0]=0;//init
for(int i=1;i<=n;++i){
pre[i]=a[i]+pre[i-1];
}
}
void merge(std::vector<std::pair<int,int>>&segs){//合并segs中所有有交集的区间
std::vector<std::pair<int,int>>res;
std::sort(segs.begin(),segs.end());
int l=-2e9,r=-2e9;
for(auto seg:segs){
if(r<seg.first){
if(l!=-2e9){
res.push_back({l,r});
}
l=seg.first,r=seg.second;
}
else{
r=max(r,seg.second);
}
}
if(l!=-2e9){
res.push_back({l,r});
}
segs=res;
}
//ST
const int N=1e5+10;
int f[N][30];
int a[N];
void create_st(int n){
for(int i=1;i<=n;i++){
f[i][0]=a[i];
}
int k=log(n)/log(2);
for(int j=1;j<=k;++j){
for(int i=1;i<=n-(1<<j)+1;++i){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//求区间最大值
}
}
}
int query(int l,int r){
int k=log(r-l+1)/log(2);
return max(f[l][k],f[r-(1<<k)+1][k]);
}
const int M=N;
//117-145 拓扑排序
int h[N],e[M],ne[M],idx; //memset(h, -1, sizeof h);
int din[N]; //入度
int q[N]; //res
void add(int a,int b){
din[b]++;
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool topsort(int n){//检查是否为有向无环图
int hh=0,tt=-1;
for(int i=1;i<=n;++i){ //起点
if(!din[i]){
q[++tt] = i;
}
}
while(hh<=tt){
int t=q[hh++];
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
din[j]--;
if(!din[j]){
q[++tt] = j;
}
}
}
return tt==n-1;
}
}
using namespace Algorithm;
namespace stack{
struct Stack{
public:
Stack(int *a,int n){
_top=0;
for(int i=1;i<=n;++i){
s[++_top]=a[i];
}
}
void push(int &x){
s[++_top]=x;
return;
}
int size(){
return _top;
}
void pop(){
--_top;
return;
}
bool empty(){
return _top==0;
}
int top(){
return s[_top];
}
void clear(){
_top=0;
}
void resize(int n){
_top=min(_top,n);
max_siz=n;
}
bool check(Stack a){
return max_siz==a.max_siz;
}
void replace(Stack a,Stack b){
if(!a.check(b)){
return;
}
for(int i=1;i<=max(a.max_siz,b.max_siz);++i){
a.s[i]=b.s[i];
}
}
private:
int max_siz=1e6+10;
int s[(int)1e6+10];
int _top=0;
};
}
namespace queue{
}
namespace STL{
using namespace stack;
using namespace queue;
}
namespace sort{
void bubblesort(int *a,int n){
}
void insertsort(int *a,int n){
}
void quicklysort(int *a,int l,int r){
if(l>=r){
return;
}
int i=l-1,j=r+1,x=a[l+r>>1];
while(i<j){
while(a[++i]<x);
while(a[--j]>x);
if(i<j){
swap(a[i], a[j]);
}
}
quicklysort(a,l,j);
quicklysort(a,j+1,r);
}
const int N=1e6+10;
int tmp[N];
void merge_sort(int *a,int l,int r){//To use this function,you need to have an array,such as tmp;
if(l>=r) return;
int mid=l+r>>1;
merge_sort(a,l,mid);
merge_sort(a,mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid and j<=r){
if(a[i]<=a[j]){
tmp[k++]=a[i++];
}
else{
tmp[k++]=a[j++];
}
}
while(i<=mid){
tmp[k++]=a[i++];
}
while(j<=r){
tmp[k++]=a[j++];
}
for(i=l,j=0;i<=r;){
a[i++] = tmp[j++];
}
}
}
signed main(){
#define creator fcz_bsa
#define create_time 2025-1-5-17-36
}
有帮助，赞一个