差分应用

题目链接

#include<bits/stdc++.h>

using namespace std;

int n, m;
const int M = 5e5 + 9;
int tree[M];

void update(int x, int y) {
    for (int pos = x;pos <= n;pos += pos & (-pos))
        tree[pos] += y;
}

int ask(int x) {
    int ans = 0;
    for (int pos = x;pos;pos -= pos & (-pos))
        ans += tree[pos];
    return ans;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int c;int last = 0;
    //构造差分树
    for (int i = 1;i <= n;i++)cin >> c, update(i, c - last), last = c;
    while (m--) {
        int a;cin >> a;
        if (a == 1) {
            int x, y, k;cin >> x >> y >> k;
            update(x, k);
            update(y + 1, -k);
        }
        else if (a == 2) {
            int z;cin >> z;
            cout << ask(z) << '\n';
        }
    }
    return 0;
}

维护区间最值

题目链接

    #include<iostream>
        #include<cstdio>
        #include<cmath>
        #include<cstring>
        #include<cstdlib>
        #include<algorithm>
        #include<queue>
        #define ll long long
        #define re register
        #define il inline
        #define fp(i,a,b) for(re int i=a;i<=b;i++)
        #define fq(i,a,b) for(re int i=a;i>=b;i--)
        using namespace std;
        const int N=50005; 
        int n,q,c[N],b[N],s[N]; //b维护最大值，s维护最小值
        il int gi()
        {
          re int x=0,t=1;
          re char ch=getchar();
          while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
          if(ch=='-') t=-1,ch=getchar();
          while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
          return x*t;
        }
        il void add(re int x,re int k)//区间维护最大最小值
        {
            for(;x<=n;x+=x&-x) b[x]=max(b[x],k),s[x]=min(s[x],k);
        }
        il int Query(re int l,re int r)//区间查询最大最小值
        {
            re int mn=2e9,mx=-1;
            while(l<=r)
            {
                for(;r-(r&-r)>=l;r-=r&-r) mx=max(mx,b[r]),mn=min(mn,s[r]);
                mx=max(c[r],mx);mn=min(mn,c[r]);
                r--;//还有一部分区间未涉及
            }
            return mx-mn;
        }
        int main()
        {
            memset(s,63,sizeof(s));
            n=gi();q=gi();
            fp(i,1,n)
            {
                c[i]=gi();
                add(i,c[i]);
            }
            fp(i,1,q) 
            {
              re int l=gi(),r=gi();
              printf("%d\n",Query(l,r));
            }
            return 0;
}