分类目录归档：数据结构

洛谷 P1801 黑匣子_NOI导刊2010提高（06）

发表评论

异常清晰，自己花了好长时间想出来的，继续加油！

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
struct BlackBox {
private:
    priority_queue<ll,vector<ll>,greater<ll> > minHeap;
    priority_queue<ll> maxHeap;
public:
    void add(ll num) {
        if (maxHeap.empty())minHeap.push(num);
        else if (num < maxHeap.top()) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
            maxHeap.push(num);
        }
        else minHeap.push(num);
    }
    ll get() {
        ll re = minHeap.top();
        maxHeap.push(minHeap.top());
        minHeap.pop();
        return re;
    }
}BB;
int m, n;
ll arr1[200005], arr2[200005];
ll arr2Ptr = 1;
int main() {
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) cin >> arr1[i];
    for (int i = 1; i <= n; i++)cin >> arr2[i];
    for (int i = 1; i <= m; i++) {
        BB.add(arr1[i]);
        while (arr2[arr2Ptr] == i) {
            cout << BB.get() << endl;
            arr2Ptr++;
        }
    }
}

洛谷 P3367 【模板】并查集

发表评论

明明记得之前应该有并查集的板子在博客里？怎么找不到了？？

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int father[10005];
int _find(int num) {
    if (father[num] == -1)return num;
    else return father[num] = _find(father[num]);
}
void _union(int v1, int v2) {
    if (_find(v1) == _find(v2))return;
    father[_find(v2)] = v1;
}
int n, m;
int main(){
    memset(father, -1, sizeof(father));
    cin >> n >> m;
    while (m--) {
        int z, x, y;
        cin >> z >> x >> y;
        if (z == 1)_union(x, y);
        else cout << (_find(x) == _find(y) ? 'Y' : 'N') << endl;
    }
}

洛谷 P1030 求先序排列

发表评论

这类型的题（给中序和前后任一个，让求另外一个的）已经做了不下3、4遍了。。
再贴出来，代码风格可能会不大一样。。。应该是相比之前的有很多改进的。。

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
51
52
53
54
55
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<deque>
#include<map>
#include<cstring>
using namespace std;

struct node {
    char l, r;
    node() {
        l = r = '*';
    }
    node(char l1, char r1) {
        l = l1;
        r = r1;
    }
};
map<char, node> dic;

string in, post;

inline int searchInTraversal(char v, int s, int e) {
    for (int i = s; i <= e; i++)if (in[i] == v)return i;
    return -1;
}
char buildTree(int is, int ie,int ps,int pe) {
    char father = post[pe];
    if (is == ie && ps == pe) {
        dic[father] = node();
        return father;
    }
    if (is > ie || ps > pe) {
        return '*';
    }
    int posOfF = searchInTraversal(father, is, ie);
    int lTreeLen = posOfF - is;
    char l = buildTree(is, posOfF - 1, ps, ps + lTreeLen - 1);
    char r = buildTree(posOfF + 1, ie, ps + lTreeLen, pe - 1);
    dic[father] = node(l, r);
    return father;
}
void preTraversal(char node) {
    if (node == '*')return;
    cout << node;
    preTraversal(dic[node].l);
    preTraversal(dic[node].r);
}

int main() {
    cin >> in >> post;
    char f=buildTree(0, in.length() - 1, 0, post.length() - 1);
    preTraversal(f);
}

洛谷 P1886 滑动窗口

发表评论

