F-排列计算

题目描述

天才程序员菜哭武和石头组队参加一个叫做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×10^5^) 和 m (1≤m≤2×10^5^) 。
接下来 m 行，每行输入两个数 l 和 r ，代表这次查询排列中第 l 个到第 r 个的和。

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

示例1

输入

7 3
1 3
3 7
5 6

输出

46

说明
一个符合条件的排列是 [1,3, 6, 4, 7, 5, 2]，
于是最终的得分为 (1 + 3 + 6) + (6 + 4 + 7 + 5 + 2) + (7 + 5) = 46

尝试：
刚拿到题目的时候看到排列，想用next_permutation()全排列一个个比较结果，算出最大的结果，于是暴试，发现数据太大实在不可能。

最后的输出只要求结果，不要求中间的具体排列组合。
然后一直在从样例里找灵感，发现样例的结果其实就是1~7（n）中间的数字加起来，并且最后加上重复的两个不同的数字，而题目又要求结果最大，故使得最后两个不同的数字在n中是最大的。所以用一个数组存储每次l、r及其中间数字的出现次数，并以1加到n为参考，找出缺漏的数字和重复的数字还有他们的个数，在1加到n的结果上加减。然后发现大的思路没什么问题，但是这个实现实在太麻烦了，也会超时。

思路详解：

首先我们要确立每个数字被查询的次数。这个时候可以用差分前缀和来记录每个数字的次数。然后排序，记录次数最小的对应1，记录次数最大的对应n即可，中间次数即对应由1至n递增的数字，并且把对应的数字乘记录次数的结果累加就是最后的结果

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long int ll;
using namespace std;

ll d[200005];
int main() {
  int n, m;
  ll sum = 0;
  cin >> n >> m;
  memset(d, 0, sizeof(d));
  int x, y;
  while (m--) {
    cin >> x >> y;
    d[x]++;d[y+1]--;
  } 
  for (int i = 1; i <= n; i++) {
    d[i] = d[i] + d[i-1];//前缀和
  }
  sort(d+1, d+n+1);
  for (int i = 1; i <= n; i++) {
    sum += d[i] * i;//对应排列数字*记录次数
  }
  cout << sum << endl;
}