常用代码

cin.tie(0)->sync_with_stdio(false);
//解除与c输入输出stdio（scanf、printf）的联系，可以提升输入输出速率，但解除之后不能混合使用。

不改变元素位置的 sort

通过阅读《C++ sort()排序函数》一节，读者已经了解了 sort() 函数的功能和用法。值得一提的是，当指定范围内包含多个相等的元素时，sort() 排序函数无法保证不改变它们的相对位置。那么，如果既要完成排序又要保证相等元素的相对位置，该怎么办呢？可以使用 stable_sort() 函数。

stable_sort()

stl的rotate

rotate可以传入三个参数，将第二个参数到第三个参数的元素放到第一个参数前面
rotate(objects.begin(), objects.begin() + pos, objects.end());

树状数组 推荐视频 https://www.bilibili.com/video/BV1pE41197Qj

洛谷 P3374 【模板】树状数组 1 https://www.luogu.com.cn/problem/P3374

【模板】树状数组 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 $x$

• 求出某区间每一个数的和

输入格式

第一行包含两个正整数 $n,m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：

• 1 x k 含义：将第 $x$ 个数加上 $k$

• 2 x y 含义：输出区间 $[x,y]$ 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 $2$ 的结果。

样例 #1

样例输入 #1

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

样例输出 #1

14
16

提示

【数据范围】

对于 $30\%$ 的数据，$1 \le n \le 8$，$1\le m \le 10$；
对于 $70\%$ 的数据，$1\le n,m \le 10^4$；
对于 $100\%$ 的数据，$1\le n,m \le 5\times 10^5$。

样例说明：

故输出结果14、16

#include <bits/stdc++.h>
using namespace std;
const int N=5*1e5+10;
int t[N];
int n;
void add(int x,int k){
    for(;x<=n;x+=x&-x) t[x]+=k;
}
int ask(int x){
    int ans=0;
    for(;x;x-=x&-x) ans+=t[x];
    return ans;
}
int main(){
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) 
    {int x;
     cin>>x;
     add(i,x);
    }
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int x,k;
            cin>>x>>k;
            add(x,k);
        }
        else if(op==2){
            int x,y;
            cin>>x>>y;
            cout<<ask(y)-ask(x-1)<<endl;
        }
    }


    return 0;
}

洛谷 P3368 【模板】树状数组 2 https://www.luogu.com.cn/problem/P3368

这个题目是树状数组的一个拓展,在树状数组中可以用前 i 项的和来表示第 i 个数.

那么当对 x ~ y 的区间进行修改的时候需要在树状数组中的第 x 个位置 + k, 第 y + 1 个位置 -k

这样便维护了这个树状数组

输出时候直接输出查询即可

【模板】树状数组 2

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 $x$；

2. 求出某一个数的值。

输入格式

第一行包含两个整数 $N$、$M$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $N$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $M$ 行每行包含 $2$ 或 $4$个整数，表示一个操作，具体如下：

操作 $1$： 格式：1 x y k 含义：将区间 $[x,y]$ 内每个数加上 $k$；

操作 $2$： 格式：2 x 含义：输出第 $x$ 个数的值。

输出格式

输出包含若干行整数，即为所有操作 $2$ 的结果。

样例 #1

样例输入 #1

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

样例输出 #1

6
10

提示

样例 1 解释：

故输出结果为 6、10。

数据规模与约定

对于 $30\%$ 的数据：$N\le8$，$M\le10$；

对于 $70\%$ 的数据：$N\le 10000$，$M\le10000$；

对于 $100\%$ 的数据：$1 \leq N, M\le 500000$，$1 \leq x, y \leq n$，保证任意时刻序列中任意元素的绝对值都不大于 $2^{30}$。

#include <bits/stdc++.h>
using namespace std;
const int N=5*1e5+10;
int t[N];
int n;
void add(int x,int k){
    for(;x<=n;x+=x&-x) t[x]+=k;
}
int ask(int x){
    int ans=0;
    for(;x;x-=x&-x) ans+=t[x];
    return ans;
}
int main(){
    int m;
    cin>>n>>m;
    int a,b;
    for(int i=1;i<=n;i++) 
    {cin>>a;
     add(i,a-b);
     b=a;
    }
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int x,y,k;
            cin>>x>>y>>k;
            add(x,k);
            add(y+1,-k);
        }
        else if(op==2){
            int x;
            cin>>x;
            cout<<ask(x)<<endl;
        }
    }

    return 0;
}

数状数组好题 题目地址 https://ac.nowcoder.com/acm/problem/239024

来源 2022河南萌新联赛第（二）场 比赛地址 https://ac.nowcoder.com/acm/contest/37344

思路

https://cdndoc.pcs.baidu.com/rest/2.0/docview/doc?datatype=pic&dp_logid=24452951802369540&expires=3h&fid=1332387745-250528-865751361966926&ipmd5=47c06cdbf0d43a68b462724874dc8f6a&method=data&nf=1&object=b10faa5a7ua6caa8ddfbad373d40928f&rt=sh&sign=FOTRE-DCb740ccc5511e5e8fedcff06b081203-4Gu%252Ba5Ks%252FO7ic391H3SS%252F%252Bw%252FimI%253D&timestamp=1658237432&uar=9daae75253a5224f4d3c931a84309a9e&env=web&product=share&pagenum=7

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1*1e14+10;
const int N=1e6+10;
int n;
ll x,y;
ll sum[N],t[N];
vector<ll> ve;
void add(int x,ll k){
    for(;x<=N;x+=x&-x)
        t[x]+=k;
}
ll ask(int x){
    ll res=0;
    for(;x;x-=x&-x) 
       res+=t[x];
    return res;
}
int get(ll x){
    return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1;
}
int main(){
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++){
        cin>>sum[i];
        sum[i]+=sum[i-1]-y;
    }
    for(int i=0;i<=n;i++){
        ve.push_back(sum[i]);
    }
    sort(ve.begin(),ve.end());
    ll ans=0;
    for(int i=0;i<=n;i++){
        ans+=i-ask(get(sum[i]-x)-1);
        add(get(sum[i]),1);
    }

    cout<<ans;

    return 0;
}