单调队列板子题。第一次新学，仍需继续努力练习。

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
51
52
53
54
55
56
57
58
59
60
61
62
/*

洛谷 P1886 滑动窗口 STL程序（各种优化都做的不大好，时间略长，但能AC）
“单调队列”数据结构 参考文档：
1、https://blog.csdn.net/a_bright_ch/article/details/77076228
2、https://blog.csdn.net/zhelong3205/article/details/77624699
3、https://blog.csdn.net/er111er/article/details/78344161
4、https://www.luogu.org/blog/hankeke/solution-p1886

建议真心想学的可以参考材料自己动手写一个。

*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
int n, k;
int arr[1000005];
deque<int> dq,pq;
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)cin >> arr[i];
    //单调队列求最小
    for (int i = 1; i <= n; i++) {
        //维护队尾并插入
        while (!dq.empty() && dq.back() > arr[i]) { //求最大和最小的区别在第二个条件是大于号还是小于号
            dq.pop_back();
            pq.pop_back();
        }
        dq.push_back(arr[i]);
        pq.push_back(i);
        //剔除无效队首并获得最优解
        while (!pq.empty() && pq.back() - pq.front() >= k) {
            dq.pop_front();
            pq.pop_front();
        }
        if (i >= k)cout << dq.front() << " ";
    }
    cout << endl;
    dq.clear();
    pq.clear();
    //单调队列求最大
    for (int i = 1; i <= n; i++) {
        //维护队尾并插入
        while (!dq.empty() && dq.back() < arr[i]) { //求最大和最小的区别在第二个条件是大于号还是小于号
            dq.pop_back();
            pq.pop_back();
        }
        dq.push_back(arr[i]);
        pq.push_back(i);
        //剔除无效队首并获得最优解
        while (!pq.empty()&&pq.back() - pq.front() >= k) {
            dq.pop_front();
            pq.pop_front();
        }
        if (i >= k)cout << dq.front()<< " ";
    }
   
}

洛谷 加分二叉树

发表评论

题号：P1040
很有意义，想了不短时间，和一位群里的同学讨论了一下：代码如下：

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
51
52
53
54
55
56
57
58
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
int n;
struct re{
    int i;
    string s;
    re(){
       
    }
    re(int i,string s){
        this->i=i;
        this->s=s;
    }
    re operator = (const re r){
        this->i=r.i;
        this->s=r.s;
        return *this;
    }
}f[32][32];
int scores[35];
string construction(int num){
    string s="";
    while(num!=0){
        s.insert(0,1,'0'+num%10);
        num/=10;
    }
    s+=' ';
    return s;
}
re dfs(int l,int r){
    if(l==r)return re(scores[l],construction(l));
    if(l>r)return re(1,"");
    if(f[l][r].i!=0)return f[l][r];
    int mm=0;
    string s;
    for(int i=l;i<=r;i++){
        re re1=dfs(l,i-1);
        re re2=dfs(i+1,r);
        if(mm<re1.i*re2.i+scores[i]){
            mm=re1.i*re2.i+scores[i];
            s=construction(i)+re1.s+re2.s;
        }
    }
    return f[l][r]=re(mm,s);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>scores[i];
    re re1=dfs(1,n);
    cout<<re1.i<<endl;
    cout<<re1.s;
}

Codeforces Round #494 (Div. 3) 1003 A/C/D题解

发表评论

A题：非常简单，只要找重复数字的最大个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
int arr[105];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int tmp;
        cin>>tmp;
        arr[tmp]++;
    }
    int maxn=0;
    for(int i=1;i<=100;i++){
        maxn=max(maxn,arr[i]);
    }
    cout<<maxn;
}

C题：用个前缀和优化一下，剩下的暴力去吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,k;
double arr[5005];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>arr[i];
    for(int i=2;i<=n;i++)arr[i]+=arr[i-1];
    double maxavg=0,curavg;
    for(int i=k;i<=n;i++){
        for(int j=i;j<=n;j++){
            curavg=(arr[j]-arr[j-i])/i;
            maxavg=max(maxavg,curavg);
        }
    }
    printf("%.15lf",maxavg);
}

D题：把所有二的次幂数全部搞到桶里，然后按照次幂由高到低往下减，看最后能不能减到0，如果能即可，不能就不能。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,q;
int bucket[32];
int powarr[32];
int checkpower(int num){
    if(num==1)return 0;
    int cnter=0;
    while(num!=1){
        num/=2;
        cnter++;
    }
    return cnter;
}
void program_init(){
    powarr[0]=1;
    for(int i=1;i<=30;i++){
        powarr[i]=powarr[i-1]*2;
    }
}
int main(){
    program_init();
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int num;
        cin>>num;
        bucket[checkpower(num)]++;
    }
    for(int i=1;i<=q;i++){
        int num,cnter=0;
        cin>>num;
        for(int i=30;i>=0;i--){
            cnter+=min(num/powarr[i],bucket[i]);
            num-=min(num/powarr[i],bucket[i])*powarr[i];
        }
        if(num!=0)cout<<-1<<endl;
        else cout<<cnter<<endl;
    }
}

洛谷 【模板】线段树 1

发表评论

题号：P3372

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cassert>
#include<vector>
#include<list>
#include<stack>
#include<queue>
struct node{
    long long value;
    long long lazymark;
}segment_tree[400005];
void build(int root, long long * arr, int start, int end){
    segment_tree[root].lazymark = 0;
    if (start == end){
        segment_tree[root].value = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(root * 2 + 1, arr, start, mid);
    build(root * 2 + 2, arr, mid + 1, end);
    segment_tree[root].value = segment_tree[root * 2 + 1].value + segment_tree[root * 2 + 2].value;
}
void pushdown(int root,int start,int end){
    if (segment_tree[root].lazymark == 0)return;
    int mid = (start + end) / 2;
    segment_tree[root * 2 + 1].lazymark += segment_tree[root].lazymark;
    segment_tree[root * 2 + 2].lazymark += segment_tree[root].lazymark;
    segment_tree[root * 2 + 1].value += segment_tree[root].lazymark*(mid - start + 1);
    segment_tree[root * 2 + 2].value += segment_tree[root].lazymark*(end - mid);
    segment_tree[root].lazymark = 0;
}
long long query(int root, int cstart, int cend, int qstart, int qend){
    if (qstart > cend || qend < cstart)return 0;
    if (qstart <= cstart&&cend <= qend)return segment_tree[root].value;
    pushdown(root,cstart,cend);
    int cmid = (cstart + cend) / 2;
    return query(root * 2 + 1, cstart, cmid, qstart, qend) + query(root * 2 + 2, cmid + 1, cend, qstart, qend);
}
void update(int root, int cstart, int cend, int ustart, int uend, long long addvalue){
    if (cend < ustart || uend < cstart)return;
    if (ustart <= cstart&&cend <= uend){
        segment_tree[root].value += addvalue*(cend - cstart + 1);
        segment_tree[root].lazymark += addvalue;
        return;
    }
    pushdown(root,cstart,cend);
    int cmid = (cstart + cend) / 2;
    update(root * 2 + 1, cstart, cmid, ustart, uend, addvalue);
    update(root * 2 + 2, cmid + 1, cend, ustart, uend, addvalue);
    segment_tree[root].value = segment_tree[root * 2 + 1].value + segment_tree[root * 2 + 2].value;
}

using namespace std;
int n, m;
long long arr[100005];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    build(1, arr, 1, n);
    while (m--){
        int op;
        cin >> op;
        if (op == 1){
            int x, y;
            long long z;
            cin >> x >> y >> z;
            update(1, 1, n, x, y, z);
        }
        else{//op==2
            int x, y;
            cin >> x >> y;
            cout << query(1, 1, n, x, y) << endl;
        }
    }
}

zcysky标程：

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
51
52
53
54
#include<bits/stdc++.h>
const int N=100005;
typedef long long ll;
using namespace std;
int a[N],n,m;
inline ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
ll sumv[N<<2],addv[N<<2];
#define lson (o<<1)
#define rson (o<<1|1)
inline void pushup(int o){sumv[o]=sumv[lson]+sumv[rson];}
inline void pushdown(int o,int l,int r){
    if(!addv[o])return;
    ll tag=addv[o];addv[o]=0;int mid=(l+r)>>1;
    addv[lson]+=tag;addv[rson]+=tag;
    sumv[lson]+=tag*1LL*(mid-l+1);sumv[rson]+=tag*1LL*(r-mid);
}
inline void build(int o,int l,int r){
    if(l==r){sumv[o]=a[l];return;}
    int mid=(l+r)>>1;
    build(lson,l,mid);build(rson,mid+1,r);
    pushup(o);
}
inline void optadd(int o,int l,int r,int ql,int qr,ll v){
    if(ql<=l&&r<=qr){sumv[o]+=v*1LL*(r-l+1);addv[o]+=v;return;}
    int mid=(l+r)>>1;pushdown(o,l,r);
    if(ql<=mid)optadd(lson,l,mid,ql,qr,v);
    if(qr>mid)optadd(rson,mid+1,r,ql,qr,v);
    pushup(o);
}
inline ll querysum(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return sumv[o];
    pushdown(o,l,r);
    int mid=(l+r)>>1;ll ans=0;
    if(ql<=mid)ans+=querysum(lson,l,mid,ql,qr);
    if(qr>mid)ans+=querysum(rson,mid+1,r,ql,qr);
    return ans;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    while(m--){
        int opt=read(),l=read(),r=read();
        if(opt==1){
            ll k=read();optadd(1,1,n,l,r,k);
        }
        else printf("%lld\n",querysum(1,1,n,l,r));
    }
}

20180816更新：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
using namespace std;

struct segmentTree{
    typedef long long ll;
    const static ll MAX=100000;
    ll v[4*MAX],m[4*MAX];
    inline static ll lson(ll r){return r*2+1;}
    inline static ll rson(ll r){return r*2+2;}
    void build(ll r,ll * a,ll s,ll e){
                m[r]=0;
                if(s==e){v[r]=a[s];return;}
                ll md=(s+e)>>1;
        build(lson(r),a,s,md);
        build(rson(r),a,md+1,e);
        v[r]=v[lson(r)]+v[rson(r)];
        }
    void pushDown(ll r,ll s,ll e){
        if(m[r]==0)return;
        ll md=(s+e)>>1;
        m[lson(r)]+=m[r];
        m[rson(r)]+=m[r];
        v[lson(r)]+=m[r]*(md-s+1);
        v[rson(r)]+=m[r]*(e-md);
        m[r]=0;
    }
    ll query(ll r,ll cs, ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r];
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)/2;
        return query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe);
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv){
        if(ce<us||ue<cs)return;
        if(us<=cs&&ce<=ue){v[r]+=addv*(ce-cs+1);m[r]+=addv;return;}
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv);
        update(rson(r),cmd+1,ce,us,ue,addv);
        v[r]=v[lson(r)]+v[rson(r)];
    }
}ST;
typedef long long ll;
ll n,m;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        int op,x,y,k;
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)<<endl;
        }
    }
}

洛谷 海底高铁

发表评论

题号：P3406
把数据类型都开成long long，不然等着丢分？？

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
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
long long track_dif[100005], track[100005];
long long P[100005];
long long A[100005], B[100005], C[100005];
long long cost;
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> P[i];
    }
    for (int i = 1; i <= n - 1; i++){
        cin >> A[i] >> B[i] >> C[i];
    }
    for (int i = 1; i <= m - 1; i++){
        int l = min(P[i], P[i + 1]), r = max(P[i], P[i + 1]);
        track_dif[l]++;
        track_dif[r]--;
    }
    for (int i = 1; i <= n - 1; i++){
        track[i] = track[i - 1] + track_dif[i];
    }
    for (int i = 1; i <= n - 1; i++){
        cost += min(track[i] * A[i], C[i] + track[i] * B[i]);
    }
    cout << cost;
}

洛谷10月月赛R2·浴谷八连测R3 -Chtholly- 浮游大陆的68号岛

发表评论

洛谷题号：3932
一个前缀和的破题改了两个钟头，真是罪过。。。
借鉴了xsun2001同学的思路……在此表示感谢。。。
原来xsun2001同学代码中有可能存在的两点错误：第一个，有可能错在read函数里，读入进来的是int。第二，中间的所有计算过程全部需要取模。我把这两点改好之后就没问题了。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
#define MOD 19260817
long long n, m;
long long dis[200005], goods[200005];
long long prefixsum_dis[200005], prefixsum_goods[200005], prefixsum_cost[200005];
//从1到i点的距离/物品数/距离*物品数
#define LeftDis(l,r,x) ((prefixsum_cost[r] - prefixsum_cost[l - 1] + MOD)% MOD - (prefixsum_dis[x] * (prefixsum_goods[r] - prefixsum_goods[l - 1] + MOD) % MOD) + MOD) % MOD
#define RightDis(l,r,x) ((prefixsum_dis[x] * (prefixsum_goods[r] - prefixsum_goods[l - 1] + MOD) % MOD) - (prefixsum_cost[r] - prefixsum_cost[l - 1] + MOD) % MOD +MOD ) % MOD
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 2; i <= n; i++){
        cin >> dis[i];
        dis[i] %= MOD;
    }
    for (int i = 1; i <= n; i++){
        cin >> goods[i];
        goods[i] %= MOD;
    }
    for (int i = 1; i <= n; i++){
        prefixsum_dis[i] = (prefixsum_dis[i - 1] + dis[i]) % MOD;
        prefixsum_goods[i] = (prefixsum_goods[i - 1] + goods[i] % MOD) % MOD;
        prefixsum_cost[i] = (prefixsum_cost[i - 1] + prefixsum_dis[i] * goods[i] % MOD) % MOD;
    }
    for (long long i = 1; i <= m; i++){
        long long result = 0;
        long long x, l, r;
        cin >> x >> l >> r;
        if (l >= x){
            result += LeftDis(l,r,x);
        }
        else if (r <= x){
            result += RightDis(l,r,x);
        }
        else{
            result += LeftDis(x + 1, r, x);
            result += RightDis(l, x - 1, x);
        }

        cout << result%MOD << endl;
    }
    return 0;
}

题解地址：
洛谷月赛R2训练营R3

差分数组的学习

发表评论

今天在洛谷八连测R2的群里讨论T2时，遇到了这个问题。搞了半天才弄懂，在这里总结一下，免得以后再要用就忘了。
先出一个问题：
给定一个长度为N的序列A：首先进行X次操作，每次操作在Li和Ri这个区间加上一个数Ci。
进行Y次询问，每次询问Li到Ri的区间和。
有人会说这是树状数组/线段树的裸题，直接用树状数组/线段树去写。但是因为线段树/树状数组不是特别好写（到现在也不会线段树/树状数组好长时间没打忘光了），所以有人就就想出来差分数组这么一个好办法来解决这个问题。
首先，请注意！差分数组的使用是有条件的！我上面所提到的问题因为是离线的，所以可以使用差分数组，而如果是在线的问题，差分数组就不要用了，还是乖乖的去写线段树吧。
大家应该都知道前缀和，而差分数组本质上是前缀和的逆运算，前缀和是加号，而差分数组在推导的时候，则是减号。
对于上面的问题，我们将序列A[n]进行差分，设差分数组D[i]=D[i]-D[i-1]。差分数组推导完毕之后，进行区间加减操作。
假设我们要在闭区间[l,r]上统一加上值k,那么我们只需：令D[l]+=k;D[r+1]-=k即可。然后对D[n]进行前缀和操作，生成数组A[n]，再对A[n]进行前缀和操作，生成数组B[n]。那么闭区间[Li,Ri]的区间和就可用B[Ri]-B[Li-1]来表示了。