题意:
给出n项的数列A[ ], q个询问, 询问 [ l, r ] 之间项的和. 求A的全排列中该和的最大值.
思路:
记录所有询问, 利用差分数列qd[ ], 标记第 i 项被询问的次数( 每次区间增1 ). 最后对qd, A 进行升序排序, 对应项相乘, 求和.
理由是: 越大的数被询问覆盖的次数越多那么总和就越大.
差分数列简单易用.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 2e5+5;
typedef long long ll;
int val[MAXN];
int dq[MAXN];
int sum[MAXN];
int main()
{
int n,q......
阅读全文