E. Special Elements（前缀和+尺取）

题目传送门http://codeforces.com/problemset/problem/1352/E

#include<iostream>
#include<algorithm>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e4+10;
typedef long long ll;
int t,a[maxn],sum[maxn];
int  vis[maxn];
int n;

bool Check(int x){               //尺取看是否元素满足题意
    int l=1,r=2;
    while(r <= n){
        int t=sum[r]-sum[l-1];

        if(t == x){
            return true;
        }
        if(t > x) l++;
        else r++;
        if(l == r) r++;
    }
    return false;
}

int main()
{
    ios;
    cin>>t;
    while(t--){
        int cnt=0;
        memset(vis,0,sizeof(vis));
        memset(sum,0,sizeof(sum));
        cin>>n;
        for(int i=1 ; i<=n; i++){
            cin>>a[i];
            vis[a[i]]++;
            sum[i]=sum[i-1]+a[i];       //定义前缀和数组
        }
        //cout<<vis[4]<<"\n";
        for(int i=1;i<=n;i++){
            if(!vis[a[i]]) continue;
            else{
                if(Check(a[i]))
                    cnt += vis[a[i]];    //用vis[]数组作为桶把元素装起来，一个元素符合，说明都符合
                    vis[a[i]]=0;  //别忘了消除标记
            }
        }
        cout<<cnt<<"\n";
    }
}

P3406 海底高铁

P3406 海底高铁
差分，求出每段路走的次数，在用前缀和解出答案

#include<iostream>
using namespace std;
char ch;
template<class T>
inline void rd(T& x) {//快读不解释了哈
    x = 0; int w = 1;
    ch = getchar();
    while (ch < '0' || ch>'9') {
        if (ch == '-')w = -1; ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    x = x * w;
}
int a[100001];  unsigned long long t ,sum;
int main()
{
    int n, m,x,y,z;
    rd(n), rd(m);
    rd(x);
    for (int i = 2; i <= m; i++)
    {
        rd(y);//这个循环是安装路牌的过程
        if (x < y)
        {
            a[x]++;
            a[y]--;
        }
        else
        {
            a[x]--;
            a[y]++;
        }
        x = y;
    }

    for (int i = 1; i < n; i++)
    {
        t += a[i];
        rd(x),rd(y),rd(z);
        sum += t * y + z < t * x ? t * y + z : t * x; //这一块决定是不是买卡

    }
    cout << sum;
    return 0;
}

差分（着实有些简单）（Acwing797）

#include<iostream>
#include<algorithm>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
int a[maxn],ca[maxn],n,m;

void add(int l,int r,int c){
    ca[l]+=c;
    ca[r+1]-=c;
}

void Recover(){
    ca[0]=0;
    for(int i=1;i <= n;i++){
        ca[i]+=ca[i-1];
    }
}

int main()
{
    a[0]=0;
    ca[0]=0;
    ios;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ca[i]=a[i]-a[i-1];
    }
    int l,r,c;
    while(m--){
        cin>>l>>r>>c;
        add(l,r,c);
    }
    Recover();
    for(int i=1;i<=n;i++) cout<<ca[i]<<" ";
    return 0;
}

Acwing1270. 数列区间最大值

传送门
第一次做的时候不知道算法，暴力超时，现在看了大佬的题解才懂
我是用树状数组做的，其他解法还有好多算法我不会，准备这两天学

#include<iostream>
#include<algorithm>

int lowest_bit(int n) { return n & (-n); }
//求长度，例如i==8，等于 1000B ，则该数组单元包括了data[8]本身的数据，
//而二进制又有三个零，所以又包括了i之前的七个数据，加上本身的数据就是2^3 =8；
const int space = 1e6 + 7;
int ali[space] = {}, al[space] = {};//ali数组是保存树状数组的值，而al数组保存的是每个单元的数据
//若该题是求区间和的话，应该通过al数组来修改ali数组才行 --- 减去之前的数据，加上更改的数据
int N, M;

void updata(int pos, int data, int arr_len)
{
    for (int i = pos; i <= arr_len; i += lowest_bit(i))
        ali[i] = std::max(ali[i], data);
    return;
}

int query(int left, int right)
{
    int max_ans = -0x7f7f7f7f, i = right;
    for (; i >= left && i - lowest_bit(i) + 1 >= left; i -= lowest_bit(i))//递推到头
        max_ans = std::max(max_ans, ali[i]);
    while (i >= left)//若i还是大于等于left则还没有枚举完成，继续枚举
    {
        max_ans = std::max(max_ans, al[i]);
        if (i - lowest_bit(i) + 1 < left)i--;
        else
        {
            max_ans = std::max(max_ans, ali[i]);
            i -= lowest_bit(i);
        }
    }
    return max_ans;
}

int main(void)
{
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &al[i]);
        updata(i, al[i], N);
    }
    while (M--)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", query(x, y));
    }
    return 0;
}