Skip to content

Latest commit

 

History

History
1400 lines (1261 loc) · 27.3 KB

信息学竞赛算法指北.md

File metadata and controls

1400 lines (1261 loc) · 27.3 KB
Raw

title: 信息学竞赛算法指北 categories: 编程 tags: [代码,算法,编程] date: 2019-02-26 16:05:00

排序

STL排序
#include <bits/stdc++.h>
using namespace std;
int main(){
    const int N = 5;
    int a [N] = {12,35,99,18,76};
    sort(a,a+5);
    for(int i = 0;i<N;i++){
        cout<<a[i]<<' ';
    }
    return 0;
}
桶排序
#include <bits/stdc++.h>
#include <conio.h>
using namespace std;
int main(){
	int a = 1,b=100,c=5;
	int srt[100001] = {0};
	//cin>>a>>b>>c;
	srt[a]++;
	srt[b]++;
	srt[c]++;
	for(int i = 1;i<=100000;i++){
		while(srt[i]){
			cout<<i<<' ';
			srt[i]--;
		}
	}
	return 0;
}
冒泡排序
#include <bits/stdc++.h>
#include <conio.h>
using namespace std;
int main(){
    const int N = 5;
    int a [N] = {12,35,99,18,76};

    for(int i = 0;i<N;i++){
        for(int j = 0;j<N-i;j++){
            if(a[j]>a[j+1])
                swap(a[j],a[j+1]);
        }
    }
    for(int i = 0;i<N;i++){
        cout<<a[i]<<' ';
    }
    return 0;
}
快速排序
#include <bits/stdc++.h>
#include <conio.h>
using namespace std;
const int N = 5;
int a [N] = {12,35,99,18,76};
void qs(int l,int r){
    if(l>=r)
        return ;
    int t = a[l];
    int i = l,j=r;
    while(i!=j){
        //必须先右后左
        while(a[j]>=t&&i<j)
            j--;
        while(a[i]<=t&&i<j)
            i++;
        if(i<j)
            swap(a[i],a[j]);
    }
    a[l] = a[i];
    a[i] = t;
    qs(l,i-1);
    qs(i+1,r);
    return ;
}
int main(){
    qs(0,N-1);
    for(int i = 0;i<N;i++){
        cout<<a[i]<<' ';
    }
    return 0;
}

数论

逆元

  • 自己瞎写的，可能是错的
//这个真的太慢了，请看下面那个
#include<bits/stdc++.h>
using namespace std;
const int A = 3,p=11;
unsigned long long inv = 1;
int main(){
	int i;
	for(i = 0;;i++){
		inv = ((i*p+1)/A)%p;
		if((A*inv)%p==1)
			break;
	}
	cout << i << ' ' << inv;
	return 0;
}
  • 现在才是真正的求逆元，用了exgcd
#include<cstdio>
#include<iostream>
using namespace std;
#define pr pair<int ,int >
pr exgcd(int a,int b){
	if(b==0) return pr(1,0);
	pr tmp = exgcd(b,a%b);
	return pr(tmp.second,tmp.first-a/b*tmp.second);
}

int main(){
	int a,b;
	cin>>a>>b;
	int t = exgcd(a,b).first;
	if(t < 0)
		t = t + b;
	cout <<t;
	return 0;
}

欧拉函数

int phi(int n){//对n求欧拉
    int Ans = n;
    for(int i = 2;i<=sqrt(n);i++){//找出每一个因数
        if(n%i == 0){//是因数
            Ans = Ans / i * (i-1);//欧拉函数分解求法
            while(n%i==0)
                n = n / i;//去除该因子
        }
    }
    if(n>1)
        Ans = Ans / n * (n-1);//最后还有因子
    return Ans;
}

图论

最短路

Dijkstra (单源)
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define Rint register int
#define maxN 100005
#define maxM 200005
#define pii pair<int,int>

int qr(){Rint ret=0,f=1;register char ch = getchar();while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar();while(isdigit(ch)) ret=ret*10+ch-'0',ch=getchar();return ret*f;}

int N,M,S;
int fir[maxN],nxt[maxM],ver[maxM],wei[maxM],tot;
int dis[maxN];
bool vis[maxN];
priority_queue <pii,vector<pii>,greater<pii> > q;

