首页 > 其他分享 >模板

模板

时间:2023-09-30 16:11:24浏览次数:26  
标签:sort end int res mid merge 模板

前缀和

s[i] = s[i - 1] + a[i];
s[r] - s[l - 1]

二维前缀和

s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]
s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1]

差分

d[l]++, d[r + 1]--;

二维差分

d[x1][y1]++, d[x2 + 1][y2 + 1]++;
d[x1][y2 + 1]--, d[x2 + 1][y1]--;

二分

while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid)) l = mid + 1;
    else r = mid - 1;
}
cout << l << "\n";

离散化

sort(b + 1, b + 1 + tot);
int m = unique(b + 1, b + 1 + tot) - (b + 1);
for (int i = 1; i <= n; i++) {
    int x = lower_bound(b + 1, b + 1 + m, a[i]) - b;
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (int i = 1; i <= n; i++) {
    int x = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
}

归并排序

void merge_sort(int l, int r) {
    if (r - l < 1) {
        return;
    }
    
    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    
    int i = l, j = mid + 1;
    int pos = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            t[pos++] = a[i], ++i;
        } else {
            t[pos++] = a[j], ++j;
            ans += mid - i + 1; // 求逆序对
        }
    }
    while (i <= mid) {
        t[pos++] = a[i], ++i;
    }
    while (j <= r) {
        t[pos++] = a[j], ++j;
    }
    
    for (int i = l; i <= r; i++) {
        a[i] = t[i];
    }
}

快速幂

int power(int a, int b, int p) {
    int res = 1 % p;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p, b >>= 1;
    }
    return res % p;
}

ST 表

void init() {
    for (int i = 2; i <= n; i++) {
        Log[i] = Log[i >> 1] + 1;
    }

    for (int j = 1; j <= Log[n]; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int RMQ(int l, int r) {
    int k = Log[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

标签:sort,end,int,res,mid,merge,模板
From: https://www.cnblogs.com/unino/p/template.html

相关文章

  • 快读“慢”写模板
    //万能头文件#include<bits/stdc++.h>usingnamespacestd;template<typenameT>inlineTread(T&ret){charc;intf=1;ret=0; //Don'tforgetthis!for(c=getchar();c<'0'||c>'9';c=getchar())if(c==&......
  • 二进制有关操作模板
    lowbit:lowbit(x)是$x$的二进制表达式中最低位的1所对应的值template<typenameT>Tlowbit(Tx){returnx&-x;}求二进制中1的个数:【方法一】库函数:__builtin_popcountll(n)附库函数的具体实现:unsignedpopcount(unsignedu){ u=(u&0x55555555)+......
  • Go每日一库之128:podinfo(k8s微服务模板)
    项目介绍官方Github:PodinfoPodinfo是一个用Go制作的小型web应用程序,它展示了在Kubernetes中运行微服务的最佳实践。它已实现的技术指标(截选自官方README.md):里面每一项技术指标的实现方式,其实都可以拿出来单独讲好久,相关理论也有好多。这里我只是讲针对这个项......
  • 【模板】线性筛素数
    【模板】线性筛素数点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineLLlonglongconstintN=1e8+10;intp[N],cnt,vis[N];intmain(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); intn,q; cin>>n>>q; for(inti=2;i......
  • 快排模板
    voidquick_sort(inta[],intl,intr){if(l>=r)return;inti=l-1,j=r+1,x=a[l+r>>1];while(i<j){doi++;while(a[i]<x);doj--;while(a[j]>x);if(i<j)swap(a[i],a[j]);}quick_sort(......
  • Go每日一库之54:quicktemplate(增强模板库)
    简介最近在整理我们项目代码的时候,发现有很多活动的代码在结构和提供的功能上都非常相似。为了方便今后的开发,我花了一点时间编写了一个生成代码框架的工具,最大程度地降低重复劳动。代码本身并不复杂,且与项目代码关联性较大,这里就不展开介绍了。在这个过程中,我发现Go标准的模板......
  • Ant Design Pro版中后台原型模板及Axure rplib元件库组件
    AntDesignPro版中后台原型模板及Axurerplib元件库组件,AntDesign服务于企业级产品的设计体系,基于确定和自然的设计价值观上的模块化解决方案,让设计者和开发者专注于更好的用户体验。AntDesign是阿里巴巴开源的一套admin框架,是当前非常主流的设计方案。本套素材,使用axureRP软......
  • Idea添加注释模板
    先展示结果具体步骤选择导航栏的File->Settings->Editor->LiveTemplates。点击右边的加号,先创建一个TemplateGroup(名字随意),选中创建的分组,再点击加号创建LiveTemplate。在下方的Abbreviation中设置想使用的快捷键,我这里填的‘*’。Templatetext中填入如下模板......
  • 平衡树模板
    Splay#definelchch[0]#definerchch[1]classSplay{private:structNode{intval,cnt,sz;Node*fa,*ch[2];inlinevoidpushup(){sz=cnt;if(lch)sz+=lch->sz;......
  • 使用ChatGPT快速构建优质网站模板的方法
    随着人工智能技术的不断发展,ChatGPT作为一种自然语言处理工具,正在被越来越多的领域所应用。其中,如何使用ChatGPT快速构建一个网站模板成为了许多开发者和企业关心的热点问题。本文将重点介绍如何使用ChatGPT快速构建一个网站模板,并突出其中的重点词汇或短语。确定网站目标和定位在......