差分

发表于2021-10-26更新于2021-10-26阅读次数

差分 & 前缀和

前缀和的差分为原序列
差分的前缀和为原序列

用差分实现区间操作

给定一个长度为n的数列a，要求支持操作add(L,R,k)表示对a[ L ]~a[ R ]的每个数都加上k。并求修改后的序列a。

我们考虑用差分的做法。这里 需要一个数组c，c用来记录某一个位置相对于前一个位置的改变量。我们对[L,R]区间进行加值操作，在c[L]处加一个k，在c[R+1]处就减去一个k。最后求序列的每个位置变成了多少，只需要求一下c数组的前缀和即可得到a。

例题

Mod, Xor and Everything HDU - 6275 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
* @Author: Marhoosh
* @Date:   2021-10-11 11:00:11
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-26 20:08:49
*/
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=1e5+11;
const ll mod=998244353;
ll f2[maxn],f3[maxn],sum2[maxn],sum3[maxn];
ll qpow(ll b,ll p){
    ll ans=1;
    while(p){
        if(p&1)  ans=ans*b%mod;
        p>>=1;
        b=b*b%mod;
    }
    return ans;
}
int main(){
    ll ca;scanf("%lld",&ca);
    while(ca--){
        memset(f2,0,sizeof(f2));memset(f3,0,sizeof(f3));
        ll n,m;scanf("%lld%lld",&n,&m);
        for(ll i=1;i<=m;i++){
            ll x,y,type;scanf("%lld%lld%lld",&x,&y,&type);
            if(type==2)  f2[x]++,f2[y+1]--;
            else  f3[x]++,f3[y+1]--;
        }
        ll ans2=INF,ans3=INF;
        sum2[0]=sum3[0]=0;
        for(ll i=1;i<=n;i++){
            sum2[i]=sum2[i-1]+f2[i];
            ans2=min(ans2,sum2[i]);
            sum3[i]=sum3[i-1]+f3[i];
            ans3=min(ans3,sum3[i]);
        }
        if(ans2==INF)  ans2=0;
        if(ans3==INF)  ans3=0;
        ll ans=qpow(2,ans2)*qpow(3,ans3)%mod;
        cout<<ans<<endl;
    }
    return 0;
}