void read(int u,int v,int w){
    nxt[++tot] = fir[u];
    fir[u] = tot;
    ver[tot] = v;
    wei[tot] = w;
}

void dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    dis[S] = 0;q.push(pii(0,S));
    while(!q.empty()){
        Rint u = q.top().second,d = q.top().first;q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(Rint i = fir[u];i;i=nxt[i]){
            Rint v = ver[i],w = wei[i];
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                if(!vis[v]) q.push(pii(dis[v],v));
            }
        }
    }
}

int main(){
    N = qr(),M = qr(),S = qr();
    for(Rint i = 1,u,v,w;i<=M;++i){
        u = qr(),v = qr(),w = qr();
        read(u,v,w);
    }
    dijkstra();
    for(Rint i = 1;i<=N;++i){
        printf("%d ",dis[i]);
    }
    return 0;
}
SPFA (单源)
//Code From 算法竞赛进阶指南
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int head[N],ver[M],edge[M],Next[M],d[N];//d是从初始顶点到其他点的距离,ver使出度,edge是路径长度,Next是下一个该顶点的出度，即原来的第二个出度
int n,m,tot;
queue<int> q;
bool v[N];//顶点是否已在队列中

void add(int x,int y,int z){
    //邻接表的添加
    ver[++tot] = y;//ver是终止顶点，tot是总路径数，y是终止顶点
    edge[tot] = z;//edge是路径长度
    Next[tot] = head[x];//Next是下一个该顶点的出度，即原来的第二个出度
    head[x] = tot;//将原来的第二个出度替换为当前添加的出度，原来的第二个出度存放在现在的第二个出度的下一个出度中
}
void SPFA(){
    memset(d,0x3f,sizeof(d));//默认将d最大化，0x3f 这里不解释,反正很大
    memset(v,0,sizeof(v));
    d[1] = 0;//1到1的距离为1
    v[1] = 1;//1号顶点在队列中,与下面一句组合使用使队列中同一顶点只出现一次
    q.push(1);//这里面的1是出发顶点
    while(q.size()){//队列不为空时
        int x = q.front();//取出队首
        q.pop();//删除队首
        v[x] = 0;//代表x已被移除队列
        for(int i = head[x];i != 0;i=Next[i]){//遍历队首所能到达的每一条边
            int y = ver[i];//到达的边
            int z = edge[i];//边长
            if(d[y]>d[x]+z){//判断是否更改"最小距离"
                d[y] = d[x] + z;
                if(!v[y]){
                    q.push(y);//将y顶点加入队列
                    v[y] = 1;//代表y顶点已被移出队列
                }
            }

        }
    }
}
int main(){
    cin>>n>>m;
    for(int i = 1;i<=m;i++){//读入m条边
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    SPFA();
    for(int i = 1;i<=n;i++){
        cout<<d[i]<<endl;
    }
    return 0;
}

//source:5 5 2 3 2 1 2 -3 1 5 5 4 5 2 3 4 3
//ans:0 -3 -1 2 4
Floyd-Wallshall (整张图)
#include <bits/stdc++.h>
#include <conio.h>
using namespace std;
int e[200][200];
int n,m;
void Floyd_Wallshall(){
    for(int k = 1;k<=n;k++){//三层循环通过k来求得当前状态下i->j的路径最小值
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                if(e[i][j] > e[i][k] + e[k][j])
                    e[i][j] = e[i][k] + e[k][j];
            }
        }
    }
    return ;
}
int main(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        memset(e[i],0x3f,sizeof(e[i]));
        e[i][i] = 0;//初始化
    }
    for(int i = 1;i<=m;i++){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);//直接读入
        e[x][y] = z;//直接读入
    }
    Floyd_Wallshall();
    for(int i = 1;i<=n;i++){//输出
        for(int j = 1;j<=n;j++){
            printf("%d ",e[i][j]);
        }
        printf("\n");
    }
    return 0;
}

负环

  • SPFA
//Luogu P3385 【模板】负环
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <ctime>

using namespace std;


