本文共 1432 字，大约阅读时间需要 4 分钟。

Powered by:AB_IN 局外人

差分与前缀和对称！！！

题目描述

天才程序员菜哭武和石头组队参加一个叫做国际排列计算竞赛 (International Competition of Permutation Calculation, ICPC) 的比赛，这个比赛的规则是这样的：

一个选手给出一个长度为 n 的排列，另一个选手给出 m 个询问，每次询问是一个形如 (l, r) 的数对，查询队友给出的排列中第 l 个数到第 r 个数的和，并将查询到的这个区间和加入总分，最后总分最高的队伍就能获胜。

石头手速很快，在比赛一开始就给出了 m 个询问；菜哭武也很强，他总是能找到最合适的排列，使得他们队的总分尽可能高。

在看比赛直播的你看到了石头给出的 m 个询问，聪明的你能不能预测出他们队伍最终的得分呢？

一个排列是一个长度为 n 的数列，其中 1 ~ n 中的每个数都在数列中恰好出现一次。比如 [1, 3, 2] 是一个排列，而 [2, 1, 4] 和 [1, 2, 3, 3] 不是排列。

输入描述

第一行输入两个数 n (1≤n≤2×105) 和 m (1≤m≤2×105) 。

接下来 m 行，每行输入两个数 l 和 r ，代表这次查询排列中第 l 个到第 r 个的和。

输出描述

输出一个整数，代表他们队伍总分的最大值。

蒟蒻想法

首先看数据2*10^5次方，只能用O（n）和O（nlogn）来写，所以得找一个logn的算法。蒟蒻一开始没看数据，先写了一个桶排，结果就t了。一看数据才知道桶排稳稳 t。所以我选择nlogn的算法——差分。

一维差分还是很好写的

先上代码

#include 
   
    using namespace std;typedef long long ll;const int maxn=2e5+10;ll b[maxn],ans;int n,m,l,r;int main(){       scanf("%d%d",&n,&m);    while(m--){           scanf("%d%d",&l,&r);        b[l]++;b[r+1]--;//因为此时原数组为全0，则不需要差分    }    for(int i=1;i<=n;i++){           b[i]+=b[i-1];    }    sort(b+1,b+1+n);    for(int i=1;i<=n;i++){           ans+=i*b[i];    }    printf("%lld",ans);    return 0;}
   

然后也可以写函数，比较方便

a为原数组，b为处理后的。

void chai_fen(){   //先差分，形成差分数组    for(int i=1;i<=n;i++)        //a[i]=read();这里的a[]为原数组，由于此题原数组全为0，且不用读入，故可省略这一步。        b[i]=a[i]-a[i-1];}void init(int l,int r,int num){   //后对差分数组处理    b[l]+=num;    b[r+1]-=num;}void get(){   //最后前缀和得出经过处理后的原数组    for(int i=1;i<=n;i++)        b[i]+=b[i-1];  }

完结。

转载地址：http://iryg.baihongyu.com/