const int MaxN = 2003,MaxM= 3005;
int cnt[MaxN];
int tot,T,N,M,d[MaxN];
bool v[MaxN];
int first[MaxN],ver[MaxM * 2],Next[MaxM * 2],wei[MaxM * 2];


void read(int x,int y,int z){
    Next[++tot] = first[x];
    first[x] = tot;
    ver[tot] = y;
    wei[tot] = z;
}
void spfa(){
    int x,y,z;
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    memset(cnt,0,sizeof(cnt));
    d[1] = 0;
    v[1] = 1;
    queue <int> q;
    q.push(1);
    cnt[1] = 1;
    while(q.size()){
        x = q.front();
        q.pop();
        v[x] = false;
        for(int i = first[x];i;i=Next[i]){
            y = ver[i];
            z = wei[i];
            if(d[y]>d[x]+z){
                d[y] = d[x] + z;
                cnt[y] = cnt[x]+1;
                if(cnt[y]>N){
                    cout<<"YE5"<<endl;
                    return ;
                }
                if(!v[y])
                    q.push(y),v[y] = 1;
            }
        }
    }
    cout<<"N0"<<endl;
    return ;
}

void calc(){
    memset(first,0,sizeof(first));
    memset(Next,0,sizeof(Next));
    tot = 0;
    scanf("%d %d",&N,&M);
    int t1,t2,t3;
    for(int i = 1;i<=M;i++){
        scanf("%d %d %d",&t1,&t2,&t3);
        if(t3>=0)
            read(t2,t1,t3);
        read(t1,t2,t3);
    }
    spfa();
}

int main()
{
    scanf("%d",&T);
    while(T--)
        calc();
    return 0;
}

网络流

最大流

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
#include <cstring>

using namespace std;

#define maxN 10005
#define maxM 200005
#define Rint register int
const int inf = 0x3f3f3f3f;
bitset <maxN> vis;

struct edge{
    int u,v,w;
    inline bool operator < (const edge &a){return w < a.w;}
}ed[maxM>>1];

int N,M,S,T;
int fir[maxN],nxt[maxM],ver[maxM],wei[maxM],tot=1,flow,dis[maxN];
long long ans;
inline int qr(){register int ret=0,f=1;register char ch = getchar();while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar();while(isdigit(ch)) ret=ret*10+ch-'0',ch=getchar();return ret*f;}
inline void read(int u,int v,int w){nxt[++tot] = fir[u];fir[u] = tot;ver[tot] = v;wei[tot] = w;}
queue <int> q,emp;
bool bfs(int u){
    q = emp;
    q.push(u);
    memset(dis,0,sizeof(dis));
    while(!q.empty()){
        for(Rint i = fir[q.front()];i;i=nxt[i]){
            if(!wei[i]) continue;
            if(!dis[ver[i]] && ver[i] != u)
                dis[ver[i]]=dis[q.front()]+1,q.push(ver[i]);
        }
        q.pop();
    }
    return dis[T];
}
int dinic(int u,int f){
    // f => max flow ; __f => sum out flow ; _f => one flow
    Rint __f = 0;
    if(u == T){ans+=f;return f;}
    for(Rint i = fir[u];i;i=nxt[i]){
        if( !wei[i] || dis[ver[i]] != dis[u] + 1) continue;
        int _f = dinic(ver[i],min(f-__f,wei[i]));
        __f += _f;
        wei[i] -= _f;
        wei[i^1] += _f;
        if(__f == f) return __f;
    }
    if(__f == 0) dis[u] = 0;
    return __f;
}
int main(){
    N = qr(),M = qr(),S = qr(),T = qr();
    for(Rint i = 1;i<=M;++i)
        ed[i].u = qr(),ed[i].v = qr(),ed[i].w = qr();
    for(Rint i = 1;i<=M;++i){
        read(ed[i].u,ed[i].v,ed[i].w);
        read(ed[i].v,ed[i].u,0);
    }
    while(bfs(S)){
        dinic(S,0x3f3f3f3f);
    }
    printf("%lld\n",ans);
    return 0;
}

割点割边

Tarjan判割点
#include <iostream>
#include <cstdio>

using namespace std;

int n,m;
int first[1000],next[10000],ver[10000];
int tot = 0;
int dfn[1000],low[1000],num=1;
int flag[1000];

void tarjan(int node,int father){
    dfn[node] = low[node] = num++;
    int child = 0;
    for(int i = first[node];i;i=next[i]){
        int togo = ver[i];
        if(dfn[togo] == 0){
            child++;
            tarjan(togo,node);
            low[node] = min(low[node],low[togo]);
            if(node != 1 && low[togo] >= dfn[node]){
                flag[node] = 1;
            }
            else if(node == 1 && child == 2){
                flag[1] = 1;
            }
        }
        else if (togo != father){
            low[node] = min(low[node],low[togo]);
        }
    }
    return ;
}

void read(int x,int y){
    next[tot] = first[x];
    first[x] = tot;
    ver[tot] = y;
    tot++;
    return;
}

int main()
{
    scanf("%d %d",&n,&m);
    int t1,t2;
    for(int i = 1;i<=m;i++){
        scanf("%d %d",&t1,&t2);
        read(t1,t2);
        read(t2,t1);
    }
    tarjan(1,1);
    for(int i = 1;i<=n;i++){
        if(flag[i])
            cout<<i<<' ';
    }
    return 0;
}
//6 7 1 4 1 3 4 2 3 2 2 5 2 6 5 6
//2

并查集

  • Luogu P3367
#include <iostream>
#include <cstdio>

using namespace std;

#define maxn 10002
int N,M;
int fa[maxn];

int f(int x){
    if(fa[x] == x)
        return x;
    return fa[x] = f(fa[x]);
}

int main()
{
    scanf("%d%d",&N,&M);
    for(int i = 1;i<=N;i++){
        fa[i] = i;
    }
    int t1,t2,t3;
    for(int i = 1;i<=M;i++){
        scanf("%d %d %d",&t1,&t2,&t3);
        if(t1 == 1){
            fa[f(t2)] = f(t3);
        }else {
            if(f(t2) == f(t3)){
                printf("Y\n");
            }else{
                printf("N\n");
            }
        }
    }
    return 0;
}

二分图匹配

  • Luogu P3386
  • 以下为未优化代码

用时: 2533ms / 内存: 7100KB

#include <iostream>
#include <bitset>
#include <cstdio>

using namespace std;

#define maxn 2002
#define maxm 1002001
#define itn int

bitset <maxn> book;

int tot,N,M,sum;
int match[maxn],first[maxn],ver[maxm],next[maxm];


void read(int x,int y){
    next[++tot] = first[x];
    first[x] = tot;
    ver[tot] = y;
}
void clean(){
    bitset <maxn> nul;
    book = nul;
}
bool dfs(int nd){
    for(int i = first[nd];i;i=next[i]){
        int v = ver[i];
        if(!book[v]){
            book[v]=1;
            if(match[v] == 0 || dfs(match[v])){
                match[v] = nd;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int tN,t1,t2;
    scanf("%d %d %d",&N,&tN,&M);

    for(int i = 1;i<=M;i++){
        scanf("%d %d",&t1,&t2);
        if(t1>N||t2>tN){
            i--,M--;
            continue;
        }
        read(t1,t2);
    }
    for(int i = 1;i<=N;i++){
        clean();
        if(dfs(i))
            sum++;
    }
    printf("%d",sum);
    return 0;
}
  • 以下为优化代码

用时: 2213ms / 内存: 2992KB

#include <iostream>
#include <bitset>
#include <cstdio>

using namespace std;

#define maxn 2002
#define maxm 1002001
#define itn int

bitset <maxn> book;

int tot,N,M,sum;
int match[maxn],first[maxn],ver[maxm],next[maxm];

inline int qr(){
    char ch;
    int ret = 0,f = 1;
    ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }	
    while(isdigit(ch)){
        ret = ret * 10 + ch - '0';
        ch = getchar();
    }
    return f * ret;
}


inline void read(int x,int y){
    next[++tot] = first[x];
    first[x] = tot;
    ver[tot] = y;
}
inline void clean(){
    bitset <maxn> nul;
    book = nul;
}
bool dfs(int nd){
    for(register int i = first[nd];i;i=next[i]){
        int v = ver[i];
        if(!book[v]){
            book[v]=1;
            if(match[v] == 0 || dfs(match[v])){
                match[v] = nd;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int tN,t1,t2;
    //scanf("%d %d %d",&N,&tN,&M);	
    N = qr();
    tN = qr();
    M = qr();
    
    for(register int i = 1;i<=M;i++){
        //scanf("%d %d",&t1,&t2);
        t1 = qr();
        t2 = qr();
        if(t1>N||t2>tN){
            i--,M--;
            continue;
        }
        read(t1,t2);
    }
    for(register int i = 1;i<=N;i++){
        clean();
        if(dfs(i))
            sum++;
    }
    printf("%d",sum);
    return 0;
}

强联通分量

Tarjan

  • Luogu P2863
#include <iostream>
#include <cstdio>

using namespace std;

#define maxn 10002
int N,M;
int fa[maxn];

int f(int x){
    if(fa[x] == x)
        return x;
    return fa[x] = f(fa[x]);
}

int main()
{
    scanf("%d%d",&N,&M);
    for(int i = 1;i<=N;i++){
        fa[i] = i;
    }
    int t1,t2,t3;
    for(int i = 1;i<=M;i++){
        scanf("%d %d %d",&t1,&t2,&t3);
        if(t1 == 1){
            fa[f(t2)] = f(t3);
        }else {
            if(f(t2) == f(t3)){
                printf("Y\n");
            }else{
                printf("N\n");
            }
        }
    }
    return 0;
}
#include <iostream>
#include <cstdio>
#include <bitset>
#include <stack>


using namespace std;

#define MaxN 10002
#define MaxM 50002
int N,M,tot,id,cnt,ans;
bitset <MaxN> ins;
bitset <MaxN> use;
int color[MaxN] ;
int dfn[MaxN],num[MaxN];
int first[MaxN],ver[MaxM],Next[MaxM];
stack <int> s;

int qr() {
    char ch = getchar();
    int ans = 0;
    while(!isdigit(ch))
        ch = getchar();
    while(isdigit(ch)) {
        ans = ans * 10 + ch - '0';
        ch = getchar();
    }
    return ans;
}

void read(int x,int y) {
    Next[++tot] = first[x];
    first[x] = tot;
    ver[tot] = y;
}

void tarjan(int nd) {
    ins[nd] = 1;
    s.push(nd);
    dfn[nd] = num[nd] = ++id;
    for(int i = first[nd]; i; i=Next[i]) {
        int access = ver[i];
        if(!dfn[access]) {
            tarjan(access);
            num[nd] = min(num[nd],num[access]);
        } else if(ins[access]) {
            num[nd] = min(num[nd],dfn[access]);
        }
    }
    if(dfn[nd] == num[nd]){
        cnt++;
        int v;
        do{
            color[cnt]++;
            v = s.top();
            s.pop();
            ins[v] = 0;
            use[v] = 1;
        }while(nd != v);
    }
}

int main() {
    N = qr();
    M = qr();
    int t1,t2;
    for(int i = 1; i<=M; i++) {
        t1 = qr();
        t2 = qr();
        read (t1,t2);
    }
    for(int i = 1; i<=N; i++) {
        if(!use[i])
            tarjan(i);
    }
    for(int i = 1;i<=cnt;i++){
        if(color[i]>1)
            ans++;
    }
    cout<<ans;
    return 0;
}

动态规划

0/1背包

for (int i = 1; i <= n; ++i) {
	for (int j = 0; j <= m; ++j) {
		if (j < w[i])
			f[i][j] = f[i - 1][j];
		else
			f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
	}
}

完全背包

#include <iostream>

using namespace std;

int T,M;

struct drug{
    int time;
    int value;
}a[105];
int f[1005];


int main()
{
    ios::sync_with_stdio(false);
    cin>>T>>M;
    int t1,t2;
    for(int i = 1;i<=M;i++){
        cin>>a[i].time>>a[i].value;
    }
    for(int i = 1;i<=M;i++){
        for(int j = a[i].time;j<=T;j++){
            f[j]=max(f[j],f[j-a[i].time]+a[i].value);
        }
    }
    cout<<f[T];
    return 0;
}

### 树状背包

```cpp
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;

#define maxn 65
#define maxm 32005

bitset <maxn> E[maxn];
int id[maxn],di[maxn],cnt,ri[maxn];
int N,M,w[maxn],val[maxn];
int f[maxn][maxm];

void dfs(int nd){
    id[nd] = cnt;
    di[cnt] = nd;
    cnt ++;
    for(int i = 1;i<=N;i++){
        if(E[nd][i])
            dfs(i);
    }
    ri[id[nd]] = cnt;
}

int main(){
    cin>>M>>N;
    int p,q;
    for(int i = 1;i<=N;i++){
        cin>>w[i]>>p>>q;
        val[i] = w[i] * p;
        E[q][i] = 1;
    }
    dfs(0);
    for(int i = N;i>=0;i--){
        for(int j = 1;j<=M;j++){
            int k = di[i];
            if(j>=w[k])
                f[i][j] = max(f[ri[i]][j],f[i+1][j-w[k]]+val[k]);
            else f[i][j] = f[ri[i]][j];
        }
    }
    cout<<f[0][M];
    return 0;
}

分组背包

//我要是再输出调试信息我当场cs
#include <iostream>
#include <vector>
using namespace std;

struct th
{
    int weight;
    int value;
};
int m,n,maxgroup;
int weight[1001];
vector <th> thing[101];

int main()
{
    ios::sync_with_stdio(false);

    cin>>m>>n;
    int t1,t2,t3;
    for(int i = 1; i<=n; i++)
    {
        struct th tmp;
        cin>>t1>>t2>>t3;
        tmp.weight=t1;
        tmp.value=t2;
        thing[t3].push_back(tmp);
        maxgroup = max(maxgroup,t3);
    }
/*
    for(int i = 0; i<=maxgroup; i++)
    {
            for(unsigned int j = 0; j!=thing[i].size(); j++)
            {
                cout<<i<<' '<<j<<' '<<thing[i][j].value<<' '<<thing[i][j].weight<<endl;
            }
    }*/
    for(int i = 0; i<=maxgroup; i++)
    {
        for(int k = m; k>=0; k--)
            for(unsigned int j = 0; j!=thing[i].size(); j++)
            {
                if(k>=thing[i][j].weight){
                    //cout<<thing[i][j].weight<<endl;
                    //cout<<max(weight[k],weight[k-thing[i][j].weight]+weight[k-thing[i][j].weight]+thing[i][j].value)<<endl;
                    weight[k] = max(weight[k],weight[k-thing[i][j].weight]+thing[i][j].value);
                    //cout<<weight[k-thing[i][j].weight]<<' '<<thing[i][j].value<<endl;
                }
            }
    }
    cout<<weight[m];
    return 0;
}
## 数据结构

### 线段树

[线段树讲解](https://www.luogu.org/blog/derren/solution-p3372)

#### 单点修改多点查询


- ACOJ 12222

```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

#define ll long long
#define l(p) p<<1
#define lt(p) t[p<<1]
#define r(p) p<<1|1
#define rt(p) t[p<<1|1]
#define maxn 100000
#define Mid int mid = (t[p].l+t[p].r)>>1
#define Luogu

#ifdef Luogu
#define read scanf("%d",&M),build(1,1,N);
#endif // Luogu

#ifdef Acoj
#define read build(1,1,N),scanf("%d",&M);
#endif // Acoj

struct node{
    int l,r;
    ll w,f;
}t[maxn<<2+3];

void build(int p,int l,int r){
    t[p].l = l;
    t[p].r = r;
    if(l == r){
        //int t;
        //scanf("%d",&t);
        scanf("%lld",&t[p].w);
        return;
    }
    int mid = (l+r)>>1;
    build(l(p),l,mid);
    build(r(p),mid+1,r);
    t[p].w = lt(p).w+rt(p).w;
}

void spread(int p){
    if(t[p].f){
        lt(p).w += t[p].f*(lt(p).r-lt(p).l+1);
        rt(p).w += t[p].f*(rt(p).r-rt(p).l+1);
        lt(p).f += t[p].f;
        rt(p).f += t[p].f;
        t[p].f = 0;
    }
}

void change(int p,int l,int r,int z){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].w += (ll)z*(t[p].r-t[p].l+1);
        t[p].f += z;
        return ;
    }
    spread(p);
    Mid;
    if(l<=mid) change(l(p),l,r,z);
    if(r> mid) change(r(p),l,r,z);
    t[p].w = lt(p).w+rt(p).w;
}
ll ask(int p,int l,int r){
    if(t[p].l>=l&&t[p].r<=r){
        return t[p].w;
    }
    spread(p);
    ll ans = 0;
    Mid;
    if(l<=mid) ans+=ask(l(p),l,r);
    if(r> mid) ans+=ask(r(p),l,r);
    return ans;
}

int N,M;
int main()
{
    scanf("%d",&N);
    read
    int t1,t2,t3;
    for(int i = 1;i<=M;i++){
        scanf("%d",&t1);
        if(t1 == 1){
            scanf("%d %d %d",&t1,&t2,&t3);
            change(1,t1,t2,t3);
        }else {
            scanf("%d %d",&t2,&t3);
            cout<<ask(1,t2,t3)<<endl;
        }
    }
    return 0;
}

区间查询

#include <iostream>
#include <cstdio>

using namespace std;

#define Rint register int
#define il inline
#define maxN 100005
#define ls (p<<1)
#define rs (p<<1|1)

typedef long long ll;

int qr(){Rint ret=0,f=1;register char ch = getchar();while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar();while(isdigit(ch)) ret=ret*10+ch-'0',ch=getchar();return ret*f;}

int a[maxN];

struct ST{
    struct tree{
        ll val,laz;
    };
    tree T[maxN<<2];
    void build(int p,int pl,int pr){
        if(pl == pr){
            T[p].val = a[pl];
            return ;
        }
        int mid = (pl + pr) >> 1;
        build(ls,pl,mid);
        build(rs,mid+1,pr);
        T[p].val = T[ls].val + T[rs].val;
    }
    void pushdown(int p,int pl,int pr){
        if(T[p].laz){
            int mid = (pl+pr)>>1;
            T[ls].laz += T[p].laz;
            T[rs].laz += T[p].laz;
            T[ls].val += T[p].laz * (mid-pl+1);
            T[rs].val += T[p].laz * (pr - mid);
            T[p].laz = 0;
        }
    }
    void edit(int p,int pl,int pr,int l,int r,int val){
        if(l <= pl && pr <= r){
            T[p].val += val*(pr-pl+1);
            T[p].laz += val;
            return ;
        }
        pushdown(p,pl,pr);
        int mid = (pl+pr)>>1;
        if(l<=mid) edit(ls,pl,mid,l,r,val);
        if(r> mid) edit(rs,mid+1,pr,l,r,val);
        T[p].val = T[ls].val + T[rs].val;
        return ;
    }
    ll get_range(int p,int pl,int pr,int l,int r){
        if(l<=pl && pr <= r){
            return T[p].val;
        }
        pushdown(p,pl,pr);
        int mid = (pl+pr)>>1;
        ll ret=0;
        if(l<=mid) ret += get_range(ls,pl,mid,l,r);
        if(r> mid) ret += get_range(rs,mid+1,pr,l,r);
        return ret;
    }
}t;
int N,M;
int main(){
    N = qr(),M = qr();
    for(Rint i = 1;i<=N;++i) a[i] = qr();
    t.build(1,1,N);
    for(Rint i = 1,t1,t2,t3,t4;i<=M;++i){
        t1 = qr();
        if(t1 == 1){
            t2 = qr(),t3 = qr(),t4 = qr();
            t.edit(1,1,N,t2,t3,t4);
        }else {
            t2 = qr(),t3 = qr();
            printf("%lld\n",t.get_range(1,1,N,t2,t3));
        }
    }
    return 0;
}

主席树-可持久化线段树

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

#define maxN 200005

int qr(){int ret=0,f=1;char ch=getchar();while(!isdigit(ch))f=ch=='-'?-1:1,ch=getchar();while (isdigit(ch))ret=ret*10+ch-'0',ch=getchar();return ret*f;}

typedef long long LL;

struct PT{
    struct Tree{int l,r;LL val;}tree[maxN<<5];
    int root[maxN],top;
    #define t tree[p]
    int clone(int p){
        tree[++top] = tree[p];
        return top;
    }
    int build(int p,int l,int r){
        p = ++top;
        if(l==r){
            return top;
        }
        int mid = (l+r) >> 1;
        t.l = build(t.l,l,mid);
        t.r = build(t.r,mid+1,r);
        return p;
    }
    int change(int p,int l,int r,int plc){
        p = clone(p);
        if(l==r){
            t.val++;
            return p;
        }
        int mid = (l+r)>>1;
        if(plc <= mid) t.l=change(t.l,l,mid,plc);
        else t.r=change(t.r,mid+1,r,plc);
        t.val = tree[t.l].val + tree[t.r].val;
        return p;
    }
    int query(int root1,int root2,int l,int r,int k){
        if(l == r)
            return l;
        int lval = tree[tree[root2].l].val - tree[tree[root1].l].val;
        int mid = (l+r)>>1;
        if (lval >=k) return query(tree[root1].l,tree[root2].l,l,mid,k);
        else return query(tree[root1].r,tree[root2].r,mid+1,r,k-lval);
    }
}a;

int dat[maxN],dat_bak[maxN],datEnd;

int bs(int x){
    return lower_bound(dat+1,dat+datEnd+1,x) - dat;
}

int main(){
    //freopen("C:/testdata.in","r",stdin);
    int N,M;
    N = qr(),M = qr();
    for(int i = 1;i<=N;i++)
        dat[i] = qr();
    memcpy(dat_bak,dat,sizeof(dat));
    sort(dat+1,dat+N+1);
    datEnd = unique(dat+1,dat+N+1) - dat - 1;
    a.root[0] = a.build(1,1,datEnd);
    for(int i = 1;i<=N;i++)
        a.root[i] = a.change(a.root[i-1],1,datEnd,bs(dat_bak[i]));
    int t1,t2,t3;
    for(int i = 1;i<=M;i++){
        t1 = qr(),t2 = qr(),t3 = qr();
        printf("%d\n",dat[a.query(a.root[t1-1],a.root[t2],1,datEnd,t3)]);
    }
    return 0;
}

树状数组

单点修改

  • LuoguP3374
#include <iostream>
#include <cstdio>

using namespace std;

int A[500002];
int N,M;
int lowbit(int a){
    return a&(-a);
}
void add(int a,int b){
    while(a<=N){
        A[a]+=b;
        a += lowbit(a);
    }
}
int Find(int a){
    int ans = 0;
    while(a>0){
        ans += A[a];
        a -= lowbit(a);
    }
    return ans;
}
int main()
{
    int t1,t2,t3;
    scanf("%d %d",&N,&M);
    for(int i = 1;i<=N;i++){
        scanf("%d",&t1);
        add(i,t1);
    }
    for(int i = 1;i<=M;i++){
        scanf("%d",&t1);
        if(t1 == 1){
            scanf("%d %d",&t2,&t3);
            add(t2,t3);
        } else {
            scanf("%d %d",&t2,&t3);
            cout<<Find(t3)-Find(t2-1)<<endl;
        }
    }
    return 0;
}

ST表

  • 这个是真的迷
  • Luogu P3865
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int a[100005][40];

inline int qr(){
    char ch;
    int ret=0;
    ch = getchar();
    while(!isdigit(ch))
        ch = getchar();
    while(isdigit(ch)){
        ret = ret * 10 + ch - '0';
        ch = getchar();
    }
    return ret;
}
int main()
{
    int N,M;
    N=qr();M=qr();
    for(int i = 1;i<=N;i++){
        a[i][0] =  qr();
    }
    for(int i = 1;i<=21;i++){
        for(int j = 1;j+(1<<i)-1<=N;j++){
            a[j][i] = max(a[j][i-1],a[j+(1<<(i-1))][i-1]);
        }
    }
    int t1,t2;
    for(int i = 1;i<=M;i++){
        t1=qr();t2=qr();
        int k = log2(t2-t1+1);
        printf("%d\n",max(a[t1][k],a[t2-(1<<k)+1][k]));
    }
    return 0;
}